#1 동적 프로그래밍이란?
① 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고 ② 이를 재귀호출로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법이다.
#2 문제의 조건
- 최적하부구조
- 부분문제들 간의 중복 존재
최적하부구조
- 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있다.
- 큰 문제와 작은 문제 간의 관계를 점화식으로 표현 가능하다.
- 예: 펙토리얼 함수
부분문제들 간의 중복 존재
- 재귀호출로 문제를 해결할 때 중복되는 연산이 존재
- 중복 연산에 의한 엄청난 비효율 발생
#3 구현전략
- 다이나믹 프로그래밍을 적용하는 방식으로 탑다운 방식과 버텀업 방식이 있다.
- 탑다운 방식은 재귀호출을 사용하고 버텀업 방식은 재귀호출 대신에 반복문을 사용한다.
- 양 방법 모두 중복되는 연산의 결과를 따로 저장한다.
- 계산결과를 저장한 자료를 탑 다운의 경우에는 메모이제이션, 버텀업은 타뷸레이션이라고 부른다.