동적계획법(Dynamic Programming)

동적계획법이란 큰 문제를 작은 문제로 나누어 푸는 문제.

---

분할정복(Divide and Conquer)과 차이

• 공통점
  - 문제를 잘게 쪼개서, 가장 작은 단위로 분할

• 차이점
  - 부분 문제는 중복되어서, 상위 문제 해결 시에 재활용된다.

  • 문제가 재활용되기에 재활용되는 문제를 계산하지 않기 위해 Memoization 기법을 활용한다.

• 분할 정복
  - 부분 문제는 중복되지 않는다.
  - Memoization 기법을 활용 하지 않는다.

---

조건

• 동일한 작은 문제가 반복이 일어나는 경우
• 같은 문제는 구할 때마다 정답이 같다.

---

Memoization

메모이제이션은 동적 프로그래밍에서는 작은 문제들이 반복되고, 이 작은 문제들의 결과값은 항상 같다. 때문에 이 점을 이용해 한 번 계산한 작은 문제를 저장해놓고 다시 사용한다. 이를 Memoiztion이라 함.

1. 작은 문제들이 반복된다.
2. 같은 문제는 구할 때 마다 정답이 같다.

---