[알고리즘 문제 해결 전략] Ch03-3. 알고리즘 설계 패러다임 (동적 계획법)

8 동적 계획법

8.1 도입

동적 계획법(dynamic programming)이라는 말은 최적화 문제를 연구하는 수학 이론에서 왔으며, 우리가 전산학 전반에서 일반적으로 사용하는 동적(dynamic), 혹은 프로그래밍(programming)이라는 단어와는 아무런 관련이 없다.

중복되는 부분 문제

동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 동적 계획법을 사용하는 알고리즘들 또한 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문이다. 동적 계획법과 분할 정복의 차이가 발생하는 부분은 문제를 나누는 방식이다.

동적 계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에, 이 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함으로써 속도의 향상을 꾀할 수 있다. 그러기 위해서는 각 문제의 답을 메모리에 저장해 둘 필요가 있다. 이 때 이미 계산한 값을 저장해 두는 메모리의 장소를 캐시(cache)라고 부르며, 두 번 이상 계산되는 부분 문제를 중복되는 부분 문제(overlapping subproblems)라고 부른다.

동적 계획법 알고리즘의 가장 유명한 예 중 하나는 이항 계수(binomial coefficient)의 계산이다. 이항 계수 ${n \choose r}$은 n개의 서로 다른 원소 중에서 r개의 원소를 순서없이 골라내는 방법의 수를 나타낸다.

재귀 호출로 이항 계수를 계산 하는 방법은 다음과 같다.

int bino(int n, int r) {
    // 기저 사례: n=r(모든 원소를 다 고르는 경우) 혹은 r=0(고를 원소가 없는 경우)
    if(r == 0 || n == r) return 1;
    return bino(n-1, r-1) + bino(n-1, r);
}

함수의 중복 호출 수는 n과 r이 커짐에 따라 기하급수적으로 증가한다. _bino(25, 12)_를 계산하기 위해서는 무려 1천만 번의 함수 호출이 필요하다. 이러한 계산량의 낭비를 피할 수는 없을까?

입력인 n과 r이 정해져 있을 때 _bino(n, r)_의 반환 값이 일정하다는 사실을 이용하면 이 문제에서 중복 계산을 제거할 수 있다. 각 n,r 조합에 대해 답을 저장하는 캐시 배열을 만들어서 각 입력에 대한 반환 값을 저장하기로 하자. 함수는 매번 호출될 때마다 이 배열에 접근해 값이 저장되어 있는지를 확인한 뒤, 저장되어 있다면 이것을 즉시 반환한다. 만약 계산되어 있지 않을 경우에는 직접 계산하여 배열에 써 넣고 반환한다. 이 방법을 이용해 다시 이항 계수를 구현한 방법은 아래와 같다. 이와 같이 함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법을 메모이제이션(memoization)이라고 부른다.

// -1로 초기화 해둔다
int cache[30][30];
int bino2(int n, int r) {
    // 기저 사례
    if(r == 0 || n == r) return 1;
    // -1이 아니라면 한 번 계산했던 값이니 곧장 반환
    if(cache[n][r] != -1)
        return cache[n][r];
    // 직접 계산한 뒤 배열에 저장
    return cache[n][r] = bino2(n-1, r-1) + bino2(n-1, r);
}

메모이제이션 구현 패턴

동적 계획법은 가장 흔한 문제 유형 중 하나이기 때문에 메모이제이션은 자주 구현하게 된다. 한 가지 패턴을 정해두고 항상 같은 형태로 구현하기로 하면 작성하기도, 버그를 찾기도 쉬워진다. 다음과 같은 재귀함수를 메모이제이션 구현하는 방법을 코드로 확인하자.

// 전부 -1로 초기화
int cache[2500][2500];

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

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

이 함수를 어떤식으로 메모이제이션으로 바꿔서 구현하는지 생각해 보자.

• 기저 사례를 제일 먼저 처리한다.
• 함수의 반환 값이 항상 0 이상이라는 점을 이용해 cache[]를 모두 -1로 초기화한다.
• ret가 cache[a][b]에 대한 참조형(reference)이라는데 유의한다. 참조형 ret의 값을 바꾸면 cache[a][b]의 값도 변하기 때문에 답을 저장할 때도 매번 귀찮게 cache[a][b]라고 쓸 필요가 없어진다.
• memset()을 이용해 cache[]를 초기화 하는 부분에 주목하자. 메모이제이션용 배열을 초기화 하는 일은 매우 자주 하는 일이므로 다중 for문보다 쉽게 초기화 할 수 있다. 단, memset()으로 배열을 초기화하는 방법은 굉장히 제한적인 경우에만 쓸 수 있다는 점에 유의하자.

메모이제이션의 시간 복잡도 분석

메모이제이션을 사용하는 알고리즘의 시간복잡도를 간단하게 계산할 수 있는 방법이 있다.

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

위 식을 이항 계수를 계산하는 bino2()*에 적용해 보자. r의 최대치는 n이므로 *bino2(n, r) 을 계산할 때 만날 수 있는 부분 문제의 수는 최대 O($n^2$)이다. 각 부분 문제를 계산할 때 걸리는 시간은 반복문이 없으므로 O(1)이고, 그러면 위 식에 따라 _bino2(n,r)_을 계산하는 데 걸리는 시간 복잡도는 $O(n^2) \times O(1)=O(n^2)$가 된다.

위의 그림 8.3을 통해 재귀 호출이 이루어지는 과정을 살펴보도록 하자. 여기서 각 원은 부분 문제를 나타낸다. 굵은 원은 해당 부분 문제를 처음 만나서 답을 직접 계산하는 경우, 그리고 얇은 원은 기저 사례나 이미 답을 계산해 둔 부분 문제에 도달한 경우를 표시한다. 여기서 얇은 원은 상수 시간에 수행되기 때문에 알고리즘의 전체 수행 시간에 영향을 미치지 않는다. 따라서 메모이제이션의 수행 시간은 굵은 원으로 표시된 재귀 호출의 수행 시간의 합이 되는데, 이 값의 상한이 앞에서 본 식이다.

8.2 문제: 와일드카드 (문제 ID: WILDCARD, 난이도 : 중)

문제

8.3 풀이: 와일드카드

이 문제를 어렵게 만드는 것은 *가 몇 글자에 대응되어야 하는지를 미리 알 수 없다는 점이다. 이럴 때 할 수 있는 가장 쉬운 방법은 완전탐색이다. 주어진 패턴이 m개의 *을 포함한다고 할 때, 이 패턴을 *가 나타날 때마다 쪼개면 이 패턴이 문자열에 대응하는지 확인하는 문제를 m+1 조각으로 나눌 수 있다. 어떤 문자열이 주어졌을 때 이 문자열 중 몇 글자가 첫 번째 조각에 대응하는지 확인한 후 그 부분을 제외한 나머지 문자열에서 두 번째 조각에 대응하는지 확인하는 식으로... 재귀 호출로 파악할 수 있다.

패턴을 쪼개지 않고서도 구할 수도 있다. 와일드카드 w가 원문 s에 대응되는지 여부를 반환하는 함수 match(w,s)를 아래와 같이 만들어 볼 수 있다. w와 s를 앞에서부터 한 글자씩 대응해 나가며, *를 만나거나 둘 중 한 문자열이 끝날 때 멈춘다. while 문은 w와 s를 더이상 맞춰 나갈 수 없을 때 종료한다. 종료하는 경우의 수는 다음과 같다.

1. _s[pos]_와 _w[pos]_가 대응되지 않는다 : 대응 실패
2. w 끝에 도달했다 : 패턴에 *이 하나도 없는 경우이다. 이 경우 패턴과 문자열의 길이가 정확히 같아야만 패턴과 문자열이 대응된다고 할 수 있다.
3. s 끝에 도달했다 : 패턴은 남았지만 문자열이 이미 끝난 경우이다. 남은 패턴이 전부 *로 구성되어 있는 경우가 아닌 이상 대응 실패이다.
4. w[pos]가 *인 경우 : *가 몇 글자에 대응될지 모르기 때문에, 0글자부터 남은 문자열의 길이까지를 순회하며 모든 가능성을 검사한다. 이 때 w의 pos+1 이후를 패턴 w’으로 하고, s의 pos + skip 이후를 문자열 s’로 해서 match(w’, s’)로 재귀 호출했을 때 답이 하나라도 참이면 답은 참이 된다.

// 와일드카드 패턴 w가 문자열 s에 대응되는지 여부를 반환한다.
bool match(const string& w, const string & s) {
    // w[pos]와 s[pos]를 맞춰 나간다.
    int pos = 0;
    while(pos < s.size() && pos < w.size() && (w[pos] == '?' || w[pos] == s[pos]))
        ++pos;
    // 더 이상 대응할 수 없으면 왜 while문이 끝났는지 확인한다.
    // 2. 패턴 끝에 도달해서 끝난 경우: 문자열도 끝났어야 대응된다.
    if(pos == w.size())
        return pos == s.size();
    // 4. *를 만나서 끝난 경우: *에 몇 글자를 대응해야 할지 재귀 호출하면서 확인한다.
    if(w[pos] == '*')
        for(int skip = 0; pos+skip <= s.size(); ++skip)
            if(match(w.substr(pos+1), s.substr(pos+skip)))
                return true;
    // 이외의 경우에는 모두 대응되지 않는다.  
    return false;
}

중복되는 부분문제

이 알고리즘은 일부 입력값의 경우 너무 오랜 시간이 걸릴 수 있다는 문제가 있다. 각 _에 대응되는 글자 수의 모든 조합을 검사하는데, 문자열이 길고 _가 많을 수록 이 경우의 수는 늘어난다. 예를 들면 ****__a 와 aaaaaaaaaab 와 같은 입력값이 주어진 경우이다.

만약 이 코드가 실행되는 과정에서 수행하는 계산의 대부분이 여러 번 중복으로 이루어진다면, 입력이 주어졌을 때 답을 저장하는 캐시를 이용하여 프로그램을 더 빠르게 실행할 수 있다. 입력으로 주어지는 w, s의 종류는 제한되어 있다. 재귀 호출할 때 항상 w와 s의 앞 글자만 떼어내기 때문에 w와 s는 항상 입력에 주어진 패턴 W와 파일명 S의 접미사(suffix)가 된다. 따라서 입력으로 주어질 수 있는 w와 s는 각각 최대 101개 밖에 없다. 이 때 match() 가 101X101=10,201 번 이상 호출되었다면 비둘기집의 원리에 따라 어떤 부분 문제가 반드시 여러번 계산되고 있음을 알 수 있다.

메모이제이션을 사용해 이 문제를 풀어보자. w는 항상 전체 패턴 W의 접미사이기 때문에 w의 길이가 결정되면 w 또한 결정된다. 이 점을 이용하면 101 X 101 크기의 배열에 모든 부분 문제의 답을 저장할 수 있다. 아래 코드는 메모이제이션을 통해 알고리즘을 구현했다. 더이상 문자열을 재귀 호출의 인자로 넘기지 않고 두 문자열의 시작 위치만을 넘기는 것이다. 그러면 매번 문자열 객체를 생성하는 수고를 덜 수 있다.

// -1은 아직 답이 계산되지 않았음을 의미한다.
// 1은 해당 입력들이 서로 대응됨을 의미한다.
// 0은 해당 입력들이 서로 대응되지 않음을 의미한다.
int cache[101][101];
// 패턴과 문자열
string W, S;
// 와일드카드 패턴 W[w..]가 문자열 S[s..]에 대응되는지 여부를 반환한다.
bool matchMemoized(int w, int s) {
    // 메모이제이션
    int& ret = cache[w][s];
    if(ret != -1) return ret;
    // W[w]와 S[s]를 맞춰나간다.
    while(s < S.size() && w < W.size() && (W[w] == '?' || W[s] == S[s])) {
        ++w;
        ++s;
    }
    // 더이상 대응할 수 없으면 왜 while문이 끝났는지 확인한다.
    // 2. 패턴 끝에 도달해서 끝난 경우: 문자열도 끝났어야 참
    if(w == W.size()) return ret = (s == S.size());
    // 4. *를 만나서 끝난 경우: *에 몇 글자를 대응해야 할지 재귀 호출하면서 확인한다.
    if(W[w] == '*')
        for(int skip = 0; skip+s <= S.size(); ++skip)
            if(matchMemioized(w+1, s+skip))
                return ret = 1;
    // 3. 이 외의 경우에는 모두 대응되지 않는다.
    return ret = 0;
}

패턴과 문자열의 길이가 모두 n이라고 할 때, 부분 문제의 개수는 $n^2$이다. _matchMemoized()_는 한 번 호출될 때마다 최대 n번의 재귀 호출을 하기 때문에 전체 시간 복잡도는 $O(n^3)$이다.

8.4 전통적 최적화 문제들

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

최적화 문제를 동적 계획법으로 푸는 것 또한 완전 탐색에서 시작한다. 그러나 최적화 문제에 특정 성질이 성립할 경우 단순히 메모이제이션을 적용하기 보다 좀 더 효율적으로 동적 계획법을 구현할 수 있다.

예제 : 삼각형 위의 최대 경로 (문제 ID : TRIANGLEPATH, 난이도 : 하)

아래 그림처럼 삼각형으로 배치된 자연수들이 있다고 생각해 보자. 맨 위에서 시작해서 한 번에 한 칸씩 아래로 내려갈 때 맨 아래 줄까지 닿는 경로를 만든다. 경로는 아래로 내려갈 때 바로 아래 또는 오른쪽 아래 숫자로 갈 수 있다. 모든 경로의 합을 최대화 하는 경우를 구하여 그 합을 계산한다.

가장 먼저 완전 탐색을 생각해 볼 수 있을 것이다. 모든 경로를 만든다고 했을 때 다음과 같은 재귀 호출 함수를 만들어 볼 수 있을 것이다.

$pathSum(y, x, sum)$ = 현재 위치가 (y, x)이고, 지금까지 만난 수의 합이 sum일 때, 이 경로를 맨 아래줄까지 연장해서 얻을 수 있는 최대 합을 반환한다.

이 때 아래쪽으로 내려갔을 때와 오른쪽으로 내려갔을 때의 최대 합을 각각 path()를 이용해 표현하면 다음과 같은 점화식을 얻을 수 있다.

$$
path1(y,x,sum)=math\begin{cases}path(y+1,x,sum+triangle[y][x])\\
path(y+1,x+1,sum+triangle[y][x])
\end{cases}
$$

하지만 이 방법은 모든 경로를 다 만들어 봐야 한다는 문제가 있다. 이 문제에서 n개의 가로줄이 있을 때 삼각형의 가로줄이 하나 늘어날 때 마다 두 배씩 늘어나기에 가능한 경로의 수는 $2^{n-1}$이 된다. 그렇다면 메모이제이션을 적용해 보자.

위에서 구현한 점화식에 메모이제이션을 적용한 코드는 다음과 같다.

// MAX_NUMBER: 한 칸에 들어갈 숫자의 최대치
int n, triangle[100][100];
int cache[100][100][MAX_NUMBER*100+1];
// (y,x) 위치까지 내려오기 전에 만난 숫자들의 합이 sum일 때
// 맨 아래줄까지 내려가면서 얻을 수 있는 최대 경로를 반환한다.
int path1(int y, int x, int sum) {
    // 기저 사례: 맨 아래 줄까지 도달했을 경우
    if(y == n-1) return sum + triangle[y][x];
    // 메모이제이션
    int& ret = cache[y][x][sum];
    if(ret != -1) return ret;
    sum += triangle[y][x];
    return ret = max(path1(y+1, x+1, sum), path1(y+1, x, sum));
}

이 코드의 문제는 첫 번째로 사용해야 하는 메모리의 크기가 너무 크다. 배열의 크기가 입력으로 주어지는 숫자의 범위에 좌우되기 때문이다. 두 번째 문제는 path1()이 특정 입력에 대해서는 완전 탐색처럼 동작한다는 것이다. 예를 들어 위의 이미지처럼 모든 값이 $2^i$꼴의 숫자로 구성된 삼각형이 있다면, 이 때 서로 다른 경로는 합이 항상 다르다. 같은 계산을 두 번 할 일이 없고 완전 탐색과 다를 바가 없다.

입력 걸러내기

이 알고리즘을 조금 더 빠르게 하는 힌트는 재귀 함수의 입력을 다음과 같이 두 부류로 나눠 보면 알 수 있다.

1. y와 x는 재귀 호출이 풀어야 할 부분 문제를 지정한다. 이 두 입력이 정해지면 앞으로 우리가 만들 수 있는 경로들이 정해진다. 따라서 이들은 앞으로 풀어야 할 조각들에 대한 정보를 주는 입력들이다.
2. 반면 sum은 지금까지 어떤 경로로 이 부분 문제에 도달했는지를 나타낸다. sum은 지금까지 풀었던 조각들에 대한 정보를 주는 입력이다.

$$
[0] [1] ... [y-1] [y] [y+1] ... [n-2][n-1]
$$

• ~ [y-1] : 이미 해결한 조각들
• [y] ~ [n-1] : 아직 해결하지 못한 조각들

다시 말하면 (y,x)는 오른쪽에 아직 해결하지 못한 조각들을 정의하는 입력이고, sum은 왼쪽에 이미 결정한 조각들에 대한 정보이다. 여기서 이미 해결된 sum은 남은 조각들을 푸는데 필요하지 않다. 따라서 재귀 함수에 sum을 아예 입력값으로 받지 않으면 알고리즘은 훨씬 더 빨라질 것이다.

하지만, 재귀 함수에서 sum을 입력 값으로 입력받지 못하면 이전까지 어떤 숫자들을 만났는지 알 수 없기에 전체 경로의 최대 합을 반환할 수 없다. 따라서 함수의 반환 값을 전체 경로의 최대치가 아니라 (y,x)에서 시작하는 부분 경로의 최대치로 바꿀 필요가 있다. 결과적으로는 다음과 같은 부분 문제를 얻는다.

path2(y,x) = (y,x)에서 시작해서 맨 아래줄까지 내려가는 부분 경로의 최대 합을 반환한다.

path2()는 앞으로 남은 조각들의 결과만을 반환한다. path2()의 동작은 다음과 같은 점화식으로 정의할 수 있다.

$$
path2(y,x)=triangle[y][x]+max\begin{cases}path2(y+1,x)\\
path2(y+1,x+1)
\end{cases}
$$

이 알고리즘에서 부분 문제의 수는 $O(n^2)$이고 각 부분 문제를 계산하는 데는 상수 시간밖에 안 걸리기 때문에 전체 시간 복잡도는 $O(n^2)$이 된다.

int n, triangle[100][100];
int cache2[100][100];
// (y,x) 위치부터 맨 아래줄까지 내려가면서 얻을 수 있는 최대 경로의 합을 반환한다.
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];
}

이론적 배경 : 최적 부분 구조

이와 같은 최적화 방법은 최적 부분 구조(optimal substructure)라는 이름으로 동적 계획법의 중요한 요소로 불린다. 다시 말해, 지금까지 어떤 경로로 이 부분 문제에 도달했건 남은 부분 문제는 항상 최적으로 풀어도 상관이 없다는 뜻이다. 최적 부분 구조는 어떤 문제와 분할 방식에 성립하는 조건이다. 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 얻어낼 수 있을 경우 이 조건이 성립한다고 한다.

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

다음은 최적화 문제의 동적 계획법을 설계하기 위한 과정을 간략하게 정리한 것이다. 모든 문제를 해결해 주지는 않겠지만, 대략적인 지침은 될 것이다.

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

8.5 문제 : 합친 LIS (문제 ID : JLIS, 난이도 : 하)

문제

8.6 풀이 : 합친 LIS

이 문제를 보고 처음 떠오르는 생각은 각각의 수열에서 LIS를 찾아서 합치는 것일 것이다. 하지만 이 방법은 주어진 예제 조차도 통과하지 못한다. 예제에서 세 번째 케이스를 보면 첫 번째 수열의 LIS도 [10, 20, 30], 두 번째 수열의 LIS도 [10, 20, 30]이다. 따라서 합쳐도 [10, 20, 30]인데 우리가 이 케이스에서 구하려는 답은 [1, 2, 10, 20, 30]이다.

우리가 기존에 LIS를 찾는데 사용했던 알고리즘을 변형해서 풀어보자. 수열 S의 최대 증가 부분 수열을 찾는 재귀 함수 lis3()의 정의는 다음과 같다.

$lis3(start)$ = S[start]에서 시작하는 최대 증가 부분 수열 길이

수열이 A, B 두 개일 경우 재귀 함수도 두 개의 입력을 받아야 한다.

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

두 수의 순서를 지정하지는 않았으므로, A[indexA]와 B[indexB] 중 작은 쪽이 앞에 온다고 하자. 그러면 이 증가 부분 수열의 다음 숫자는 A[indexA+1] 이후 혹은 B[indexB+1] 이후 수열 중 max(A[indexA],B[indexB])보다 큰 수 중 하나가 된다. 그리고 A[nextA]를 다음 숫자로 선택했을 경우에 합친 증가 부분 수열의 최대 길이는 1+jlis(nextA, indexB)가 된다. 점화식으로 쓰면 다음과 같다.

$$
jlis(indexA,indexB)=max\begin{cases}max_{nextA\in NEXT(indexA)}jlis(nextA, indexB)+1\\
max_{nextB\in NEXT(indexB)}jlis(indexA, nextB)+1
\end{cases}
$$

이 때 NEXT(indexA)와 NEXT(indexB)는 증가 부분 수열의 다음 위치에 올 수 있는 A와 B 원소의 인덱스이다. 이 아이디어를 구현한 코드는 아래와 같다. lis3()와 같이 a[-1]=B[-1]=$-\infty$ 로 두고 이 둘은 항상 JLIS에 포함된다고 가정한다.

// 입력이 32비트 부호 있는 정수의 모든 값을 가질 수 있으므로
// 인위적인 최소치는 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) {
    // 메모이제이션
    int& ret = cache[indexA+1][indexB+1];
    if(ret != -1) return ret;
    // A[indexA], B[indexB]가 이미 존재하므로 2개는 항상 있다.
  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 = index + 1; nextA < n; ++nextA)
        if(maxElement < A[nextA])
            ret = max(ret, jlis(nextA, indexB) + 1);
    for(int nextB = indexB + 1; nextB < m; ++nextB)
        if(maxElement < B[nextB])
            ret = max(ret, jlis(indexA, nextB) + 1);
    return ret;
}

8.9 문제 : Quantization (문제 ID : QUANTIZE, 난이도 : 중)

문제

8.10 풀이 : Quantization

이 문제는 일반적인 재귀적 해법을 찾으려고 하면 성공할 수 없다. 단순하게 생각해 보면 양자화된 결과 수열을 답으로 생각하고, 맨 앞의 숫자에서부터 하나씩 채워 나가는 접근 방법을 택하게 된다. 주어진 수열 A의 첫 번째 숫자를 어떤 숫자로 표현할 것인지를 결정하고, 나머지 수열에 대해 재귀 호출로 문제를 해결하는 식이다.

$quantize(A)$ = A에 속한 수를 양자화해서 얻을 수 있는 최소 오차 제곱의 합

그런데 이 문제에서는 사용할 수 있는 숫자의 가지수에 제한이 있기 때문에 남은 문제를 재귀적으로 해결할 때는 이 함수처럼 지금까지 사용한 숫자들을 무시할 수가 없다. 이미 s가지 숫자들을 다 쓴 상태라면 이 중 하나의 숫자를 선택해야 하기 때문이다. 다시 말해, 최적 부분 조건이 성립하지 않는다.

$quantize()$는 남은 숫자들만이 아니라 이전 숫자들을 어떤 숫자로 양자화했는지 또한 알아야 하기 때문에, 지금까지 사용한 숫자들의 집합 또한 입력으로 받아야 한다. 결국 함수는 다음과 같은 형태로 구현해야 한다

$quantize(A,U)$ = U가 지금까지 한 번 이상 사용한 숫자들의 집합일 때 A에 속한 수를 양자화해서 얻을 수 있는 최소 오차 제곱의 합

그러면 quantize()는 A의 첫 번째 숫자를 어떻게 표현할지를 결정하고 나머지를 재귀 호출해서 해결하게 된다. 그러나 이러한 완전 탐색 코드는 실로 엄청나게 많은 수의 답을 하나하나 만들게 된다. 메모이제이션에 필요한 메모리를 확보할 수도 없고, 시간도 엄청나게 오래 걸린다.

답의 형태 제한하기

이와 같이 부분 문제의 갯수가 너무 많을 때 쓸 수 있는 방법 중 하나는, 답이 항상 어떤 구조를 가질 것이라고 예측을 하고 그것을 강제하는 것이다. 답이 갖는 구조를 예측한다고 해서 꼭 복잡한 것은 아니다. 예제를 손으로 풀어보면 두 숫자 a<b에 대해 a에 대응되는 숫자가 b에 대응되는 숫자보다 커서는 안 된다는 사실을 알 수 있다.

예를 들어 1을 7로 바꾸고 9를 6으로 바꾸는 것은 절대로 최적해가 될 수 없다. $(1-7)^2 + (9-6)^2 = 36+9 = 45 > (1-6)^2+(9-7)^2=25+4=29$ 위와 같이 대응되는 두 숫자를 서로 바꾸면 항상 더 작은 오차를 얻을 수 있기 때문이다. 이것을 일반화 하면 다음과 같다.

주어진 수열을 정렬하면, 같은 숫자로 양자화되는 숫자들은 항상 인접해 있다.

이렇게 생각하면 이 문제를 해결하는 방법이 보인다. 우선 입력에 주어지는 수들을 정렬한 뒤, 인접한 숫자끼리 묶음으로 적절히 분할하고, 각 묶음을 한 숫자로 표현해서 오류를 최소화하는 것이다. 오차 제곱의 합은 각 숫자의 순서가 변하더라도 상관없기 때문에 이와 같이 풀 수 있다.

{1, 4, 6, 744, 755, 777, 890, 897, 902} → {1, 4, 6}, {744, 755, 777}, {890, 897, 902}

따라서 이 문제는 주어진 수열을 s개의 묶음으로 나누는 문제가 된다. 이것은 비교적 쉽게 재귀적으로 해결할 수 있다. 매 재귀 호출마다, 첫 묶음의 크기가 얼마일지를 결정하면 된다. 첫 묶음의 크기를 x라고 한다면 이제 나머지 n-x 개의 숫자를 s-1개의 묶음으로 나누면 된다. 이 때 나머지 s-1 묶음의 오차 합이 최소여야 전체도 최소 오차이기 때문에 최적 부분 구조 또한 성립한다.

from 번째 이후의 숫자들을 parts개의 묶음으로 묶을 때, 최소 오차 제곱 합을 반환하는 함수 quantize(from, parts)가 있다고 하자. parts개의 묶음 중 첫 번째의 크기는 1 이상 n-from 이하의 값이므로, 이들을 각각 다 계산하면 된다. 첫 번째 묶음의 크기가 size 일 때 최소 오차는 minError(from, from + size -1) + quantize(from + size, parts - 1)이 된다. (여기서 minError(a, b)는 a 번째 숫자부터 b 번째 숫자까지를 하나의 수로 표현했을 때 최소 오류를 반환 한다고 하자.

따라서 다음과 같은 점화식이 성립한다.

$$
quantize(from, parts) = \underset{size = 1}{\overset{x-from}{min}} [minError(from, from+size-1) + quantize(from+size, parts-1)]
$$

지금까지 설명한 동적 계획법 알고리즘의 구현은 다음과 같다. 시간복잡도는 부분 문제의 수 $O(ns)$에 각 부분 문제의 답을 계산하는 데 드는 시간 $O(n)$을 곱한 $O(n^2s)$ 가 된다. minError()의 시간복잡도는 $O(1)$이다.

const int INF = 987654321;
// A[] : 양자화해야 할 수열, 정렬한 상태
// pSum[] : A[]의 부분합을 저장한다. pSum[i]는 A[0] .. A[i]의 합
// pSqSum[] : A[] 제곱의 부분합을 저장한다. pSqSum[i]는 A[0]^2 .. A[i]^2의 합
int n;
int A[101], pSum[101], pSqSum[101];
// A를 정렬하고 각 부분합을 계산한다.
void precalc() {
    sort(A, A+n);
    pSum[0] = A[0];
    pSqSum[0] = A[0] * A[0];
    for(int i = 1; i < n; ++i) {
        pSum[i] = pSum[i-1] + A[i];
        pSqSum[i] = pSqSum[i-1] + A[i] * A[i];
    }
}
// A[lo] .. A[hi] 구간을 하나의 숫자로 표현할 때 최소 오차 합을 계산한다.
int minError(int lo, int hi) {
    // 부분합을 이용해 A[lo] ~ A[hi]까지의 합을 구한다.
    int sum = pSum[hi] - (lo == 0 ? 0 : pSum[lo-1]);
    int sqSum = pSqSum[hi] - (lo == 0 ? 0 : pSqSum[lo-1]);
    // 평균을 반올림한 값으로 이 수들을 표현한다.
    int m = int(0.5 + (double)sum / (hi - lo + 1));
    // sum (A[i]-m)^2를 전개한 결과를 부분 합으로 표현
    int res = sqSum - 2 * m * sum + m * m * (hi - lo + 1);
    return ret;
}
int cache[101][11];
int quantize(int from, int parts) {
    // 기저 사례 : 모든 숫자를 다 양자화 했을 때
    if(from == n) return 0;
    // 기저 사례 : 숫자는 아직 남았는데, 더 묶을 수 없을 때 아주 큰 값을 반환한다.
    if(parts == 0) return INF;
    int& ret = cache[from][parts];
    if(ret != -1) return ret;
    ret = INF;
    // 조각의 길이를 변화시켜 가며 최소치를 찾는다.
    for(int partSize = 1; from + partSize <= n; ++partSize) {
        ret = min(ret, minError(from, from + partSize - 1) + quantize(from + partSize, parts - 1));
    }
    return ret;
}