동적 계획법

동적계획(動的計劃, dynamic programming)은 어떤 알고리즘이 부분 문제 반복과 최적 기본 구조라는 특징을 가지고 있을 때, 이 알고리즘의 실행시간을 줄이는 방법이다. 수학자인 리처드 벨만이 1953년에 '동적계획'이라는 용어를 만들었다.

[편집] 예제

보통 피보나치 수열을 구하는 함수는 다음과 같이 작성한다.

function fib(n)
 if n = 0 or n = 1
  return 1
 else
  return fib(n-1) + fib(n-2)

이때, fib(5)를 구한다고 한다면 계산은 다음과 같이 이루어진다.

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

여기에서 세 번째 줄의 fib(2)가 중복되어 계산되고, 이것은 전체적인 계산 속도를 떨어뜨린다. 이 알고리즘의 시간 복잡도는 지수 함수가 된다.

여기에서 각 함수의 계산값을 저장하는 객체 m을 추가하면, 이 알고리즘은 다음과 같이 바뀐다.

var m := map(0 → 1, 1 → 1)

function fib(n)
 if n not in keys(m)
  m[n] := fib(n-1) + fib(n-2)
 return m[n]

이렇게 각 계산값을 저장하면, 중복 계산이 줄어들고 시간 복잡도는 O(n)이 된다.

longest-common subsequence problem - 주어진 두 개 이상의 문자열 내에서 공통적으로 발견되는 가장 긴 문자열을 발견하는 알고리즘
Cocke-Younger-Kasami (CYK) algorithm - 주어진 문맥무관문법으로 원하는 문자열을 만들 수 있는지 판정하는 알고리즘
비터비 알고리즘
Earley algorithm
벨만-포드 알고리즘
데이크스트라 알고리즘 - 주어진 시작점과 종료점 사이의 가장 짧은 경로를 찾아내는 알고리즘
플로이드-와샬 알고리즘
chain matrix multiplication의 최적 곱셈 순서
부분집합 합 알고리즘
배낭 문제

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Chapter 15: Dynamic Programming, pp.323–369.