4.2.2 동적 계획법 이해하기

동적 계획법(dynamic programming)은 1950년대에 리차드 벨만(Richard Bellman)이 알고리즘 최적화를 위해 제안한 전략입니다. 이 전략은 무거운 연산 작업을 재활용하는 똑똑한 캐싱(caching) 메커니즘에 기반을 두고 있습니다. 이 캐싱 메커니즘을 메모이제이션(memoization)이라고 부릅니다.

동적 계획법은 풀려는 문제가 작은 하위 문제들로 구성된 경우에 유용하게 사용할 수 있습니다. 하위 문제를 푸는 연산 작업은 다른 하위 문제에도 반복되는 경우가 많습니다. 동적 계획법의 핵심 아이디어는 시간이 많이 소요되는 연산 작업을 수행한 후, 이 결과를 다른 하위 문제에 재활용하는 것입니다. 이 과정을 담당하는 것이 메모이제이션입니다. 따라서 동적 계획법은 입력 데이터를 반복 처리하는 재귀적 구조를 가진 문제를 풀 때 강력한 성능을 발휘합니다.