동적 계획법 (DP, Dynamic Programming)
복잡한 문제를 간단한 여러 문제로 나누어 푸는 방법을 뜻한다.
문제를 여러개의 하위 문제로 나누어 해답을 구하고, 저장해 중복되는 문제에서 해답을 가져와 해결한다. 이후 하위 해답을 결합해 최종 해답을 구한다.
동적 계획법은 문제를 해결하기 위한 모든 방법을 검토하고 최적의 방안을 사용하기 때문에 주로 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다.
사용 가능 조건
동적 계획법은 두가지 가정이 만족되는 조건에서 사용 가능하다.
Overlapping Subproblems
여러 번 재사용되는 하위 문제로 분리할 수 있거나 문제에 대한 재귀 알고리즘이 동일한 하위 문제를 반복해서 해결할 수 있다면 Overlapping Subproblems가 있다고 본다.
하위 문제는 상위 문제를 해결할 때 여러 번 반복해서 사용할 수 있어야 한다.
function fibo(n) {
if(n<=2) {
return 1;
}
return fibo(n-1) + fibo(n-2)
}위에 코드에서 피보나치 수열의 5번째 수를 구하면 다음과 같이 함수가 호출된다.
fibo(5) => fibo(4) + fibo(3)
fibo(5) => (fibo(3) + fibo(2)) + (fibo(2) + fibo(1))
fibo(5) => ((fibo(1) + fibo(2)) + fibo(2)) + (fibo(2) + fibo(1))전개된 함수 호출과 같이 하위 해답이 여러번 사용된다.
Optimal Substructure
하위 문제의 최적의 해답으로 최종적인 최적의 해답을 구할 수 있다면 Optimal Substructure를 가지고 있다고 본다
최단 경로는 찾는 문제를 푼다고 했을 때 주어진 조건이 다음과 같다면
A부터 각 목적지의 최단 경로와 비용은 다음과 같다.
- A to B : A => B | 1
- A to C : A => B => C | 4
- A to D : A => B => D | 3
- A to E : A => B => D => E | 5
E까지 가는 최단 경로를 찾을 때 바로 D까지 가는 최단 경로가 최종 최단 경로에 영향을 준다.
즉, 하위 문제의 최적의 해답의 결합이 최종 최적의 해답이 된다.
Reference
코드 스테이츠
wikipedia-동적 계획법
