DP(Dynamic Programming)는 먼저 작은 부분 문제들의 해들을 구하고 이들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 문제를 해결하는 알고리즘 설계 기법이다.
DP를 적용하려는 문제는 다음과 같은 조건을 가지고 있어야 한다.
- 중복 부분문제 구조(Overlapping subproblems)
- 최적 부분문제 구조(Optimal substructure)
중복 부분문제 구조
- 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해(Optimal Solution)를 이용하여 순환적으로 큰 문제를 해결한다. 이 때 순환적인 관계를 명시적으로 표현하기 위해서 DP에서는 수학적 도구인 점화식을 사용한다.
- DP는 문제의 순환적인 성질 때문에 이전에 계산되어졌던 작은 문제의 해가 다른 어딘가에서 필요하게 되는데 이를 위해 DP에서는 이미 해결된 작은 문제들의 해들을 배열을 만들어 저장해놓는다.
- 저장된 해들이 다시 필요할 때 마다 해를 얻기 위해 다시 문제를 재계산하지 않고 참조를 통하여 중복된 계산을 피하게 된다.
최적 부분문제 구조
- DP가 최적화에 대한 어느 문제에나 적용될 수 있는 것은 아니다. 주어진 문제가 최적의 원칙을 만족해야 DP를 효율적으로 적용 가능하다.
- 최적의 원칙은 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것이다. DP의 방법자체가 큰 문제의 최적 해를 작은 문제의 최적해 들을 이용하여 구하기 때문에 만약 큰 문제의 최적해가 다른 문제들의 최적화의 해들로 구성되지 않는다면 이 문제는 DP를 적용할 수 없다.
분할 정복과 비교하면?
분할 정복과 DP는 둘 다 부분 문제로 분할하여 해결 방법을 찾는다. 하지만 큰 차이점이 있는데, 분할 정복은 부분 문제들간의 연관이 없고, DP는 부분 문제들간의 연관이 있다는 점이다.
