🌹 정리 by 장미(https://velog.io/@newbiekim/)
Dynamic Programming은 Optimization Problem을 해결하는 전략 중 하나이다.
여기서 Optimization Problem이란, 문제를 해결하는 최적의 답(Optimal Solution)을 찾아야 하는 문제를 뜻한다.
Optimal Solution은 하나 이상일 수 있으며, 최대 혹은 최소값을 가지는 Solution을 찾는 문제들이 주를 이룬다. (예: 가장 빨리 도착하는 경로(Solution)의 소요 시간(Value)은? 등…)
DP는 해결하려는 문제를 좀 더 작은 크기의 SubProblem으로 나누고, 그 SubProblem의 Optimal Solution을 활용하여 원래 Problem의 Optimal Solution을 찾는 방식이다.
여기서 문제를 계속 잘게 쪼개다 보면, 어느 순간 겹치는(Overlapping) SubProblem이 생긴다. 그럴 때 이 서브 문제들을 계속 계산하는 것이 아니라 맨 처음 한 번만 계산을 하고, 그 결과를 저장한 뒤에 필요하다면 또 재사용한다.
| Top-Down Approach | Bottom-Up Approach | |
|---|---|---|
| 구조 | Recursive(재귀) | Iterative(for-loop) |
| SubProblem | ||
| 결과 저장 | Memoization | Tabulation |
| 선호되는 상황 | SubProblems의 일부만 계산해도 최종 Optimal Solution을 구할 수 있을 때 | 모든 SubProblems를 계산해야 최종 Optimal Solution을 구할 수 있을 때 |
Top-Down Approach는 문제들을 작은 크기의 문제로 나누어서 해결하는 것이고, Bottom-Up Approach는 일단 작은 크기의 문제부터 차근차근 해결해 나가는 것이다.