🤢 Dynamic Programing (DP)

🎾DP로 풀어야하는 문제의 속성

• Overlapping Subproblem

  • 문제를 작은 문제로 쪼갤 수 있다.
  • 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.

  → 한 문제를 같은 종류의 작은 문제들로 쪼갤 수 있다.

• Optimal Substructure

  • 문제의 정답을 작은 문제의 정답에서 구할 수 있다. 즉, 문제의 정답을 작은 문제들의 정답을 합하는 것으로 구할 수 있다.
  • 어떠한 작은 문제를 풀던, 그 전에 푼 특정 작은 문제의 정답은 변하지 않는다.

  → 각 작은 문제의 답이 항상 일정하다. → Memoization

즉, 작은 문제에 대한 답을 구할 때, 어딘가에 메모를 해두고, 중복 호출이면 메모해놓은 값을 리턴한다. 중복 호출인지 먼저 검토 && 리턴하고, 아니면 답을 구하고 리턴하는 순서이다.