[심화] 다이나믹 프로그래밍 Dynamic Programming

다이나믹 프로그래밍 DP (Dynamic Programming)

개념

하나의 문제를 여러 개의 작은 문제로 쪼개어, 작은 문제의 해를 이용해 전체 문제의 해를 구하는 알고리즘
반복되는 연산 감소 -> 효율 증가, 빠른 속도

적용

2가지 조건

• 겹치는 부분 문제 Overlapping Subproblems
  전체 문제{동일한 작은 문제 여러 개}
  문제에서 겹치는 부분이 있어야 함
• 최적 부분 구조 Optimal Substructure
  부분 문제의 해 => 전체 문제의 해
  작은 문제에서 구한 답으로 전체 문제에서의 답을 구할 수 있는 경우

방식

• Tabulation
  상향식 Bottom-Up
  반복문 사용
  table

• Memorization
  하향식 Top-Down
  재귀 함수 사용
  memory

---

참고: https://hongjw1938.tistory.com/47