동적 계획법(Dynamic Programming)의 두 가지 속성

Dynamic Programming (DP)

DP는 복잡한 문제를 여러 개의 부분 문제(sub-problems)로 쪼개서 해결하는 알고리즘 패러다임이다. 이때, 이러한 부분 문제들의 해(solution)을 기록하여 중복되는 부분 문제를 여러 번 계산하지 않도록 한다.
DP로 풀 수 있는 문제는 다음의 두 가지 속성을 갖는다.

(1) Overlapping Subproblems
(2) Optimal Substructure

---

Overlapping Subproblems

DP는 부분 문제의 해를 결합한다는 점에서 분할 정복(Divide and Conquer)과 비슷하지만, 같은 부분 문제의 해를 여러 번 이용한다는 점에서 분할 정복과 다르다. 따라서 중복된 부분 문제(Overlapping Subproblems)를 풀어야 하는 문제가 아니라면 DP는 유용하지 않다.
예를 들어, 이진 탐색(Binary Search)는 부분 문제를 여러 번 풀 필요가 없다. 따라서 DP가 아니라 분할 정복이 적절하다. 반면, 피보나치 수를 계산하는 문제는 이전 항을 반복해서 사용해야 하므로 DP로 해결 할 수 있다.
부분 문제의 해를 기억하는 방법은 크게 두 가지가 있다.

(1) Memoization (Top-Down)
(2) Tabulation (Bottom-Up)

---

Optimal Substructure

어떤 문제의 최적해(Optimal solution)를 부분 문제의 최적해를 이용하여 알 수 있다면, 해당 문제가 Optimal Substructure 속성이 있다고 부른다.
예를 들어, 최단 경로 문제는 다음과 같은 Optimal Substructure를 가진다.
만약 어떤 노드 x가 시작 노드 u와 도착 노드 v의 최단 경로에 존재한다면, u와 v의 최단 경로는 u와 x의 최단 경로에 x와 v의 최단 경로를 합한 것과 같다. Floyd-Warshall와 Bellman-Ford 알고리즘은 DP의 전형적인 예다.

---

Conclusion

따라서, 어떤 문제를 DP로 풀기 위해서 가장 먼저 할 일은 해당 문제가 Optimal Substructure 속성을 갖는지 확인하는 것이다.

---

Reference

• Overlapping Subproblems Property in Dynamic Programming | DP-1
• Optimal Substructure Property in Dynamic Programming | DP-2