[종만북] 8장 동적 계획법

종만북 8장 동적 계획법

이 포스팅은 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략>, 구종만, 인사이트(2012)을 읽고 개인 학습용으로 정리한 글입니다.

➖ 21-07-04

도입

동적 계획법(dynamic programming)

• 동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다
  동적 계획법은 문제를 나누는 방식에서 분할 정복과 차이가 있다

• 중복되는 부분 문제(overlapping subproblems) 발생 -> 계산 결과를 캐시(cache)메모리에 저장하여 재활용 -> 속도 향상
  = 메모이제이션 기법(memoization)

이항 계수(binomial co-efficient) 문제

• 재귀 호출을 이용한 이항 계수의 계산
  -> 같은 값을 두 번 이상 계산할 일이 빈번하다

	int bino(int n, int r){
		if(r == 0 || n == r) return 1;
		return bino(n-1, r-1) + bino(n-1, r);
	}

• 메모이제이션을 이용한 이항 계수의 계산
  -> 모든 부분 문제가 한 번씩만 계산된다

	//캐시 -1로 초기화해 둔다
	int cache[30][30];

	int bino2(int n, int r){
		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 transparency)
  : 함수의 반환값이 그 함수의 입력값으로만 결정되는 특성

• 참조적 투명 함수(referential transparent function)
  : 입력이 고정되어 있을 때 결과가 항상 같은 함수들

• 메모이제이션은 참조적 투명 함수의 경우에만 적용할 수 있다

메모이제이션 구현 패턴

• 항상 기저 사례(base case)를 제일 먼저 처리

• cache[]를 모두 -1로 초기화
  -> 만약 함수의 반환값이 음수일 수도 있다면 다른 값을 사용해야한다
  -> memset()을 이용해 cache[] 초기화하는 방법은 매우 제한적인 경우에만 가능하다

• ret은 cache[a][b]에 대한 참조형(reference)

//a, b는 각각 [0, 2500) 구간 안의 정수
//반환 값은 항상 int형 안에 들어가는 음이 아닌 정수
int someObscureFunction(int a, int b);

//캐시 -1로 초기화해 둔다
int cache[2500][2500];

int someObscureFunction(int a, int b){
	//기저 사례 제일 먼저 처리
	if(...) return ...;

	//(a, b)에 대한 답을 구한 적이 있으면 곧장 반환
	int &ret = cache[a][b];
	if(ret != -1) return ret;

	//(a, b)에 대한 답 계산
	...
	return ret;
}

int main(){
	//memset()을 이용해 cache배열 초기화
	memset(cache, -1, sizeof(cache));
}

메모이제이션의 시간 복잡도 계산

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

동적 계획법 레시피

1. 주어진 문제를 완전 탐색을 이용해 해결

2. 중복된 부분 문제를 한 번만 계산하도록 메모이제이션 적용

• 재귀 호출을 이용하지 않고 동적 계획법 알고리즘 구현 가능
  -> 반복적 동적 계획법
  -> 그러나 재귀 호출 & 메모이제이션을 이용하면 더 직관적으로 구현 가능

전통적 최적화 문제들

• 동적 계획법의 가장 일반적인 사용처: 최적화 문제의 해결

• 최적 부분 구조(optimal structure)
  : 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 얻어낼 수 있는 경우 성립하는 조건

최대 증가 부분 수열(LIS)

• 포함된 숫자들이 순증가(strictly increasing)하는 부분 수열
  = 증가 부분 수열

• 증가 부분 수열 중 가장 긴 증가 부분 수열
  = 최대 증가 부분 수열(LIS, Longest increasing Sebsequence)

• 최대 증가 부분 수열(LIS)찾기 문제
  : 주어진 수열에서 얻을 수 있는 증가 부분 수열 중 가장 긴 것을 찾는 문제

• lis(S): 수열 S를 입력받아 LIS의 길이를 반환하는 재귀함수
  -> 입력이 정수의 배열 -> 메모이제이션 까다롭다

	int lis(const vector<int>& S){
		//base case
		if(S.empty()) return 0;
	
		int ret = 0;
		for(int i = 0; i< S.size(); ++i){
			vector<int> smallS;
			for(int j = i+1; j< S.size(); ++j)
              if(S[i] < S[j]) smallS.push_back(S[j]);
			ret = max(ret, 1 + lis(smallS));
		}
		return ret;
	}

• lis2(start): S[start]에서 시작하는 부분 증가 수열 중 최대 길이 반환
  -> 별도의 기저 사례 필요하지 않다

	int n;
	int cache[100], S[100];

	int lis2(int start){
		//lis2(start)에 대한 답을 구한 적이 있으면 곧장 반환
		int& ret = cache[start];
		if(ret != -1) return ret;

		//lis2(start)에 대한 답 계산
		//항상 S[start]는 있기 때문에 길이는 최하 1
		ret = 1; 
		for(int next = start+1; next < n; ++next)
			if(S[start] < S[next])
				ret = max(ret, 1 + lis2(next));

		return ret;
	}

	int maxLen = 0;
	for(int begin = 0; begin < n; ++begin)
		maxLen = max(maxLen, lis2(begin));

• lis2()를 호출할 때는 항상 증가 부분 수열의 시작 위치를 지정해줘야
  -> S[-1] = -infinite라고 가정하면
  -> lis2(-1)을 호출하면 항상 -infinite 부터 시작
  -> 모든 시작 위치를 자동으로 시도하게 된다

• lis3(start): lis2()의 시작 위치를 고정한 함수
  -> start = -1이 주어질 수 있음
  -> cache[start] 대신 cache[start + 1] 사용, cache[]배열 크기 1 증가
  -> 결과 : lis3(-1) -1 (S[-1]은 가상으로 추가한 입력값이기 때문에 최종 반환값-1)

	int n;
	int cache[101], S[100];

	int lis2(int start){
		//lis2(start)에 대한 답을 구한 적이 있으면 곧장 반환
		int& ret = cache[start+1];
		if(ret != -1) return ret;

		//lis2(start)에 대한 답 계산
		//항상 S[start]는 있기 때문에 길이는 최하 1
		ret = 1; 
		for(int next = start+1; next < n; ++next)
			if(start == -1 || S[start] < S[next])
				ret = max(ret, 1 + lis2(next));

		return ret;
	}

• 더 빠른 해법: 이분 탐색 이용하기
  https://velog.io/@sunjoo9912/LIS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-1

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

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

2. 전체 답의 점수를 반환하는 것이 아닌,
   앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제의 정의 바꾸기

3. 메모이제이션 적용

• 재귀 호출의 입력에 이전 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄인다
  -> 최적 부분 구조 성립할 경우 이전 선택에 관련된 정보 완전히 없앨 수 있다

• 재귀 호출의 입력이 배열이거나 문자열인 경우 가능하다면 적절히 변환
  -> 입력의 종류가 줄어들수록 많은 부분 문제 중복됨 -> 메모이제이션 효과적

합친 LIS(JLIS)

• 두 개의 정수 배열 A와 B의 각각 길이가 0 이상의 증가 부분 수열을 얻은 뒤 이들을 크기 순서대로 합친 것
  = 합친 증가 부분 수열

• 합칩 증가 부분 수열 중 가장 긴 수열
  = 합친 LIS(JLIS, Joined Longest increasing Sebsequence)

• jlis(indexA, indexB): A[indexA]와 B[indexB]에서 시작하는 합친 증가 부분 수열의 최대 길이

• 이 증가 부분 수열의 다음 숫자:
  A[indexA+1]이후 혹은 B[indexB+1]이후의 수열 중 max(A[indexA], B[indexB])보다 큰 수 중 하나

• A[-1] = B[-1] = -infinite 로 두고, 이 둘은 항상 jlis에 포함된다고 가정

//입력이 32비트 부호있는 정수의 모든 값을 가질 수 있으므로 
//인위적인 최소치(-infinite)는 64비트여야 한다
const long long NEGINF = numeric_limits<long long>::min();
int n, m, A[100], B[100];
int cache[101][101];

//첫번째 숫자가 min(A[indexA], B[indexB])이고, 두번째 숫자가 max(A[indexA], B[indexB])인
//합친 증가 부분 수열의 최대 길이 반환
//단, indexA == indexB == -1 부터 시작하고 A[indexA] != B[indexB]라고 가정한다
int jlis(int indexA, int indexB){

	//메모이제이션
	// indexA와 indexB의 값으로 -1이 주어질 수 있음
	// cache[indexA][indexB] 대신 cache[indexA+1][indexB+1] 사용
	int& ret = cache[indexA+1][indexB+1];
	if(ret != -1) return ret;

	//A[indexA], B[indexB]가 이미 존재하므로 길이는 최하 2
	ret = 2;
	//A[indexA] (A[-1] = -infinite)
	long long a = (indexA == -1 ? NEGINF : A[indexA])
	//B[indexB] (B[-1] = -infinite)
	long long b = (indexB == -1 ? NEGINF : B[indexB])
	//다음 원소 찾기
	long long maxElement = max(a, b);
	for(int nextA = indexA + 1; nextA < n ; ++nextA){
		if(maxElement < A[nextA])
			ret = max(ret, 1 + jlis(nextA, indexB));
	}
	for(int nextB = indexB + 1; nextB < n ; ++nextB){
		if(maxElement < B[nextB])
			ret = max(ret, 1 + jlis(indexA, nextB));
	}
	return ret;
}

원주율 외우기(PI)

• 원주율의 일부가 입력으로 주어질 때, 난이도의 합을 최소화하도록 숫자들을 3~5자리로 끊어 읽으려고 한다
  -> 이때 가능한 최소 난이도를 계산하는 프로그램 작성

• 각 조각들의 난이도
  -> 모든 숫자가 같을 때 = 1 (ex. 333, 555)
  -> 숫자가 1씩 단조 증가/감소할 때 = 2 (ex. 23456, 3210)
  -> 두 개의 숫자가 번갈아가며 나타날 때 = 4 (ex. 323, 54545)
  -> 숫자가 등차 수열을 이룰 때 = 5 (ex. 147, 8642)
  -> 이 외의 모든 경우 = 10 (ex. 331, 17912)

• 첫 조각의 길이를 하나하나 시도해보며 남은 수열을 재귀적으로 쪼개도록 구현
  -> 길이 3인 조각의 난이도 + 3글자 빼고 나머지 수열에 대한 최적해
  -> 길이 4인 조각의 난이도 + 4글자 빼고 나머지 수열에 대한 최적해
  -> 길이 5인 조각의 난이도 + 5글자 빼고 나머지 수열에 대한 최적해

• 한 조각의 숫자가 주어졌을 떄 난이도 판정

const int INF = 987654321;
string N;

//N[a .. b]구간의 난이도를 반환한다
int classify(int a, int b){
	//숫자 조각을 가져온다
	string M = N.substr(a, b-a+1);

	//모든 숫자가 같을 때 -> 1
	if(M == string(M.size(), M[0]))	return 1;

	//등차 수열인지 판별	 
	bool progressive = true;
	for(int i = 0; i<M.size()-1; ++i)
		if(M[i+1] - M[i] != M[1] - M[0]){
			progressive = false;
			break;
		}
	//숫자가 1씩 단조 증가/감소할 때 -> 2
	if(progressive && abs(M[1] - M[0]) == 1) return 2;
    	//숫자가 등차 수열을 이룰 때 -> 5
	if(progressive) return 5;

	//두 개의 숫자가 번갈아가며 나타나는지 판별
	bool alternating = true;
	for(int i = 0; i<M.size(); ++i){
		if(M[i] != M[i%2]){
			alternating = false;
			break;
		}
	}
	//두 개의 숫자가 번갈아가며 나타날 때 -> 4
	if(alternating) 
		return 4;
    //이 외의 모든 경우	-> 10
	return 10;
}

• 실제 메모이제이션 구현

int cache[10002];

//숫자 N[begin .. ]를 외우는 방법 중 난이도의 최소 합을 구한다
int memorize(int begin){
	//base case
	if(begin == N.size()) return 0;

	//메모이제이션
	int& ret = cache[begin];
	if(ret != -1) return ret;

	ret = INF;
	for(int L = 3; L <= 5; ++L)
		if(begin + L <= N.size())
			ret = min(ret, classify(begin, begin+L-1) + memorize(begin+L));
	return ret;
}

📌참고자료

• memset 사용시 주의할 점
  https://minusi.tistory.com/entry/memset-%EC%82%AC%EC%9A%A9%EC%8B%9C-%EC%A3%BC%EC%9D%98%ED%95%A0-%EC%A0%90

• #include $<cstring>$
• void $*$memset ( void * ptr, int value, size_t num );
  -> ptr 포인터에 의해 지정된 메모리 블록의 num 바이트만큼을 지정된 value로 채웁니다
  ->이 때 메모리 블록을 채우는 기준이 1byte(8bit = unsigned char) 이다
  -> 0이 아닌 다른 값으로 메모리를 초기화하고자 할 때 문제가 발생할 수 있다

➖ 21-07-09

경우의 수와 확률

• 동적 계획법은 경우의 수를 세거나 확률을 계산하는 문제에도 사용된다

경우의 수 계산하기 레시피

1. 모든 답을 직접 만들어서 세어보는 완전 탐색 알고리즘 설계
   이때, 재귀 호출의 각 단계에서 고르는 각 선택지는 다음과 같은 속성이 성립해야한다
   -> 모든 경우는 이 선택지들에 포함되어야 한다
   -> 어떤 경우도 두개 이상의 선택지에 포함되지 않아야 한다

2. 최적화 문제를 해결할 때와 같이, 이전 조각에서 결정한 요소들에 대한 입력을 없애거나 변형해서 줄인다
   -> 재귀 함수는 앞으로 남아있는 조각들을 고르는 경우의 수만을 반환해야

3. 메모이제이션 적용