[include(틀:컴퓨터공학)]
[include(틀:이론 컴퓨터 과학)]
[목차]
[clearfix]
== 개요 ==
{{{+1 [[動]][[的]] [[計]][[劃]][[法]] / dynamic programming, DP}}}

[[최적화 이론]]의 한 기술이며, 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 [[알고리즘]] 설계 기법이다.

조금 장난스럽게 말해서 답을 재활용하는 거다. 앞에서 구했던 답을 뒤에서도 이용하고, 옆에서도 이용하고...엄밀히 말해 동적 계획법은 구체적인 알고리즘이라기보다는 문제해결 패러다임에 가깝다. 동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다. [* 초보자라서 이게 무슨 소리인지 잘 이해가 안간다면 "N번째 답을 구하기 위해 N-1번째 답을 활용하는 방식의 접근법" 이라고 이해해도 된다. N번째 답이 N-1번째 답에서 도출될 수 있다면, N-1번째 답은 N-2번째 답에서 도출되고, N-2번째 답은 N-3번째에서.. 하는 방식으로 나아가게 될 것이다. 결국 2번째 답은 1번째 답을 활용해서 구할 수 있으므로, 1번째 답만 구해놓고 dp를 활용하면 원하는 N이 무엇이든 답을 얻을 수 있게 된다. 수준이 올라갈수록 N번째 답을 구하기 위해 N-k번째 답을 활용한다거나 하는 식으로 여러모로 복잡하게 활용되기 시작하지만, 초보자라면 지금 당장은 저렇게 이해해도 무방하다.]

답을 구하기 위해서 했던 계산을 또 하고 또 하고 계속해야 하는 종류의 문제의 구조를 [[그리디 알고리즘#s-2.1|최적 부분 구조(Optimal Substructure)]]라고 부른다. 동적 계획법은 이런 문제에서 효과를 발휘한다.

동적 계획법을 영문으로는 다이나믹 프로그래밍(dynamic programming)이라 표기하는데, 이름과는 달리 딱히 다이나믹하지도 않고 [[프로그래밍]]이라는 단어와도 큰 연관이 없다.[* 동적 계획법의 고안자인 벨만(Richard E. Bellman, 벨만-포드 알고리즘의 그 벨만 맞다.) 은 dynamic 이라는 단어가 멋있어서 이름으로 선택했다고 한다. Programming 이란 단어는 최적화 연구 분야에서 최적의 프로그램을 찾아낸다는 의미로 사용된다. - 프로그래밍 대회에서 배우는 알고리즘 문제해결전략(구종만 저) 1권 p.207][* 벨만이 다이나믹 프로그래밍에 대해 쓴 저서의 서문을 보면 연구소에서 펀딩을 받기에 좋은(...) 단어라서 선택했다고 나온다. 그는 당시 [[벨 연구소]]에 재직중이었다.] 이에 대해 이광근 교수의 저서 "컴퓨터 과학이 여는 세계"에서는 다이나믹 프로그래밍을 본질적인 의미를 더 살려서 '''기억하며 풀기'''로 더욱 [[적절]]하게 번역하였다.
== 구현 ==
동적 계획법의 접근 방식은 기본적으로 [[분할 정복 알고리즘]]과 비슷하다. 위에서도 설명했지만 동적 계획법을 사용하는 알고리즘 역시 주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결과값을 이용해 원래 문제의 답을 산출하기 때문이다. 여기서 분할정복과 차이가 생기는 부분은 원래의 문제를 부분 문제로 나누는 방식에 있다. 동적 계획법의 경우 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한 번만 계산하고 저장해둔 뒤 다시 한 번 이 부분 문제를 이용할 때에는 저장해둔 정답을 바로 산출하여 이용함으로써 속도를 향상시킨다.

[[파일:5-23-2.png|width=500]]

즉, 동적 계획법은 그림과 같이 [[그리디 알고리즘#s-2.1|최적 부분 구조(Optimal Substructure)]]를 지닌 중복된 하위 문제들(Overlapping Subproblems)을 분할 정복으로 풀이하는 문제해결 패러다임이다.
=== 접근 ===
동적 계획법의 개념과 구현에 대해 정확하게 짚고 넘어가기 위해 동적 계획법을 적용시킬 수 있는 예에 대해 알아보자.

 * f(a,b) = f(a-1,b) + f(a,b-1) (a,b >= 1 )
 * f(0,0) = 1, 임의의 자연수 n에 대해 f(n,0) = f(0,n) = 1

위와 같이 정의된 함수에서 주어진 임의의 a,b에 대해 f(a,b)의 값을 효율적으로 구하고자 할 때 동적 계획법을 적용시킬 수 있다.

예를 들어 f(2,2)을 계산한다고 해보자. 이 경우 아래 그림과 같은 참조를 거치게 된다.

[[파일:external/s21.postimg.org/tree.png]]

순서대로 계산횟수를 구해보면 f(2,2)를 구하기 위해 총 5번의 연산을 거쳐야한다. 이때 중복되는 부분 문제[* overlapping subproblems - 두 번 이상 계산되는 부분 문제]에 대한 답을 미리 계산해놓고 연산한다고 가정했을 때 계산횟수를 구해보면 f(2,2)를 구하기 위해 4번의 연산을 거쳐야한다. 이 경우 간단한 예라 중복되는 부분 문제가 f(1,1) 하나뿐이기 때문에 큰 속도의 이득을 볼 수 없지만 a, b의 값이 커질수록 속도 면에서 엄청난 이득을 볼 수 있다. 몇 가지 a, b 값에 대해 f(a, b)를 구하기 위한 연산 횟수를 나타낸 아래 표를 참고해보자.

||<tablebordercolor=#000><rowbgcolor=#000> {{{#fff (a,b)}}} || {{{#fff '''그냥 계산 시 연산 횟수'''}}} || {{{#fff '''동적 계획법 이용 시 연산 횟수'''}}} ||
|| (2,2) || 5 || 4 ||
|| (4,4) || 69 || 16 ||
|| (6,8) || 3002 || 48 ||
|| (10,10) || 184755 || 100 ||

이 정도면 아마 대충 동적 계획법의 효율이 느껴질 것이다. 실제로 a, b가 1 증가할 때마다 연산 횟수는 기하급수적으로 증가하며, 이때 중복되는 부분 문제를 적절히 처리해줌으로써 높은 계산효율을 얻을 수 있는 것이다.

=== 예시 ===
동적 계획법을 이해하는 가장 쉬운 예시로 [[피보나치 수열]] 구하기가 있다. 물론 굳이 동적 계획법을 쓰지 않고도 훨씬 깔끔하게 구할 수 있지만,[* 굳이 알고리즘을 쓸 필요없이 피보나치 수열의 점화식을 표현하는 행렬의 거듭제곱을 하는 것이 가장 깔끔하긴 하다. 행렬의 거듭제곱 계산을 O(log N)에 한다면 시간복잡도 역시 O(log N)이다. 피보나치 수열의 일반항을 이용하는 경우도 시간복잡도는 같지만 일반항에 무리수가 포함된다는 단점이 있다.] 이해를 돕기 위해 여기서는 정통적인 동적 계획법으로 풀어본다.

==== 재귀함수 형태의 피보나치 수열 ====
피보나치 수열은 다음과 같이 [[재귀함수]]의 형태(Recursive Form)로 표현된다.
{{{f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2) when n > 1}}}
이 수학적인 정의는 매우 깔끔하지만, 실제로 컴퓨터가 계산하기엔 매우 부적합한 형태이다. 위 정의를 그대로 C언어로 구현하면 아래와 같다.
{{{#!syntax cpp
int f(unsigned int n)
{
    if(n <= 1)
        return 1;
    else
        return f(n-1)+f(n-2);
}
}}}
C언어를 배우면 왜 문제인지 알 수 있다. 함수가 호출되면 프로그램 메모리의 [[스택(자료구조)|스택]](Stack)이라는 곳에 데이터가 쌓이게 된다. 그 함수의 실행이 끝났을 때 다시 메모리가 해제되는 방식인데, 이 말인 즉슨 함수가 계속 호출되면 메모리에 쌓이는 것들이 계속 증가한다는 소리다! 여기서 재귀적 피보나치 함수의 문제가 드러난다. 5번째 피보나치 수열을 구하기 위해선 다음 그림과 같이 총 15번의 함수 호출이 발생한다.

[[파일:5-23-3.png|width=600]]

숫자가 작을 때는 그나마 괜찮지만, 숫자가 조금만 커져도 시간 복잡도와 공간 복잡도가 지수 스케일로 폭발한다! (이런 걸 Exponential Explosion이라고 한다) 시간 복잡도야 시간을 많이 들이면 견딜 수 있다 해도, 공간 복잡도의 경우 스택 오버플로우가 발생해 프로그램이 튕겨버린다.
==== 동적 계획법 형태의 피보나치 수열 ====
동적 계획법에서는 이런 '삽질(=반복계산)'을 막기 위해 이전에 계산했던 값들을 배열에 저장한다. 대표적인 방식은 Top-down과 Bottom-up이다.

Top-down은 위에서 내려오는 것, 즉, 큰 문제부터 시작해서 계속 작은 문제로 분할해 가면서 푸는 것이다. fibonacci(4)를 구하는 큰 문제는 fibonacci(3)과 fibonacci(2)를 구하는 작은 문제로 나눌 수 있다. fibonacci(3)을 구하는 작은 문제는 fibonacci(2)와 fibonacci(1)을 구하는 더 작은 문제로 나눌 수 있다...따라서 fibonacci(n)을 구하는 큰 문제를 풀 수 있다. 구현은 다음과 같다.
{{{#!syntax cpp
int memo[100]{}; //메모이제이션 공간. 전역 변수이므로 0으로 초기화
int fibonacci(unsigned int n)
{
  if (n<=1) //0번째, 1번째 피보나치 수
    return n;
  if (memo[n]!=0) //메모가 있는지 확인(0으로 초기화되었으므로 0이 아니라면 메모가 쓰인 것임)
    return memo[n]; //메모 리턴
  memo[n]=fibonacci(n-1) + fibonacci(n-2); //작은 문제로 분할
  return memo[n];
}
}}}
Bottom-up은 바닥에서 올라오는 것, 즉, 작은 문제부터 시작해서 작은 문제를 점점 쌓아 큰 문제를 푸는 것이다. 첫 번째 피보나치 수를 구하는 문제와 두 번째 피보나치 수를 구하는 문제를 풀면 세 번째 피보나치 수를 구하는 문제를 풀 수 있다. 두 번째 피보나치 수를 구하는 문제와 세 번째 피보나치 수를 구하는 문제를 풀면 네 번째 피보나치 수를 구하는 문제를 풀 수 있다....이걸 반복하면 n번째 피보나치 수를 구할 수 있다. 구현은 다음과 같다.
{{{#!syntax cpp
int f_data[N] = {1, 1}; // N은 정의하기 나름
int last_pos = 1; // 마지막으로 계산한 지점. 이 코드에선 이미 f_data[1]까지 정의되어있기 때문에 1로 초기화한다.
int f(int n) //피보나치 수열의 제 n항을 구한다. 배열의 관점에서는 n-1번째 요소를 구하는 것.
{
    int i;
    if(f_data[n-1] == 0)  // 아직 구한 적이 없으면 구한다
    {
        for(i=last_pos+1; i<n; ++i)
        {
            f_data[i] = f_data[i-1] + f_data[i-2];
        }
        last_pos = n-1;
    }
    return f_data[n-1];
}
}}}
이렇게 하면 숫자를 저장하는 공간이 계속 필요한 대신 O(n)의 시간 복잡도로 상큼하게(...) 구할 수 있다. 간단한 트릭을 쓰면 공간 복잡도 마저 O(1)로 만들 수 있지만 동적 계획법이랑 관계가 없으니 여기선 생략한다.[* 슬라이딩 윈도우 기법이다. 궁금한 사람은 한번 검색해보자.] 사실 [[분할 정복 알고리즘|분할 정복]]까지 응용하면 시간복잡도가 O(log n)이 되는 기적도 볼 수 있다... 더군다나 [[표준 템플릿 라이브러리|STL]]에 있는 map을 응용하면 공간복잡도도 O(log n)이 된다. 물론 시간복잡도가 O(log n) 정도 되면 웬만한 범위는 아래 링크가 걸려 있는 메모이제이션을 동반한 재귀호출로 머리 아프지 않게 코딩을 해 낼 수 있으니 참고하자.

슬라이딩 윈도우 기법이 궁금하다면 아래의 예제를 펼쳐보자. 가독성을 위해서 C가 아닌 자바스크립트로 작성.
{{{#!folding [JavaScript]
{{{#!syntax javascript
function fibonacci(n) {
   function fibHelp(lastTwo, x) {
      const sum = lastTwo[0] + lastTwo[1];
      return x == 2 ? sum : fibHelp([lastTwo[1], sum], x - 1);
   }
   return n < 2 ? n : fibHelp([0, 1], n);
}
}}}
bottom-up, 혹은 tabulation이라고 하는 방법. 시간복잡도는 O(n), 공간복잡도는 O(1)다. 사실 F(n)을 찾으려면 F(n - 1)와 F(n - 2)만을 기억하고 있으면 되므로 숫자 2개를 가지고 있는 리스트만 있으면 된다. 
}}}
=== [[메모이제이션]] ===
[include(틀:상세 내용, 문서명=메모이제이션)]
== 기타 ==
동적 계획법을 사용하기 적절한 문제에 동적 계획법을 사용하면 매우 빠르게 해를 얻을 수 있다. 지수 복잡도 알고리즘을 다항 시간으로 줄여주기도 하고, 같은 다항 시간 알고리즘도 차수를 낮출 수 있다. 예를 들면 숫자 배열 중에서 가장 '최대 합을 갖는 구간' 찾기 같은 경우, O(n^^3^^)짜리 알고리즘 하나를 쥐어짜서 분할 정복법으로 만들면 O(n*logn) 정도의 복잡도로 만들 수도 있는데, 동적 계획법으로 더욱 쥐어짜면 O(n)으로 만들 수도 있다. 체감상 따지자면 몇만 개의 데이터 속에서 최대 구간을 찾으려면 O(n^^3^^)은 80000초 가량이 걸릴 수도 있는데 O(n)으로는 1초도 안 되어 나오기까지 한다. 

그러나 퍼포먼스가 좋은 만큼 난해하고 복잡하고 디버깅하기 힘들고.... 다른 알고리즘에 비해서 '''풀이가 직관적으로 떠오르지 않기 때문에''', 초심자들이 [[멘탈붕괴]]를 심하게 겪는다. 간단한 동적 계획법들은 1차원 배열을 사용하는데, 조금만 문제가 복잡해지면 2차원 이상의 배열을 써야 한다!!! 그렇다고 항상 그게 맞느냐 하니, 경우에 따라선 2차원 이상의 배열을 쓴게 1차원보다 더 거지같을 수도 있다. 간혹 [[정올]] 같은 데는 4차원 배열 같은 무시무시한 게 나오기도 한다. 거기다 막대한 양의 메모리를 희생한다는 단점도 있다.

동적 계획법을 써서 구현할 수 있는 것들은 대개 [[백트래킹]]으로도 구현할 수 있는데, 백트래킹은 거의 모든 경우를 다 체크하기 때문에 동적 계획법이 빠르다. 하지만 대신 저장할 양이 많기 때문에 상황에 따라서는 동적 계획법으로는 메모리 오버플로우가 날 수도 있지만 백트래킹으로는 돌아가는 경우도 있다.

파이썬의 경우는 딕셔너리나 functools.lru_cache를 이용하여 편리하게 자주 쓰는 함수에 대한 메모이제이션이 가능하다.

ACM ICPC 등의 알고리즘 대회에서 동적 계획법을 사용해야 해결할 수 있는 문제가 자주 출제된다. 이런 문제는 엥간하면 분할 정복법 등을 이용하거나 재귀를 써도 풀리는 게 대부분이지만, '시간 제한'이 짧은 경우가 많아 동적 계획법 만큼의 빠른 알고리즘이 없으면 통과가 불가능할 정도다.[* 심지어 동적계획법을 최적화해서 설계를 해야 하는 경우도 있다. ] ~~학부생 죽는 소리 안 나게 해라~~ 대표적인 "아주 기초적인~~뭐?~~" 동적 계획법 문제로 아래와 같은 것들이 있다..

 * 3항 이상의 재귀 수열
 * [[0-1 배낭 문제]](0-1 Knapsack Problem) : 견딜 수 있는 무게가 제한된 배낭에 가장 많은 가치의 물건을 넣기. 모든 무게를 정수로 볼 수 있다면, 배낭의 최대 무게 W일 때 O(W)로 구할 수 있다. 그게 아닌 경우라면 NP-hard이므로 근사 알고리즘을 써야 한다. 비슷한 것으로 Rational Knapsack Problem이 존재하는데, 이는 보통 [[그리디 알고리즘]]으로 사용된다. 0-1 Knapsack과 다른 점은 단순히 물건을 넣느냐 빼느냐가 아니라, 잘라서 (일부분만) 넣을 수 있게 하는 것이다.
 * [[최장 증가 부분 수열|가장 긴 증가 수열 문제(LIS Problem)]] : 아무 수열이나 주고, 순서를 바꾸지 않은 상태로 뽑아서 만들 수 있는 가장 긴 증가수열의 길이 구하기. O(N²)이며, [[이진 탐색]]을 사용할 줄 안다면 O(NlogN)으로도 줄일 수 있다.
 * [[연쇄 행렬 곱셈 알고리즘|연쇄 행렬 곱셈 문제]]: 주어진 연쇄행렬들의 곱셈을 각 원소의 곱셈 횟수를 최소로 할 수 있는 행렬곱셈의 순서를 찾는 최적화 문제이다. 동적 계획법과 메모이제이션을 적용할 수 있는 대표적인 알고리즘들 중 하나이다. 
 * 그래프 상의 최단거리 문제 - [[벨먼-포드 알고리즘]], [[플로이드-워셜 알고리즘]] : 점 개수가 V일 때 O(V³)으로 구할 수 있다. Floyd-Warshall은 모든 출발점과 도착점에 대해 최단거리를 구할 수 있고, Bellman-Ford는 거리 합이 음수인 사이클이 있을 때에 대해서도 구할 수 있다.  ([[다익스트라 알고리즘]]은 일종의 [[BFS]]이다.)

[[분류:프로그래밍 이론]] [[분류:알고리즘]][[분류:최적화 이론]]