DP(Dynamic Programming, 동적 계획법) 개념과 메모이제이션

동적계획법(Dynamic Programming)

동적계획법(Dynamic Programming)이라는 것은 알고리즘에서 아주 자주 등장하는 주제입니다. 줄여서 DP라고도 부릅니다.

DP의 특징은 어떤 부분 문제는 두 개 이상의 문제를 푸는 데 사용될 수 있습니다. 그래서 "답을 여러 번 계산하는 대신 한번 만 계산한다!" 입니다.  

개인적으로 DP를 보면 항상 먼저 떠오르는게 바로 재활용이라고 생각합니다. 재활용을 통해서 속도를 빠르게 향상 시킬 수 있는 방법입니다.

어떻게 재활용을 할 수 있을까요? 가장 유명한 피보나치 수열을 한 번 보도록 해봅시다. 피보나치의 정의는 아래와 같습니다. 간단합니다.

이 피보나치 수열을 재귀함수로 정의해보겠습니다. 

int fibo(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	return fibo(n - 1) + fibo(n - 2);
}

이런식으로 정의가 될 것 같네요. 여기서 n은 무조건 양수라고 가정하겠습니다. 음수는 귀찮습니다. 만약 fibo(5)라는 값을 계산하려면 어떤 과정을 거칠까요?

fibo(5) = fibo(4) + fibo(3) 라는 것을 알 수 있고 이제 fibo(4)와 fibo(3)을 더해주기만 하면 됩니다.

그럼 왼쪽 fibo(4)부터 차근 차근히 계산을 해보도록 하겠습니다. 노가다로 해보겠습니다.

fibo(4) = fibo(3) + fibo(2) 

이것도 역시 fibo(3), fibo(2)를 계산해야 되겠군요

fibo(3) = fibo(2) + fibo(1) 이 되겠습니다.

fibo(2) = fibo(1) + fibo(0) 이 되어서 fibo(2) = 1이라는 것을 알게 됩니다.

그렇다면 fibo(3) = fibo(2) + fibo(1) 이니까 1+1 해서 fibo(3) = 2라는 것을 알 수 있겠네요.

fibo(4) = fibo(3) + fibo(2) 랍니다. 여러 분, 이제 슬슬 감이 오고 있나요? 노가다 하기 싫습니다.

fibo(4) = 2 + fibo(2)라는 것이 됩니다. fibo(3)을 방금전에 계산했거든요. 그러면 오른쪽 fibo(2)를 구해보도록 합시다.

fibo(2) = fibo(1) + fibo(0) 으로 fibo(2)=1입니다.

그럼 fibo(4) = 2+ 1 = 3 이라는 결과가 나옵니다. 이제 fibo(4) 구한 겁니다.

이제 fibo(3)을 구해볼까요?

이제 손가락이 아파서 못할 거 같고요

fibo(3) 뭐라고 했지요? 아까 계산했는데 말입니다.

2가 나왔죠?

이 같은 노가다를 막기 위한 것이 바로 DP의 큰 역할이라고 할 수 있겠습니다. 만약 위의 저 코드를 통해서 fibo(40)을 계산한다면 얼마나 걸릴까요? 아마 계산했던 결과를 또 계산하고 앉아있으니 오래 걸릴거라는 걸 짐작할 수 있나요?

네, 오래 걸립니다. 우리는 이제 계산된 값을 재활용 합시다. 이렇게요.

int dp[50];
int fibo(int n) {
	
	if (n == 0) return 0;
	if (n == 1) return 1;
	if (dp[n] != -1) return dp[n];
	return dp[n] = (fibo(n - 1) + fibo(n - 2));
}
int main() {
	memset(dp, -1, sizeof(dp));
	printf("fibo(40)=%d\n", fibo(40));
}

어떻습니까? 맨 처음 초기화값은 -1입니다. memset함수에 주목합시다. 이 함수는 dp라는 배열을 -1이라는 값으로 전부 초기화 시키는 역할을 하는 것이랍니다. 처음 계산하는 값이라면 dp[n]에 -1이라는 값이 들어있을 겁니다. 그렇지 않을까요? 이해 되십니까?

그리고 다음에 같은 값을 계산할때, 즉 또 같은 짓거리할 때 그때는 -1이라는 값이 아닌 0이나 1이상의 값이 들어있을 겁니다. 피보나치는 음수가 나올 수 없으니까요. 그렇단 얘기는, 즉 dp[n] != -1이라는 얘기는 앞 전에 이미 한번 계산이 된 값이니까 그냥 dp[n]을 바로 반환해버리면 fibo(n-1)과 fibo(n-2)를 더 이상 호출하지 않으니 시간을 절약할 수 있다는 이야기랍니다. 이미 계산된 결과를 재활용하는 것이죠.

★우리는 dp[n]을 이용하여 재활용합니다. 그러니까 dp[n]은 fibo(n)의 결과를 기억하고 있는 겁니다. 이것을 메모이제이션(memoization) 이라고 합니다. 메모이제이션! 기억해두세요. 여러모로 쓸일이 많을 겁니다.

맨 처음 코드와 dp를 적용한 코드를 한 번 실행시켜보고 비교해보세요. 차이가 확연히 드러날 겁니다.

DP는 그럼 어디에 쓰일까요? 동전 교환 알고리즘, 냅색 알고리즘 등 쓰임새는 아주 유용합니다. DP는 recursive(재귀적) 뿐만 아니라 iterative(반복적)하게도 사용될 수 있습니다. dp에 관한 기본적인 이론을 쉽게 풀어내느라고 좀 횡설수설한 거 같기도 합니다. 부족한글 읽어주셔서 감사합니다. 다음에는 본격적인 문제를 풀어보도록 합시다.