Dynamic Programming

Dynamic Programming

큰 문제를 한번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 것을 분할정복 기법이라고 합니다. 작은 문제들을 풀다보면 반복해서 푸는 경우가 생기는데 매번 재계산을 대신 값을 저장했다가 사용하는 것을 Dynamic Programming이라고 합니다.

예시

가장 많은 예시로 피보나치 수열이 있습니다.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
1~2번 째 수를 제외하고 수열의 길이가 N일 때 P(N) = (n - 2) + (n - 1)의 식입니다.

예로들면, 4번째 자리인 숫자 3을 만들기 위해서는, 1하고 2가 더합니다. 그 다음 숫자인 5는 2와 3이 더해진 값이고, 숫자 3은 1하고 2가 더해진 값이기에 작은 문제의 결과 값이 필요해지는 상황이 생깁니다.

이런 경우 Dynamic Programming을 사용해 큰 문제를 작은 문제로 만들며, 작은 문제의 결과 값을 저장하는 Memoization을 이용해 값을 저장하여 문제를 해결합니다.