동적 계획법(Dynamic Programming)이란 무엇인가?

DP(동적계획법)란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.

두 가지 방법으로 문제를 해결할 수 있는데,

• Top-down은 가장 큰 문제를 나누어 작은 문제를 호출해 답을 찾는 방식이고
• Bottom-up은 가장 작은 문제들 부터 답을 구해가며 전체 문제의 답을 찾는 방식이다.

---

Top-down 방식은 재귀함수를 이용해 구현한다.

예를 들어, 피보나치 함수를

 f(n) = f(n-1) + f(n-2), f(1) = 1, f(2) = 1

위와 같은 점화식으로 세웠을 때 Top-down 방식으로 코드를 구현하면 다음과 같다.

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

 

하지만 이처럼 재귀로 구현할 경우 f(6)의 값을 구하기 위해 f(5)의 값과 f(4)의 값이 필요하며, f(5)는 또 다시 f(4)의 값을 필요로한다.

중복되어 호출되는 값이 많다.

이러한 상황에서 구해야 하는 값이 중복되는 경우 이미 구해놓은 값을 사용하는 방법을 메모이제이션(Memoization)이라고한다.

Top-down 방식은 메모이제이션(Memoization)을 사용하여 연산 횟수를 줄이는 것이 중요하다.

메모리제이션(X)이 아니라 메모이제이션(O)이 맞는 표현이니 헷갈리지 않도록하자.

(메모리를 사용하긴 하나 메모한다는 의미에 중점을 둔 단어이다.)

코드로 구현하면 다음과 같다.

int dt[10]; // 메모이제이션을 위한 배열
int f(int n)
{
	if(n <= 2) return 1;
	if(dt[n] != 0) return dt[n]; // f(n)의 값이 계산되어있다면 그 값을 리턴
	else return dt[n] = f(n-1) + f(n-2); // 계산되어있지 않은경우 점화식 값을 계산
}

---

Bottom-up 방식은 주로 반복문을 사용해 구현한다.

Top-down 방식에서 사용한 피보나치 함수를 Bottom-up 으로 구현하면 다음과 같다.

int f[10];
f[1] = 1;
f[2] = 1;
for(int i = 3 ; i <= 6 ; i++)
{
	f[i] = f[i-1] + f[i-2];
}

Bottom-up 방식을 사용하면 f(6) 값을 구하기 위해 불필요한 연산이 수행되지 않는다.

Bottom-up 방식에서 앞의 함수 값을 미리 구해놓는 방법을 타뷸레이션(Tabulation) 이라고 한다.

 

이미지 출처 : https://medium.com/@nkhaja/memoization-and-decorators-with-python-32f607439f84