동적 계획법(dynamic programming)

동적 계획법(dp)이란?

• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
• 메모이제이션을 통해 중복 계산을 방지하여 프로그램 실행 시간을 줄이는 방법

동적 계획법의 조건

• 어떤 문제(problem)가 여러 개의 하위 문제(sub problem)로 나누어지는 경우
• 하위 문제들의 답으로 어떤 문제를 해결할 수 있는 경우
• 서로 다른 문제에서 하위 문제들이 겹치는 경우

---

동적 계획법의 예시

dp를 사용하는 많은 문제 중에 피보나치 수를 구하는 문제가 있다. 피보나치 수는 다음과 같이 정의된다.

fib(n)
{
	if (n = 0)
		then return 0;
	else if (n = 1)
		then return 1;
	else return (fib(n - 1) + fib(n - 2));
}

이 문제는 재귀적 알고리즘으로 해결할 수 있지만 비효율적이다. 이를 dp를 통해 효율적으로 해결할 수 있는데 그 예시는 아래와 같다.

#include <stdio.h>
#include <time.h>
long long int cnt[51];
long long int fib(int n) {
	cnt[n]++;
	if (n <= 1) return n;
	else return fib(n - 1) + fib(n - 2);	
}
main() {
	int start = clock();
	printf("fib(50) = %lld, ", fib(50));
	int stop = clock();
	double duration = (double)(stop - start) / CLOCKS_PER_SEC;
	printf("실행시간: %g초\n", duration);
	for (int i = 0; i <= 50; i++) {
		printf("fib(%d)의 호출 횟수: %lld회\n", i, cnt[i]);
	}
}

이 코드를 실행했을 때 출력값은 다음과 같다.

fib(50) = 12586269025, 실행시간: 187.704초
fib(0)의 호출 횟수: 7778742049회
fib(1)의 호출 횟수: 12586269025회
fib(2)의 호출 횟수: 7778742049회
fib(3)의 호출 횟수: 4807526976회
fib(4)의 호출 횟수: 2971215073회
fib(5)의 호출 횟수: 1836311903회
fib(6)의 호출 횟수: 1134903170회
fib(7)의 호출 횟수: 701408733회
fib(8)의 호출 횟수: 433494437회
fib(9)의 호출 횟수: 267914296회
fib(10)의 호출 횟수: 165580141회
fib(11)의 호출 횟수: 102334155회
fib(12)의 호출 횟수: 63245986회
fib(13)의 호출 횟수: 39088169회
fib(14)의 호출 횟수: 24157817회
fib(15)의 호출 횟수: 14930352회
fib(16)의 호출 횟수: 9227465회
fib(17)의 호출 횟수: 5702887회
fib(18)의 호출 횟수: 3524578회
fib(19)의 호출 횟수: 2178309회
fib(20)의 호출 횟수: 1346269회
fib(21)의 호출 횟수: 832040회
fib(22)의 호출 횟수: 514229회
fib(23)의 호출 횟수: 317811회
fib(24)의 호출 횟수: 196418회
fib(25)의 호출 횟수: 121393회
fib(26)의 호출 횟수: 75025회
fib(27)의 호출 횟수: 46368회
fib(28)의 호출 횟수: 28657회
fib(29)의 호출 횟수: 17711회
fib(30)의 호출 횟수: 10946회
fib(31)의 호출 횟수: 6765회
fib(32)의 호출 횟수: 4181회
fib(33)의 호출 횟수: 2584회
fib(34)의 호출 횟수: 1597회
fib(35)의 호출 횟수: 987회
fib(36)의 호출 횟수: 610회
fib(37)의 호출 횟수: 377회
fib(38)의 호출 횟수: 233회
fib(39)의 호출 횟수: 144회
fib(40)의 호출 횟수: 89회
fib(41)의 호출 횟수: 55회
fib(42)의 호출 횟수: 34회
fib(43)의 호출 횟수: 21회
fib(44)의 호출 횟수: 13회
fib(45)의 호출 횟수: 8회
fib(46)의 호출 횟수: 5회
fib(47)의 호출 횟수: 3회
fib(48)의 호출 횟수: 2회
fib(49)의 호출 횟수: 1회
fib(50)의 호출 횟수: 1회

실행시간도 약 3분정도 소요됐을뿐더러 fib(2)는 무려 7,778,742,049회 호출됐다. 아래는 dp를 사용한 코드이다.

#include <stdio.h>
#include <time.h>
long long int cnt[51], dp[51];
long long int fib(int n) {
	cnt[n]++;
	if (dp[n] == -1) {
		dp[n] = fib(n - 1) + fib(n - 2);
	}
	return dp[n];
}
main() {
	int start = clock();
	dp[0] = 0;
	dp[1] = 1;
	for (int i = 2; i <= 50; i++) {
		dp[i] = -1;
	}
	printf("fib(50) = %lld, ", fib(50));
	int stop = clock();
	double duration = (double)(stop - start) / CLOCKS_PER_SEC;
	printf("실행시간: %g초\n", duration);
	for (int i = 0; i <= 50; i++) {
		printf("fib(%d)의 호출 횟수: %lld회\n", i, cnt[i]);
	}
}

이 코드를 실행했을 때 출력값은 다음과 같다.

fib(50) = 12586269025, 실행시간: 0초
fib(0)의 호출 횟수: 1회
fib(1)의 호출 횟수: 2회
fib(2)의 호출 횟수: 2회
fib(3)의 호출 횟수: 2회
fib(4)의 호출 횟수: 2회
fib(5)의 호출 횟수: 2회
fib(6)의 호출 횟수: 2회
fib(7)의 호출 횟수: 2회
fib(8)의 호출 횟수: 2회
fib(9)의 호출 횟수: 2회
fib(10)의 호출 횟수: 2회
fib(11)의 호출 횟수: 2회
fib(12)의 호출 횟수: 2회
fib(13)의 호출 횟수: 2회
fib(14)의 호출 횟수: 2회
fib(15)의 호출 횟수: 2회
fib(16)의 호출 횟수: 2회
fib(17)의 호출 횟수: 2회
fib(18)의 호출 횟수: 2회
fib(19)의 호출 횟수: 2회
fib(20)의 호출 횟수: 2회
fib(21)의 호출 횟수: 2회
fib(22)의 호출 횟수: 2회
fib(23)의 호출 횟수: 2회
fib(24)의 호출 횟수: 2회
fib(25)의 호출 횟수: 2회
fib(26)의 호출 횟수: 2회
fib(27)의 호출 횟수: 2회
fib(28)의 호출 횟수: 2회
fib(29)의 호출 횟수: 2회
fib(30)의 호출 횟수: 2회
fib(31)의 호출 횟수: 2회
fib(32)의 호출 횟수: 2회
fib(33)의 호출 횟수: 2회
fib(34)의 호출 횟수: 2회
fib(35)의 호출 횟수: 2회
fib(36)의 호출 횟수: 2회
fib(37)의 호출 횟수: 2회
fib(38)의 호출 횟수: 2회
fib(39)의 호출 횟수: 2회
fib(40)의 호출 횟수: 2회
fib(41)의 호출 횟수: 2회
fib(42)의 호출 횟수: 2회
fib(43)의 호출 횟수: 2회
fib(44)의 호출 횟수: 2회
fib(45)의 호출 횟수: 2회
fib(46)의 호출 횟수: 2회
fib(47)의 호출 횟수: 2회
fib(48)의 호출 횟수: 2회
fib(49)의 호출 횟수: 1회
fib(50)의 호출 횟수: 1회

물론 프로그램을 실행하는 컴퓨터의 성능을 비롯한 여러 가지 조건에 따라 실행시간은 다르게 나오겠지만 실행시간을 비롯한 각 함수의 호출 횟수 모두 확연히 줄어든 것을 확인할 수 있다.

또한 dp는 위와 같은 재귀(Top-Down)를 사용한 방법과 반복문(Bottom-Up)을 사용한 방법이 있다.

#include <stdio.h>
#include <time.h>
long long int fib(int n) {
	long long int n2 = 0, n1 = 1, n0;
	for (int i = 2; i <= n; i++) {
		n0 = n1 + n2;
		n2 = n1;
		n1 = n0;
	}
	return n0;
}
main() {
	int start = clock();
	printf("fib(50) = %lld, ", fib(50));
	int stop = clock();
	double duration = (double)(stop - start) / CLOCKS_PER_SEC;
	printf("실행시간: %g초\n", duration);
}

이 코드에서의 n0은 탑다운 방식에서의 fib(n)을, n1은 fib(n -1), n2는 fib(n - 2)를 의미하며 출력값은 다음과 같다.

fib(50) = 12586269025, 실행시간: 0초