동적 계획법

이 항목은 Dynamic Programming, 다이나믹 프로그래밍 으로도 들어올 수 있습니다.

1 개요

동적 계획법(Dynamic Programming), 줄여서 DP는 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.
조금 장난스럽게 말해서 답을 재활용하는거다. 앞에서 구했던 답을 뒤에서도 이용하고, 옆에서도 이용하고....
엄밀히 말해 동적 계획법은 구체적인 알고리즘이라기보다는 문제해결 패러다임에 가깝다. 동적 계획법은 "어떤 문제를 풀기위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다. 동적 계획법을 써야 좋은 효과를 얻을 수 있는 문제들은 주로 Optimal Substructure라고 불리는 구조를 가진 것들이다. 쉽게 이야기하면, 뭘 구하기 위해서 했던 계산을 또하고 또하고 계속해야하는 류의 문제를 풀 때 동적 계획법이 효과를 발휘한다는 것.

경제학에서는 성장 모형등을 계산하는데 자주 쓰인다. 이 때는 컴퓨터 그딴거 없고 손으로 푼다. 석기시대

동적 계획법을 영문으로는 다이나믹 프로그래밍(dynamic programming)이라 표기하는데, 이름과는 달리 딱히 다이나믹하지도 않고 프로그래밍이라는 단어와도 큰 연관이 없다. 이에 대해 이광근 교수의 저서 "컴퓨터 과학이 여는 세계"에서는 다이나믹 프로그래밍을 본질적인 의미를 더 살려서 기억하며 풀기로 더욱 적절하게 번역하였다.

2 구현

동적 계획법의 접근 방식은 기본적으로 분할 정복 알고리즘과 비슷하다. 위에서도 설명했지만 동적 계획법을 사용하는 알고리즘 역시 주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결과값을 이용해 원래 문제의 답을 산출하기 때문이다. 여기서 분할정복과 차이가 생기는 부분은 원래의 문제를 부분 문제로 나누는 방식에 있다. 동적 계획법의 경우 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한 번만 계산하고 저장해둔 뒤 다시 한 번 이 부분 문제를 이용할 때에는 저장해둔 정답을 바로 산출하여 이용함으로써 속도를 향상시킨다.

2.1 접근

동적 계획법의 개념과 구현에 대해 정확하게 짚고 넘어가기 위해 동적 계획법을 적용시킬 수 있는 예에 대해 알아보자.

• 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)을 계산한다고 해보자. 이 경우 아래 그림과 같은 참조를 거치게 된다.

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

(a,b)	그냥 계산시 연산 횟수	동적 계획법 이용시 연산 횟수
(2,2)	5	4
(4,4)	70	17
(6,8)	3003	49
(10,10)	184756	101

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

2.2 예시

동적 계획법을 이해하는 가장 쉬운 예시로 피보나치 수열 구하기가 있다. 물론 굳이 동적 계획법을 쓰지 않고도 훨씬 깔끔하게 구할 수 있지만, 이해를 돕기 위해 여기서는 정통적인 동적 계획법으로 풀어본다.

2.2.1 재귀함수 형태의 피보나치 수열

피보나치 수열은 다음과 같이 '재귀함수'의 형태(Recursive Form)로 표현된다.

f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2) when n > 2

이 수학적인 정의는 매우 깔끔하지만, 실제로 컴퓨터가 계산하기엔 매우 부적합한 형태이다. 위 정의를 그대로 C언어로 구현하면 아래와 같다.

int f(int n)
{
if(n <= 2)
return 1;
else
return f(n-1)+f(n-2);
}

C언어를 열심히 배운 사람들은 다 알겠지만, 함수가 호출되면 프로그램 메모리의 스택(Stack)이라는 곳에 데이터가 쌓이게 된다. 그 함수의 실행이 끝났을 때 다시 메모리가 해제되는 방식인데, 이 말인 즉슨 함수가 계속 호출되면 메모리에 쌓이는 것들이 계속 증가한다는 소리다! 여기서 재귀적 피보나치 함수의 문제가 드러난다. 5번째 피보나치 수열을 구하기 위해선 다음과 같은 함수 호출이 발생한다.

 1. f(5)를 구하기 위해서 f(4)와 f(3)을 구함
2. f(5)에서 호출된 f(4)를 구하기 위해서 f(3)와 f(2)를 호출함
3. f(4)에서 호출된 f(3)을 구하기 위해서 f(2)와 f(1)을 호출함
4. f(5)에서 호출된 f(3)을 구하기 위해서 f(2)와 f(1)을 호출함 (또 호출함)
=> 총 9번 호출됨

숫자가 작으니 망정이지, 숫자가 조금만 커져도 시간 복잡도와 공간 복잡도가 지수 스케일로 폭발한다! (이런 걸 Exponential Explosion이라고 한다) 시간 복잡도야 대충 1년 정도 개기면 된다해도, 공간 복잡도의 경우 스택 오버플로우가 발생해 프로그램이 튕겨버린다.

2.2.2 동적 계획법 형태의 피보나치 수열

동적 계획법에서는 이런 '삽질(=반복계산)'을 막기 위해 이전에 계산했던 값들을 배열에 저장한다. C언어로 구현하면 아래와 같다. 다만 상황에 따라서 다르게 짤 수도 있기 때문에 절대적인 정답은 아니다.

int f_data[N] = {1, 1}; // N은 정의하기 나름
int last_pos = 1; // 마지막으로 계산한 지점
int f(int n)
{
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)이 되는 기적도 볼 수 있다... 더군다나 map을 응용하면 공간복잡도도 O(log n)이 된다. 물론 시간복잡도가 O(log n) 정도 되면 웬만한 범위는 아래 링크가 걸려 있는 메모이제이션을 동반한 재귀호출로 머리 아프지 않게 코딩을 해 낼 수 있으니 참고하자.

2.3 메모이제이션

문서 참고.

3 기타

적절한 경우에 동적 계획법을 사용하면 막대한 양의 메모리를 희생하는 대신 겁나 빠르게 해를 계산해준다. 지수 복잡도 알고리즘을 다항 시간으로 줄여주기도 하고, 같은 다항 시간 알고리즘도 차수를 낮추는 기적을 보여준다. .예를 들면 숫자 배열 중에서 가장 '최대 합을 갖는 구간' 찾기 같은 경우, O(n^3)짜리 알고리즘 하나를 쥐어짜서 divide&conquer로 만들면 O(n*logn) 정도의 복잡도로 만들 수도 있는데, 동적 계획법으로 더욱 쥐어짜면 O(n)으로 만들 수도 있다. 체감상 따지자면 몇만 개의 데이터 속에서 최대 구간을 찾으려면 O(n^3)은 80000초 가량이 걸릴 수도 있는데 O(n)으로는 1초도 안되어 나오기까지 한다.

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

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

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

• 3항 이상의 재귀 수열
• 0-1 배낭 문제(0-1 Knapsack Problem) : 견딜 수 있는 무게가 제한된 배낭에 가장 많은 가치의 물건을 넣기. 모든 무게를 정수로 볼 수 있다면, 배낭의 최대 무게 W일 때 O(W)로 구할 수 있다. 그게 아닌 경우라면 NP-hard이므로 근사 알고리즘을 써야 한다. 비슷한 것으로 Rational Knapsack Problem이 존재하는데, 이는 보통 Greedy Algorithm으로 사용된다. 0-1 Knapsack고 다른 점은 단순히 물건을 넣느냐 빼느냐가 아니라, 잘라서 (일부분만) 넣을 수 있게 하는 것이다.
• 가장 긴 증가 수열 문제(LIS Problem) : 아무 수열이나 주고, 순서를 바꾸지 않은 상태로 뽑아서 만들 수 있는 가장 긴 증가수열의 길이 구하기. O(N²)이며, 이진 탐색을 사용할 줄 안다면 O(NlogN)으로도 줄일 수 있다.
• 그래프 상의 최단거리 문제 - Floyd, Bellman-Ford. 점 개수가 V일 때 O(V³)으로 구할 수 있다. Floyd는 모든 출발점과 도착점에 대해 최단거리를 구할 수 있고, Bellman-Ford는 거리 합이 음수인 사이클이 있을 때에 대해서도 구할 수 있다. (Dijkstra는 일종의 BFS이다.)