동적 계획법

수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

 설명 
주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.

동적 계획 알고리즘은 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다. 이것은 동적 계획법은 문제를 해결하기 위한 모든 방법을 검토하고, 그 중에 최적의 풀이법을 찾아내기 때문이다. 문제가 가능한 모든 방법을 충분히 빠른 속도로 처리할 수 있는 경우, 동적 계획법은 최적의 해법이라고 말할 수 있다.

때로는 단순한 재귀함수에 저장 수열(이전의 데이터를 모두 입력하는 수열)을 대입하는 것만으로도 최적해를 구할 수 있는 동적 알고리즘을 찾을 수 있다. 그러나 대다수의 문제는 이보다 훨씬 더 복잡한 프로그래밍을 요구한다. 그 중에 일부는 여러 개의 매개 변수를 이용하여 재귀 함수를 작성해야 하는 것도 있고, 아예 이러한 방법으로 동적 알고리즘을 짤 수 없는 문제 또한 존재한다. 이러한 퍼즐로는 대표적으로 Egg Dropping Puzzle이 있다.

 그리디 알고리즘과의 비교 
동적 계획법은 위에서 설명했듯이, 가능한 모든 방법을 고려해야 한다는 단점이 있다. 이러한 단점을 극복하기 위하여, 동적 계획법 대신 그리디 알고리즘이 등장했다. 그리디 알고리즘은 항상 최적해를 구해주지는 않지만, 다행히 Minimum Spanning Tree(최소 신장 트리 문제) 등의 여러 문제에서 그리디 알고리즘이 최적해를 구할 수 있음이 이미 입증되었다.

그리디 알고리즘과 동적 계획법을 비교하자. 우리가 차량 정체 구간에서 A라는 지점에서 B라는 지점까지 가능한 빨리 이동하는 경로를 찾고 싶다고 하자. 이 문제에서 동적 계획법을 사용한다면, 우리가 갈 수 있는 모든 상황과 교통 정체를 전부 감안하여 최적의 경로를 찾아낸다. 반면 그리디 알고리즘은 전체적인 상황을 고려하지 않고, 순간순간 교차로가 보일 때마다 가장 빠른 경로를 검색하여 찾아줄 것이다.

물론 동적 계획법으로 경로를 검색하는 동안 우리가 운전을 잠깐 쉬어야 하듯이, 우리는 동적 계획법을 사용하면 약간의 시간이 걸린다는 단점이 있다. 그러나 이렇게 얻어낸 경로는 (교통 환경이 변하지 않았다는 가정 하에) 우리가 갈 수 있는 가장 빠른 길이 된다고 장담할 수 있다.
반면 그리디 알고리즘은 즉효성이 있는 대신, 항상 최적의 경로를 찾아주지는 않는다. 각 구간마다 최적의 경로를 찾는다고 해도 그것이 전체적으로 최적의 경로가 되지는 않기 때문이다. 즉, 동적 계획법은 그리디 알고리즘에 비해 시간적으로는 효율적이지 못할 수는 있어도, 그 결과에 대해서는 효율적인 값을 구할 수가 있다.

 역사 
수학자인 리처드 벨만이 1940년대에 사용하던 용어였다. 1953년, 벨만은 큰 문제 안에 작은 문제가 중첩되어있는 문제를 해결하는 데 사용하는 이 방법을 '동적 계획법'이라 이름붙였다.

벨만은 그의 자서전, '태풍의 눈'에서 다음과 같이 말했다.

즉, 'Dynamic'이라는 말은 벨만이 이런 알고리즘의 '시가변적이며 다단계적인' 특성을 나타내기 위해서 채택한 용어인 것이다. 또한 'Programming'이라는 단어는 공군 내에서도 워드 프로세서 교육이나 군수 물자 운송 등에 이용되는 단어였기 때문에 사용하는데 아무 제약이 없었던 것이다. 이렇게 만들어진 '동적 계획법'이라는 단어는 선형 계획법이나 수리 계획법처럼 하나의 프로그래밍 기법을 나타내는 단어가 되었다.

 예제 
 피보나치 수열 
보통 피보나치 수열을 구하는 함수는 다음과 같이 작성한다.
 function fib(n)
  if n = 0
   return 0
  else if 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)이 된다.

 동적계획을 이용한 알고리즘 
 최장 공통 부분 수열 - 주어진 두 개 이상의 수열의 부분수열이 되는 가장 긴 수열을 찾는 알고리즘
 Cocke-Younger-Kasami (CYK) 알고리즘 - 주어진 문맥무관문법으로 원하는 문자열을 만들 수 있는지 판정하는 알고리즘

 비터비 알고리즘
 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. . Chapter 15: Dynamic Programming, pp.323–369.

 외부 링크 
 David B. Wagner. Dynamic Programming. 동적계획에 대한 소개글 (1995년)
 Ohio State University: CIS 680: class notes on dynamic programming
 A Tutorial on Dynamic programming 
 More DP Notes
 Algorithmist's Dynamic Programming 동적계획의 많은 예제가 있음.


분류:최적화 알고리즘