동적 계획법::메모이제이션

동적 계획법이란::

문제를 같은 해법을 가지는 재귀적인 덩어리로 분할 해서 각각 분할된 부분 문제들을 해결하고

 

이를 합쳐나가며 전체의 해를 찾는 풀이법을 말한다. 완전 탐색과 다른 점은 이미 계산된 해를 계산하지 않는다는 점이다.

 

이 때, 나눠진 부분 문제들이 같은 문제 일 경우, 의미없는 중복계산이 발생되어 코드가 느려진다.

 

메모이제이션은 각각의 부분문제들의 대한 해법을 따로 테이블에 계산해놓고 같은 부분 문제가 나올 경우,

 

그 해를 사용하는 알고리즘 기법이다.

 

이를 통해서 중복된 계산을 피하고 백트래킹으로는 답을 구하기 힘든 문제들을 비교적 쉽게 계산 할 수 있다.

 

중복 계산을 소거하기 위해서 사용되는 대표적인 기법이다.

 

부분 문제에 대한 해를 구했을 경우 그 해를 저장해놓고 이 후, 풀이과정에서 같은부분 문제가 다시 제기 되었을 경우, 

 

저장된 해를 사용하므로써 중복 계산을 피한다.

 

아래코드는 피보나치를 구하는 bottom-up 방식의 재귀호출이다.

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

이 코드의 동작과정을 복기하며 문제점을 찾아보자.

fibo(6)

fibo(5) + fibo(4)

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

fibo(3) + fibo(2)   fibo(2) + fibo(1)  fibo(2) + fibo(1)  fibo(1) + fibo(0)

fibo(2) + fibo(1)   fibo(1) + fibo(0)   fibo(1) + fibo(0)

아래와 같이 각 층마다 호출 될 것이다. 이 때, fibo(4), fibo(3), fibo(2)의 중복된 호출은 필요없는 계산들이다.

 

따라서 아래와 같이 최적화가 가능하다.

dp[0] = 1;
dp[1] = 1;
int memoization[100] = { -1, };
int fibo(int n) {
	 if(n <= 1) return 1;
     if(memoization[n] != -1) return memoization[n];
     return memoization[n] = fibo(n - 1) + fibo(n - 2);
}

memoization 배열에 n번째 피보나치수를 저장해놓고 그 값이 있다면 추가적인 호출을 하지 않도록 한다.

 

메모이제이션은 동적 계획법의 핵심이 되는 기법으로 PS를 할 때에도 이 기법을 어디에 적용할지 항상 고민하며 

 

풀이해야한다.