[알고리즘] 동적 계획법(Dynamic Programming)
2019.10.24
1. 동적 계획법(Dynamic Programming, DP)이란? 동적 계획법(Dynamic Programming, DP)은 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 설계 기법이다. 분할 정복 알고리즘과 차이는 메모이제이션의 필요여부다. 분할 정복 알고리즘은 계산된 소문제의 출력값을 저장하지 않는다. (1회용) 동적 계획법은 계산된 소문제의 출력값을 저장해서 다음 계산때 사용한다. (재활용) 동적 계획법을 적용시킬 수 있는 예시는 다음과 같다. f(a,b) = f(a-1,b) + f(a,b-1) (a,b >= 1 ) f(0,0) = 1, 임의의 자연수 n에 대해 f(n,0) = f(0,n) = 1 위 그림에서 초록색으로 칠해논 부분이 문제를 작은 문제로 분할하는 과정에서 중복되는 문제다. 그림의 패..