알고리즘 문제 해결 전략 1 - CH 08. 동적 계획법(2)

알고리즘 문제 해결 전략을 읽고

(p.225 ~ p.239)

CH 08. 동적 계획법

8.4 전통적 최적화 문제들

동적 계획법의 가장 일반적인 사용처는 최적화 문제의 해결이다. (최적화 문제란 여러 개의 가능한 답 중 가장 좋은 답을 찾아내는 문제를 말한다.)

 

예제: 삼각형 위의 최대 경로

맨 위의 숫자에서 시작하여 아래줄로(바로 아래 숫자 또는 오른쪽 아래 숫자만 가능) 내려가며 숫자를 더할 때 모든 경로 중 숫자의 합을 최대화하는 경로를 구하는 프로그램

 

아래와 같은 재귀 호출을 통한 완전 탐색을 이용하여 구현할 수 있지만 모든 경로를 다 확인해야 하기 때문에 가로줄이 늘어난다면 계산이 불가능하다.

// path1(y, x, sum) = 맨 윗 줄부터 현재 위치(y, x)의 아래/오른쪽 아래로 쭉 내려갔을 때까지 얻을 수 있는 최대 합
path1(y, x, sum) = max(path(y+1, x, sum+triangle[y][x]), path(y+1, x+1, sum+triangle[y][x]))

 

따라서 위의 점화식에 무식하게 메모이제이션을 적용한 코드는 다음과 같다. 

하지만 아래 코드는 배열의 크기가 너무 커서 사용되는 메모리가 너무 크다는 점과 특정 입력에서 완전 탐색처럼 동작한다는 문제점이 있다.

int n, triangle[100][100];
int cache[100][100][MAX_NUMBER*100+1];

int path1(int y, int x, int sum) {
    // 기저 사례: 맨 아래 줄까지 도달했을 경우
    if(y == n-1) return sum + triangle[y][x];
    // 메모이제이션
    int& ret = cache[y][x];
    if(ret != -1) return ret;
    sum += triangle[y][x];
    return ret = max(path1(y+1, x+1, sum), path1(y+1, x, sum));
}

 

이러한 문제를 해결하기 위해 필요없는 입력인 sum을 제거하면 아래와 같은 코드가 최종적으로 나온다. 

// path2(y, x) = (y, x)에서 시작해서 맨 아래줄까지 내려가는 부분 경로의 최대 합
path2(y, x) = triangle[y][x] + max(path2(y+1, x), path2(y+1, x+1))

int n, triangle[100][100];
int cache2[100][100];

int path2(int y, int x) {
    // 기저 사례: 맨 아래 줄까지 도달했을 경우
    if(y == n-1) return triangle[y][x];
    // 메모이제이션
    int& ret = cache2[y][x];
    if(ret != -1) return ret;
    return ret = max(path2(y+1, x), path2(y+1, x+1)) + triangle[y][x];
}

 

위의 두 번째 메모이제이션 적용 사례는 지금까지 어떤 경로로 현재 위치의 부분 문제에 도달했건 남은 부분 문제는 항상 최적으로 풀어도 상관 없다는 최적 부분 구조의 조건을 만족시킨다. 이 최적 부분 구조는 효율적인 동적 계획법 알고리즘을 적용하기 위한 중요한 조건이다. 

 

 

예제: 최대 증가 부분 수열

주어진 수열에서 얻을 수 있는 가장 긴 증가 부분 수열을 찾는 프로그램

 

A[j] = 2라는 숫자가 수열의 첫 숫자라고 할 때, 위치가 j보다 크면서 2보다 큰 숫자들을 고른 뒤 그 숫자들로 수열을 만들어 A[j] 뒤에 붙여주면 A[j]로 시작하는 부분 수열을 얻을 수 있다. 이를 완전 탐색 알고리즘으로 구현하면 아래 코드와 같다. 

// lis(A) = A의 증가하는 모든 부분 수열 중 가장 긴 부분 수열의 길이를 반환
int lis(const vector<int>& A) {
    // 기저 사례: A가 비어있을 때
    if(A.empty()) return 0;
    int ret = 0;
    for(int i = 0; i < A.size; i++)
    	vector<int> B;
        for(int j = i+1; j < A.size(); j++)
            if(A[i] < A[j])
                B.push_back(A[j]);
        ret = max(ret, 1 + lis(B));
    }
    return ret;
}

 

위 코드는 완전 탐색의 기능을 잘 수행하지만 입력이 정수가 아니라 정수 배열이기 때문에 메모이제이션 적용이 까다롭다. 

따라서 수열 A를 더 간단히 표현하여 코드를 다시 작성하면 아래와 같이 나오게 된다. 

// lis(start) = S[start]에서 시작하는 부분 증가 수열 중 최대의 길이
int n;
int cache[100], S[100];

int lis2(int start) {
    int& ret = cache[start];
    if(ret != -1) return ret;
    ret = 1;
    for(int next = start + 1; next < n; next++)
    	if(S[start] < S[next])
        	ret = max(ret, lis2(next)+1);
    return ret;
}

 

여기에 시작 위치를 고정하는 코드를 추가하면

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

int lis3(int start) {
    int& ret = cache[start+1];
    if(ret != -1) return ret;
    ret = 1;
    for(int next = start + 1; next < n; next++)
    	if(start == -1 || S[start] < S[next])
        	ret = max(ret, lis3(next)+1);
    return ret;
}

다음과 같은 코드가 완성된다. 

 

 

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

1. 모든 답을 만들어 보고 그중 최적해의 점수를 반환하는 완전 탐색 알고리즘 설계하기
2. 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꾸기
3. 재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄이기
4. 입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모이제이션할 수 있도록 하기
5. 메모이제이션 적용하기

(22.09.21 추가)

8.5 문제: 합친 LIS

8.6 풀이: 합친 LIS

수열 A와 수열 B에서 각각 얻은 증가 부분 수열을 합쳐서 만든 수열 중 가장 긴 것 즉, LIS의 길이를 계산하는 프로그램

 

이 문제는 두 개의 수열에서 각각 LIS를 구한 뒤 이를 합치면 된다고 생각할 수 있지만 이 방식으로 풀이를 하면 답이 나오지 않는다. 

문제를 풀기 위해서는 다음과 같은 코드를 작성할 수 있다. 

const long long NEGINF = numeric_limits<long long>::min();
int n, m, A[100], B[100];
int cache[101][101];

int jlis(int indexA, int indexB){
	int& ret = cache[indexA+1][indexB+1];
    if(ret != -1) return ret;
    ret = 2;
    long long a = (indexA == -1 ? NEGINF : A[indexA]);
    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, jlis(nextA, indexB)+1);
    for(int nextB = indexB+1; nextB < n; nextB++)
    	if(maxElement < B[nextB])
        	ret = max(ret, jlis(indexA, nextB)+1);
    return ret;
}