CS/알고리즘
[Algo] DP (dynamic programming)
hio9_9
2023. 1. 23. 03:00
DP(dynamic programming)
- 복잡한 문제를 여러 개의 간단한 작은 문제로 나누어 푼 다음 작은 문제의 답을 모아 최종적으로 문제를 해결하는 방법
- "중복되는 부분 문제"와 "최적 부분 구조"를 만족할 때 사용
- 중복되는 부분 문제(overlapping subproblem): 동일한 부분 문제(작은, 간단한 문제)를 반복적으로 해결
- 최적 부분 구조(optimal substructure): 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결 가능
- Memorization, 이전에 해결한 하위 문제의 답을 저장해서 반복 작업을 줄이는 것이 핵심