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

도입

동적 계획법을 처음 듣는 사람은 다소 오해를 할 수 있다.

필자 또한 처음 동적 계획법 특히 영어로 dynamic programming을 봤을 때, 'heap 영역을 다루는 기법인가?'라고 생각했다.

일반적으로 우리가 사용하는 "dynamic"이나 "programming"라는 단어엔 아무련 관련이 없다.

 

그렇다면 무엇을 동적 계획법이라 할까?

 

중복되는 부분 문제

동적 계획법은 크게 보면 분할 정복과 같다고 볼 수 있다.

동적 계획법을 사용하는 알고리즘들은 큰 문제를 작은 문제로 나눠 푸는 데 사용되는데,

분할 정복과 다른 점은 한번 계산한 결과를 재이용한다는 것이다.

 

백문이불여일견이라고 예시를 통해 이해해보자.

 

예제 - 이항 계수 

우리는 점화식을 통해 다음과 같이 이항 계수를 구할 수 있다.

//점화식을 이용한 이항계수 구하기
int bino(int n, int r)
{
	//base case
	if (r == 0 || n == r) return 1;
	return bino(n - 1, r - 1) + bino(n - 1, r);
}

bino(4,2)를 계산하는 과정을 그림으로 표현하면 다음과 같다.

위 그림을 보면 알 수 있듯이, 겹치는 부분이 발생하게 된다.

n과 r의 크기가 커질수록 함수 호출이 기하급수적으로 늘어나게 된다.

 

Memoization

중복을 제거하는 방법으로, 한 번 계산한 값을 저장해 뒀다 재활용하면 된다.

이를 메모이제이션(memoization)이라 한다.

int cache[30][30] = { -1 };
int bino(int n, int r)
{
	//base case
	if (r == 0 || n == r) return 1;
	//한 번 계산된 경우
	if (cache[n][r] != -1) return cache[n][r];
	return cache[n][r] = bino(n - 1, r - 1) + bino(n - 1, r);
}

이와 같은 방식을 이용해 최적화하는 과정을 동적 계획법이라 한다.

 

 적용할 수 있는 경우

함수의 반환 값이 그 입력 값만으로 결정되는 경우에만 사용할 수 있다.

이를 referential transparent function(참조적 투명 함수)라고 한다.

 

 구현 패턴

앞으로 종만북에서 소개한 대로 구현할 예정이다.

//전부 -1로 초기화해 둔다.
int cache[2500][2500];
// a와 b는 (0, 2500] 구간 내 정수
// 반환 값은 크기는 int, 음이 아닌 정수
int someObsureFunction(int a, int b)
{
	//base case를 항상 먼저 처리해준다.
	if (..) return ...;
	// (a, b)를 구한 적이 있으면 곧장 반환
	int& ret = cache[a][b]; // index 혼동 방지, 매번 a,b 를 써줄 필요가 없다.
	if (ret != -1) return ...;
	//여기에 답을 계산한다.
	...
	return ret;
}

int main()
{
	//memset()을 이용해 cache배열을 -1로 초기화 해준다.
	memset(cache, -1, sizeof(cache));
	return 0;
}

※ memset()은 매우 한정된 상황에서만 사용할 수 있다. (초기화하는 수가 0, -1이거나 자료형이 int형인 경우)

초기화 관련해서 추가 참고 사항 :

2021/01/05 - [알고리즘 문제 해결 전략] - 동적 계획법 - 12. 폴리오미노 & 메모이제이션

동적 계획법 - 12. 폴리오미노 & 메모이제이션

 

 시간 복잡도

시간 복잡도를 계산이 다소 복잡하다고 생각할 수 있지만, 간단하게 계산할 수 있는 방법이 있다.

 

(존재하는 부분 문제의 수) X (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)

 

메모이제이션을 적용한 bino() 함수의 시간 복잡도를 구하면 다음과 같다.

 

부분 문제의 최대 수 : O(n^2) ; n^2 ( r = n )

부분 문제를 풀 때  : O(1) ; 반복문이 필요 없다.

 

따라서 O(n^2)xO(1) = O(n^2) 이다.

 

최적화 문제 동적 계획법 레시피

 

1. 모든 답을 만들어 보고 그중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계한다.

2. 전체가 아닌 부분을 반환하도록 부분 문제 정의로 바꾼다.

3. 재귀 과정에서 최대한 중복되는 것을 없애고 메모이제이션 활용을 최대로 한다.

4. 입력이 배열 또는 문자열인 경우 적절한 변환을 통해 메모이제이션을 할 수 있도록 한다.

5. 메모이제이션을 활용한다.