동적 계획법(DP) 완벽 가이드

DP(Dynamic Programming(동적계획법)이란?

큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말

1.1 DC(Divide and Conquer, 분할정복)과의 차이

DP는 작은 문제를 나누었을 때 작은 문제가 중복이 일어나며 단지 작은 문제로 나누어 푸는 방법

DC는 작은 문제를 나누었을 때 작은 문제가 중복이 일어나지 않음

1.2 DP 방법

모든 작은 문제들은 한번만 풀어야 한다.

정답을 구한 작은 문제를 메모해 놓고 다시 그보다 큰 문제를 풀어나갈 때 같은 방법으로 작은 문제를 해결한다.

1.3 DP의 조건

작은 문제가 반복적으로 일어나는 경우

같은 문제는 구할 때마다 정답이 같은 경우

위와 같은 조건을 만족하는 경우에만 동적프로그래밍을 사용할 수 있습니다. 작은 문제의 결과 값이 항상 같다는 점을 이용해 큰 문제를 해결하는 방법입니다.

1.4 Memoization

DP에서 작은 문제들이 반복되고 이 작은 문제들의 결과값이 항상 같다. 이점을 이용하여 한번 계산한 작은 문제를 저장해놓고 다시 사용한다. 이것을 Memoization이라고 한다.

ex) 피보나치

피보나치는 1, 1, 2, 3, 5, 8 ... 의 수를 이루게 된다.

즉, 첫번째와 두번째 값을 제외한 2부터의 수를 계산하는 방법은 이전 수열 + 다음 수열 즉 2를 구하기 위해서는 1 + 1, 3을 구하기 위해서는 1 + 2라는 수열의 합이 사용된다.

1) 작은 문제들이 반복된다.

5번째 값을 구하기 위해서는 3,4번째 값이 필요하다. 다시 4번째 값을 구하기 위해서는 2,3번째 값이 필요하다. 이 경우를 살펴보면 5번째 값을 구하기 위해서도 3번째 값이 필요하고 4번째 값을 구하기 위해서도 3번째 값이 필요하다는 것을 알 수 있다. 즉, 작은 문제가 반복되는 구조

2) 같은 문제는 구할때 마다 정답이 같다.

피보나치 수열의 경우 첫번째, 두번째 값은 각각 1로 고정되어 있다.

즉, 3번째 수열은 언제나 2이고 3번째 수열을 구하기 위해 2번째 수열과 3번째 수열을 이용해 구하므로 언제나 정답이 같다는 사실을 알 수 있다.