[알고리즘] 동적 계획법, 메모이제이션이란?

 

동적 계획법 중 메모이제이션을 적용하는 문제들이 참 많았는데, 

무슨 소리인지 제대로 이해하지 못했다.

그래서 오늘 각잡고 조사해보았다. ^_^

 

 

 

 

 

1. 동적 계획법이란?

 

  동적 계획법 (dynamic programming): 처음 주어진 문제들을 분할하고, 이로부터 본 문제에 관한 답을 도출하는 접근 방법이다. 특히 부분 문제들의 수가 기하급수적으로 증가할 때 유용하다. 동적 계획법은 여러 문제 해결에 사용되는 부분 문제에 대한 결과를 여러번 계산하는 대신, 한 번만 계산하고 이를 재활용하여 속도를 향상시킨다는 점에서 분할 정복법과 차이가 있다. 이를 위하여 각 문제의 답을 메모리에 저장해야 하는데, 이미 계산된 값을 저장해두는 메모리의 장소를 캐시(cache)라고 하며, 두 번 이상 계산되는 부분 문제를 중복되는 부분문제라고 부른다. 

 

 

 

- 각 부분 문제들이 서로 연관이 없을 때

-> 단순한 재귀 호출로 문제 해결

-> 분할 정복법

 

- But 나눠진 문제들이 같은 부분 문제들에 중복되어 의존할 때

-> 분할의 깊이가 깊어질수록 중복 횟수 지수적 증가 (조합 폭발)

-> 이를 해결하기 위하여 고안된 알고리즘 : 동적 계획법

 

 

 

 

 

2. 메모이제이션(memoization)이란?

 

 - 함수의 결과를 저장하는 장소를 마련해두고, 한 번 계산한 값을 저장하여 재활용하는 최적화 기법

 - 동일한 계산을 반복해야 할 경우, 메모이제이션을 통하여 중복 계산을 방지할 수 있다.

 - 메모리라는 공간 비용을 투입하여, 계산에 소요되는 시간 비용을 줄이는 방식이다. 

 

 

 

 

 

3. 메모이제이션의 활용

 

// 재귀 호출을 통한 이항 계수의 계산

int bino(int n, int r) {
	if (r == 0 || n == r) {
		return 1;
		// 기저 사례
	}
	else {
		return bino(n - 1, r - 1) + bino(n - 1, r);
		// 함수의 중복 호출 횟수는 n과 r이 증가함에 따라 기하급수적으로 증가
	}
}


// 메모이제이션을 통한 이항 계수의 계산

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

	if (cache[n][r] != -1) {
		return cache[n][r];
		// -1이 아니라면 이미 계산된 값이 있다는 뜻!
	}

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

 

 

 

// 귀엽고 재미있는 달팽이 문제에서도 cache를 찾아볼 수 있다! :)


int n = 0;
int m = 0;
int cache [MAX_N] [2 * MAX_N + 1];

int climb(int days, int climbed) {
	if (days == m) {
		return climbed >= n ? 1 : 0;
	}

	int& ret = cache[days][climbed];
	if (ret != -1) {
		return ret;
	}
	
	ret = climb(days + 1, climbed + 1) + climb(days + 1, climbed + 2);
	return ret;
}


// 장마가 찾아왔다!
// 여름 장마로 인해 비가 올 확률이 50% -> 75%

int climb2(int days, int climbed) {
	if (days == m) {
		return climbed >= n ? 1 : 0;
	}

	int& ret = cache[days][climbed];
	if (ret != -1) {
		return ret;
	}

	ret = 0.25*climb2(days + 1, climbed + 1) + 0.75*climb2(days + 1, climbed + 2);
	return ret; // 경우의 수가 아닌, 확률을 return 한다. 
}

 

 

 

 

 

4. 최적 부분 구조 (optimal substructure)

 

- 효율적인 동적 계획법 알고리즘을 적용하기 위하여 아주 중요한 조건이다. 

- 최적 부분 구조가 성립할 경우, 각 부분 문제의 최적해만으로 전체 문제의 최적해를 쉽게 구할 수 있다. 

- 지금까지의 선택과 무관하게 각 부분 문제를 최적으로 풀기만 하면, 전체 문제의 최적해도 알 수 있다. 

- 많은 문제에서 최적 부분 구조는 직관적으로 이해할 수 있다. 증명이 필요할 경우 귀류법, 혹은 대우를 활용한다. 

 

 

 ex) 서울에서 부산으로 가는 최단 경로가 대전을 지난다. 

해당 경로를 (서울, 대전), (대전, 부산)으로 나눌 때, 각각의 최단 경로를 얻으면 전체 경로의 최단 경로를 찾을 수 있다. 

이와 같이 각 부분 문제의 최적해가 전체 문제의 최척해로 이어질 때, 이를 최적 부분 구조를 갖는다고 한다. 

 

 

 

 

5. 최적화 문제 동적 계획법 TIP

 

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

2. 전체 문제의 최적해를 반환하지 않고, 앞으로 남은 선택들에 해당하는 답을 반환하도록 부분 문제의 정의를 변환한다.

3. 재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면, 꼭 필요한 것만 남기고 줄인다. 

- 가능한 한 중복되는 부분 문제를 많이 만든다. 입력의 종류가 줄어들수록 더 많은 부분 문제가 중복되고, 메모이제이션을 최대한 효율적으로 적용할 수 있다. 

4. 입력이 배열이거나 문자열이라면, 적절한 변환을 통하여 메모이제이션 할 수 있도록 한다. 

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

 

 

 

 

 

 

출처: 

- 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (구종만)

- https://namu.wiki/w/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

- https://ssminji.github.io/2020/02/05/the-cake-thief/

- https://kamang-it.tistory.com/entry/AlgorithmDynamic-Programming%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%EA%B3%BC-%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98memoization-%ED%83%80%EB%B7%B8%EB%A0%88%EC%9D%B4%EC%85%98tabulation