[8] 동적 계획법

[동적 계획법]

 - 큰 의미에서 분할 정복과 같은 접근 방식

 - 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에, 이 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함으로써 속도의 향상을 꾀할 수 있다.

-> 각 문제의 답을 메모리(캐시)에 저장해 둘 필요가 있다! 왜냐하면 중복 호출이 기하급수적으로 증가하기 때문에 계산량의 낭비를 피하기 위해!

    반환 값이 일정하다는 사실을 이용하면 답을 저장하는 캐시 배열을 만들어서 각 입력에 대한 반환 값을 저장할 수 있다.

 

이와 같이 함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법을 메모이제이션이라고 한다.

//-1로 초기화해 둔다.
int cache[30][30];
int bino2(int n, int r){
//기저사례
if(r==0 || n==r) return 1;

//-1이 아니라면 한 번 계산했던 값이니 곧장 반환
if(chche[n][r] != -1)
  return cache[n][r];

return cache[n][r] = bino2(n-1, r-1) + bino2(n-1, r);
}

(메모이제이션을 사용하면 모든 부분 문제가 한 번씩만 계산된다고 보장할 수 있기 때문에 함수 호출 횟수가 엄청나게 감소하리라 예상할 수 있다!)

 

*메모이제이션은 함수의 반환 값이 그 입력 값만으로 결정될 때만 사용가능하다. -> 입력이 같은데 외부 요소에 따라 다른 값이 반환된다면 캐싱 X

 

 

[메모이제이션 구현 패턴]

 

1. 항상 기저 사례를 제일 먼저 처리한다. 

   입력이 범위를 벗어난 경우 등을 기저 사례로 처리하면 매우 유용한데, 기저 사례를 먼저 확인하지 않고 cache[]에 접근하면 범위를 벗어나는 등의       오류가 있을 수 있다.

 

2. 함수의 반환 값이 항상 0 이상이라는 점을 이용해라.

   cache[]를 모두 -1로 초기화하면 -1일 경우 이 값은 계산된 반환 값일리가 없다!

 

3. ret가 cache[a][b]에 대한 참조형이라는데 유의해라.

   참조형 ret의 값을 바꾸면 cache값도 변하기 때문에 저장할 때도 매번 귀찮게 cache라고 쓸 필요가 없어진다.

 

4. memset()을 이용해 cache[]를 초기화해라.

   다중 for문보다 쉽게 초기화할 수 있다!(하지만 굉장히 제한적인 경우에만 쓸 수 있는 일이다. 만약 배열이 32비트나 64비트 정수형일 때는 X)

 

코드 8.3 메모이제이션의 사용 예

//전부 -1로 초기화해 둔다.
int cache[2500][2500];
//반환 값은 항상 int형 안에 들어가는 음이 아닌 정수
int function(int a, int b) {
	//기저 사례를 처음에 처리!
	if (..)	return ..;
	//(a,b)에 대한 값을 구한 적이 있으면 곧장 반환
	int& ret = cache[a][b];
	if (ret != -1)	return ret;
	//여기에서 답 계산
	..
		return ret;
}

int main() {
	memset(cache, -1, sizeof(cache));
}