Dynamic Programming 이라는 말은 최적화 문제를 연구하는 수학 이론에서 왔으며, 전산학에서 일반적으로 사용하는 동적(dynamic), 혹은 프로그래밍(programming) 이란 단어와는 무관합니다. 따라서 Dynamic Programming의 적절한 번역은 동적 프로그래밍이 아니라 동적 계획법 입니다.
동적 계획법 알고리즘의 구현 단계
1. 주어진 문제를 완전 탐색을 이용해 해결합니다. (재귀함수호출)
2. 중복된 부분 문제를 한 번만 계산하도록 메모이제이션을 적용합니다. (캐싱)
메모이제이션 이란?
- 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법입니다.
- 참조적 투명 함수(referential transparent function)의 경우에만 적용할 수 있습니다.
참조적 투명 함수란?
- 입력이 고정되어 있을 때 그 결과가 항상 같은 함수들 (외부 변수들의 영향을 받지 않는 함수)