CodeAngie

문제 상자의 크기가 입력된 배열이 주어졌을 때, 앞에서부터 작은 상자를 뒤의 큰 상자에 넣는다면 최대 몇 개의 상자를 겹칠 수 있는지 개수를 묻는 문제이다. 풀이 왼쪽의 작은 상자를 오른쪽의 큰 상자에 넣는다는 것은 오른쪽으로 이동하면서 오름차순으로 증가하는 상자를 골라야 한다고 말할 수 있다. 즉, 상자배열 내에서 가장 긴 증가하는 부분 수열 (LIS) 을 구한다면, 겹칠 수 있는 최대 상자의 개수를 알 수 있다. 알고리즘 겹치는 상자의 개수를 담는 dp 를 1로 초기화한다. 상자의 크기가 담긴 box 배열을 순회한다. 해당 상자의 이전에 있는 상자들과 비교하면서 담을 수 있는 상자라면, 이전 상자에 담기는 상자의 개수(dp[j])에 1을 더한 값과 현재 dp[i]에 담긴 값을 비교하여 더 큰 값을 d..

문제 1번에서 N번까지 나열되어 있는 집들의 색을 RGB 중 한 가지 색으로 칠할 때, 맨 첫 번째 집과 맨 마지막 집의 색이 겹치지 않으면서 앞뒤로 위치한 이웃집끼리의 색도 겹치지 않게 칠하는데 드는 비용의 최솟값을 구하는 문제이다. 이웃집과 색이 겹치는 경우는 최소비용이 들더라도 불가능하다. 예를 들어 R-G-G 나 R-G-B-R 등으로 칠할 수 없다. 풀이 기존 RGB거리 문제와의 차이는 맨 첫 번째 집과 맨 마지막 집의 색깔 관계도 살펴봐야 한다는 점이다. 최소비용을 도출하는 점화식은 RGB거리 문제와 동일하다. dp[i]["빨강"] = min(dp[i-1]["초록"], dp[i-1]["파랑"]) + RGB[i]["빨강"] dp[i]["초록"] = min(dp[i-1]["빨강"], dp[i-1][..

문제 1번에서 N번까지 직선으로 나열되어 있는 집들의 색을 앞뒤로 위치한 이웃집과 겹치지 않게 RGB 중 한 가지 색으로 칠할 때 드는 비용의 최솟값을 구하는 문제이다. 이웃집과 색이 겹치는 경우는 최소비용이 들더라도 불가능하다. 예를 들어 R-R-G 나 R-G-B-B 등으로 칠할 수 없다. 풀이 서로 겹치지 않게 색칠하려면, 현재 위치(i)에서 초록색을 선택했을 경우 이전 위치(i-1)에는 빨간색이나 파란색을 선택해야 한다. i번째 집을 초록색으로 칠한다면 i까지의 최소 비용은 i-1번째 집이 빨간색과 파란색일 경우 중 더 작은 비용을 가진 색의 비용과 i번째 집의 초록색 비용을 더한 값이 된다. 모든 위치에서 앞집과 다른 색으로 최소비용을 계산해줌으로써 색이 겹치지 않게 집을 칠하는 비용의 최솟값을 ..

문제 N*N 크기의 게임판이 있을 때, (0, 0)에서 (N-1, N-1)까지 규칙(조건)에 맞게 이동할 수 있는 경로의 수를 구하는 문제이다. 문제 조건 각 칸에는 한 번에 이동 가능한 거리가 쓰임 반드시 오른쪽 혹은 아래쪽으로 이동 풀이 문제의 조건을 주의해야 한다. (오른쪽과 아래쪽으로만 한 번에 직선 이동 가능) 오른쪽과 아래쪽으로만 이동 가능하기 때문에 왼쪽 위의 경로의 수를 먼저 구하고 해당 경로의 수를 활용하여 다음 위치의 경로의 수를 구할 수 있다. 즉, DP를 활용할 수 있다. 위의 그림은 의 예시의 풀이 과정을 시각화한 것이다. 각 칸을 방문하면서 게임판의 범위 내에서 이동 가능한 거리라면, DP에 저장되어 있는 현재 위치까지 도달하는데 가능한 경로의 수..

동적프로그래밍동적 프로그래밍은 큰 문제를 작은 문제로 나누어 푸는 방법이다.분할 정복과는 다르게 작은 문제를 푸는데서 답이 같은 문제가 중복적으로 일어날 경우 사용한다.보통 점화식을 만들 수 있다.1. 동적프로그래밍의 조건큰 문제는 작은 문제로 나눌 수 있고 작은 문제가 반복해서 나타난다.같은 문제라면 계산할 때마다 같은 답이 도출된다.2. 메모이제이션 (Memoization)메모이제이션은 한번 풀었던 작은 문제를 다시 반복해서 풀지 않기 위해 메모해두고 필요할 때 답만 꺼내 보는 것이다.담아 놓는 것이기 때문에 캐싱 (caching) 이라고도 불린다.메모이제이션을 통해 먼저 구한 결과를 담아 두면, 아래 피보나치 예시에서 점선으로 표시된 노드는 먼저 먼저 계산된 값을 사용하면 되기 때문에 반복해서 계산..

문제 두 전봇대 A와 B 사이에 몇 개의 전깃줄을 제거해야 교차하는 전깃줄이 없는지 구하는 문제이다. 즉, 최소한의 제거할 수 있는 전깃줄의 개수를 도출해야 한다. 풀이 서로 전깃줄이 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구해야 한다. 예를 들어, A-1번과 B-8번이 연결된 전깃줄보다 A-3번과 B-9번이 연결된 전깃줄이 더 아래 있는 것을 알 수 있다. 이를 통해 A의 번호가 순차적으로 커질 때, 각각의 A와 연결된 B의 번호도 더 커진다면 교차하지 않는 전깃줄의 개수를 구할 수 있음을 알 수 있다. A의 정렬된 번호를 리스트의 인덱스로 두고, B의 번호를 가지고 가장 긴 증가하는 수열(LIS)을 구함으로써 교차하지 않는 전깃줄의 최대 개수(c)를 구할 수 있다...

가장 긴 증가하는 부분 수열 알고리즘 이란, 왼쪽에서 오른쪽 방향으로 탐색할 때 오름차순으로 증가하는 부분 수열 중 가장 길이가 긴 부분 수열을 찾는 알고리즘이다. 0 1 2 3 4 5 6 10 40 20 50 30 40 60 위의 리스트에서 증가하는 부분 수열은 {10,40,50,60}, {10,20,50,60}, {10,20,30,40,60}, {40, 50, 60} 이 있다. 여기서 가장 긴 증가하는 부분 수열은 {10,20,30,40,60}이며, 부분 수열의 길이는 5가 된다. LIS 알고리즘은 두 가지 방법으로 구성될 수 있다. DP 활용 방법 이분탐색 활용 방법 1. LIS 알고리즘 (DP 활용) 시간복잡도: O(N**2) 1.1. DP 초기화 DP에는 부분 수열의 길이가 담기기 때문에 DP는..