기록공간

동적계획법을 사용하는 문제이다. 아래 층에 있는 수를 선택 할때에는 대각선 왼쪽과 오른쪽 중 하나만 선택이 가능하다는 조건을 상기하며 살펴보도록 하자. 층마다 저장해야 할 정수 값들이 늘어난다. 그렇기 때문에 값을 저장할때나 DP테이블로 사용할때 2차원 배열이 필요하다. 맨 위에 값은 하나이기 때문에 DP테이블에 맨 윗층은 한개의 값이 저장된다. 그리고 2층은 값이두개가 되며 맨 위층의 값과 더하여 DP 테이블에 2개의 값이 저장된다. 여기서 특성을 알수 있는데 양 사이드에 있는 값들은 무조건 왼쪽 값은 그 위층의 맨 왼쪽값과만 더할 수 있고, 오른쪽 값은 그 위층의 맨 오른쪽 값과만 더할 수 있다. 그리고 3층은 값이 세개가 되며 양 사이드 2개의 값은 위와 같은 규칙으로 더해지고, 중간 값 하나는 2..

동적계획법을 사용하는 문제였다. 이번 문제는 다른 문제들과 다르게 DP 테이블을 2차원 배열로 만들어줘야 한다. 한 경우(집)에 3가지 값(RGB)을 DP 테이블에 기록해야 하기 때문이다. 예를들어 어떤 집 N을 R로 칠할경우, 전 집 N - 1은 R로 칠할 수 없으므로 G와 B로 칠하는 비용중 가장 작은 비용을 찾아 N의 R로 칠하는 비용을 더해 DP 테이블에 기록하면 된다. N에서 G와 B도 위와 같은 방법으로 해주면 된다. DP(N에서 R) = DP(N - 1에서 G나 B중 가장 작은 값) + H(N에서 R) DP(N에서 G) = DP(N - 1에서 R나 B중 가장 작은 값) + H(N에서 G) DP(N에서 B) = DP(N - 1에서 R나 G중 가장 작은 값) + H(N에서 B) (DP는 DP테이..

동적계획법을 사용하는 문제였다. 규칙 계단을 오른때는 1칸 또는 2칸 오를 수 있다. 연속된 3칸을 오를 수 없다. 마지막 계단은 무조건 밟아야한다. 위 3가지 규칙을 바탕으로 마지막 계단을 밟는 경우를 두가지로 분류 해볼 수 있다. 1. 마지막 계단을 밟고 그 전 계단을 밟는 경우 (하지만 위 규칙 2번으로 인해 무조건 전 계단을 밟은 이후 전전전 계단을 밟아야 한다.) 이 경우 점화식은 S[n] = S[n] + S[n - 1]이 된다. (위 규칙 2번으로 인해 DP[n - 3]도 더해줘야 한다.) (S는 계단의 값들을 보관하는 배열이고 DP는 계단까지의 최대값을 보관하는 DP테이블(배열)이다.) 2. 마지막 계단을 밟고 그 전전 계단을 밟는 경우 이 경우 점화식은 S[n] = S[n] + DP[n -..

역시 동적계획법을 사용하여 푸는 문제이다. 우선 규칙을 살펴보자. 피보나치 규칙인 F(N) = F(N - 1) + F(N - 2)를 염두해두고 보자. * N이 0일때 0 호출 횟수 = 1 1 호출 횟수 = 0 * N이 1일때 0 호출 횟수 = 0 1 호출 횟수 = 1 * N이 2일때 0 호출 횟수 = (1일때 0 호출 횟수) + (0일때 0 호출 횟수) = 0 + 1 = 1 1 호출 횟수 = (1일때 1 호출 횟수) + (0일때 1 호출 횟수) = 1 + 0 = 1 * N이 3일때 0 호출 횟수 = (2일때 0 호출 횟수) + (1일때 0 호출 횟수) = 1 + 0 = 1 1 호출 횟수 = (2일때 1 호출 횟수) + (1일때 1 호출 횟수) = 1 + 1 = 2 0과 1의 호출 횟수가 필요하기 때문에 ..

동적계획법을 사용하는 문제이다. 규칙을 먼저 살펴보자. * 1일 경우 1 -> 1개 * 2일 경우 1 + 1 2 -> 2개 * 3일 경우 1 + 1 + 1 2 + 1 1 + 2 3 -> 4개 * 4일 경우 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 2 + 1 + 1 2 + 1 1 + 3 3 + 1 -> 7개 (혹은 F(3) + F(2) + F(1) = 4 + 2 + 1 = 7) * 5일 경우 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 1 + 2 + 1 + 1 1 + 1 + 2 + 1 1 + 1 + 1 + 2 2 + 2 + 1 2 + 1 + 2 1 + 2 + 2 3 + 1 + 1 1 + 3 + 1 1 + 1 + 3 2 + 3 3 + 2 -> 13개 (혹은 F(4) + F(3..

동적계획법을 사용하여 푸는 문제이다. 우선 규칙을 먼저 살펴보자. * 정수 2 1. 1을 빼면 1이 된다. 2. 2로 나누어 떨어지고 1이 된다. 3. 3으로 나누어 떨어지지 않는다. -> 정수 2를 1로 만드는 최소 횟수는 1이다. * 정수 3 1. 1을 빼면 2가 된다. 정수 2에서 1로 되는 최소 횟수는 1이다. 그러므로 1 + 1 = 2이다. 2. 2로 나누어 떨어지지 않는다. 3. 3으로 나누어 떨어지고 1이 된다. -> 정수 3을 1로 만드는 최소 횟수는 1이다. * 정수 4 1. 1을 빼면 3이 된다. 정수 3에서 1로 되는 최소 횟수는 1이다. 그러므로 1 + 1 = 2이다. 2. 2로 나누어 떨어지고 2가 된다. 2에서 1로 되는 최소 횟수는 1이다. 그러므로 1 + 1 = 2이다. 3...

LIS(최장증가수열)는 동적계획법으로 풀 수 있는 알고리즘 문제 중 하나이다. 어떤 임의의 수열이 주어졌을때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들수 있다. 이 때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장증가수열이라고 한다. 예를 들어 다음 수열이 주어졌다고 하자. 3 5 7 9 2 1 4 8 위 수열에서 몇 개의 수를 제거해 부분 수열을 만들었다고 하자. 3 7 9 1 4 8 (5, 2 제거) 7 9 1 8 (3, 5, 2, 4 제거) 3 5 7 8 (9, 2, 1, 4 제거) 1 4 8 (3, 5, 7, 9, 2 제거) 이들 중 세번째와 네번째 수열은 오름차순으로 정렬되어 있다. 이들을 '증가 부분 수열'이라고 한다. 그리고 세번째와 같이 이러한 수열 중 가장 긴..

동적계획법 이란? 동적계획법(다이나믹 프로그래밍)은 큰 문제를 작은 문제로 나누어 푸는 알고리즘 방법이다. 다이나믹 프로그래밍이란 명칭은 그냥 알고리즘 창조한 사람이 단지 이름이 멋지다는 이유로 붙여진 것이다(...). 분할정복(Divide and Conquer)과 다른 점 거의 비슷하지만 결정적인 차이점이 존재한다. 그것은 바로 나눠진 작은 문제에서 중복이 일어나는가 안일어나는가이다. 분할정복은 큰 문제를 해결하기 위해 그냥 작은 문제로 나누어 푸는 방법이다. 특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점이다. 동적계획법은 작은 문제들이 반복되는것(단, 바뀌지 않음)을 이용해 풀어나가는 방법이다. 동적계획법의 방법 모든 작은 문제들은 꼭 한번만 풀어야 한다. 그러므로 작은 문제의 정답은 어딘가..