CS/알고리즘

[Algo] DP (dynamic programming)

hio9_9 2023. 1. 23. 03:00

DP(dynamic programming) 

  • 복잡한 문제를 여러 개의 간단한 작은 문제로 나누어 푼 다음 작은 문제의 답을 모아 최종적으로 문제를 해결하는 방법
  • "중복되는 부분 문제""최적 부분 구조"를 만족할 때 사용
    • 중복되는 부분 문제(overlapping subproblem): 동일한 부분 문제(작은, 간단한 문제)를 반복적으로 해결
    • 최적 부분 구조(optimal substructure): 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결 가능
  • Memorization, 이전에 해결한 하위 문제의 답을 저장해서 반복 작업을 줄이는 것이 핵심