[알고리즘] 동적 계획법(DP, Dynamic Programming)

동적 계획법이란?

재귀(再歸)라고 하는 수학적 개념에 기초를 두고 「최적성의 원리」에 따라 다단계의 결정과정을 취급하는 것이며 최대의 목재생산을 위한 간벌계획문제를 비롯해서 각종의 배분문제, 재고문제, 경제문제 등의 여러 가지 결정문제에 유용하게 쓰인다.
[네이버 지식백과] 동태계획법 [dynamic programming, 動態計劃法] (산림임업 용어사전)

어떤 문제의 해결 과정을 간략화하기 위해, 즉 최적화를 위해 복잡한 문제를 여러 개의 간단한 문제로 나누어 해결하는 방법이다. 1010: 다리 놓기나 4948: 베르트랑 공준이 동적 계획법을 사용해 문제를 해결할 수 있는 예이다.

다이나믹 프로그래밍이라는 용어는 꽤 어려워 보일수도 있다. 근데 용어에는 큰 의미는 없다고 한다. 강의 시간에 교수님께서 좀 있어보이는 이름을 지은 것 뿐이라고 말씀하신 게 떠오른다.

int fib(int n)
{
	if (n == 1 || n == 2)
    	return 1;
    else
    	return fib(n-2) + fib(n-1);
}

예를 들어 위 함수는 피보나치 숫자를 구하는 재귀 함수이다. n이 1 또는 2가 될 때까지 재귀 호출을 반복하고 있다.
피보나치 수열의 순환식은 $n>2$일 때 $f(n)=f(n-1)+f(n-2)$로 표현된다. 다음 피보나치 수를 구하기 위해선 이전의 피보나치 수를 알아야 한다.

그러나 위 코드는 굉장히 비효율적으로 짜여진 코드이다.

함수의 실행 과정을 자세히 살펴보면 계산 과정에서 많은 계산이 중복으로 발생하고 있기 때문이다.

예를 들어 $f(7)$을 구하고자 하면
$f(7) =$$f(6)$$+$ $f(5)$ 이다. 이를 또 재귀 호출하면
$f(7) =$$f(5)+f(4)$$+$$f(4)+f(3)$ 이다.

2번째 재귀 호출에서부터 $f(4)$의 계산이 중복되고 있다.

어떻게 하면 실행시간을 최적화할 수 있을까? 계산을 중복으로 하는 것이 문제라면 컴퓨터에서 캐싱을 사용하는 것처럼 계산 결과를 캐싱해서 저장해 두고 사용하면 된다. 이처럼 중간 계산 결과를 저장해 두고 반복수행을 줄이는 방법을 메모이제이션(Memoization)이라고 한다.

1. Memoization 방법

int fib(int n)
{
	if (n==1 || n==2)
		return 1;
	else if (f[n] > -1) /* 배열 f가 -1으로 초기화되어 있다고 가정 */
		return f[n]; /* 즉 이미 계산된 값이라는 의미 */
	else {
		f[n] = fib(n-2) + fib(n-1); /* 중간 계산 결과를 caching */
		return f[n];
	}
}

메모이제이션도 동적 계획법의 일종으로 보기도 한다. 메모이제이션과 동적 계획법은 유사한 작동 방식을 가진다. 그러나 메모이제이션은 top-down 방식이며 재귀 호출이 동반되기에 아무리 캐싱을 한다고 하더라도 이로 인한 오버헤드가 발생할 수밖에 없다.

그에 반해 bottom-up 방식의 동적 계획법은 기본적으로는 재귀 수행에 기반을 두지만 재귀적으로 수행하지 않으며 이로 인한 오버헤드가 없다는 특징이 있다.

(참고) Bottom–up and top–down design

2. bottom-up 방식의 Dynamic programming

int fib(int n)
{
	f[1] = f[2] = 1;
	for (int i=3; i<=n; i++)
		f[i] = f[i-1] + f[i-2];
	return f[n];
}

for문에서 값을 순서대로 계산해 놓으면 뒤의 값을 바로 계산할 수 있다. bottom-up 방식을 사용한다는 것은 순환식에서 우변의 값이 좌변의 값보다 먼저 계산되어 있어야 한다는 것이다.

참고자료
동적계획법 (Dynamic Programming) / https://youtu.be/K15qLnKKrow