동적 계획법(dynamic programming)이란 말은 수학에서 유래한 용어이다. 의미를 살펴보면 프로그래밍 언어에서 말하는 동적(dynamic), 정적(static)이란 말과는 구별을 두어야 할 듯 싶다. 동적 계획법은 일종의 최적화 기법으로 어떤 문제를 부분적으로 나눌 수 있을 때 중복되는 문제해결 과정을 재사용하여 계산을 최적화 하는 기법이다. 이를 메모이제이션(memoization)이라고 한다. 예를 들어 어떤 문제집합을 풀 때 func(1,2)라는 호출이 여러번 있다면 func(1,2)라는 호출에 대한 결과를 캐시에 저장해 놓고 다음 호출 부터는 캐시에 있는 결과값을 바로 얻는 방식이다. 단 이 경우에 func(1, 2)라는 값은 언제나 동일함을 보장해야 한다. 가장 쉬운 예로는 피보나치 수..
