DP

DP

• 메모이제이션(memoization): 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술로, DP의 핵심
• DP는 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘

DP를 적용할 수 있는 조건

• 중복 부분문제 구조(Overlapping subproblems)
  • 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해를 이용하여 순환적으로 큰 문제 해결
  • 점화식을 통해 표현
• 최적 부분문제 구조(Optimal substructure)
  • 최적화의 원칙을 만족해야 DP를 적용할 수 있다.
  • 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 뜻이다.

Divide and Conquer vs DP

• 분할 정복
  • 연관이 없는 부분 문제로 분할
  • 부분 문제를 재귀적으로 해결하고 결합
• DP
  • 연관이 있는 부분 문제에만 적용
  • 부분 문제들은 더 작은 부분 문제들을 공유함
  • 모든 부분 문제를 한번만 계산하고 결과를 저장하고 재사용함