[Algorithm Strategies] 3-8. 동적 계획법

구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다.

📕 목차

1. 도입
2. 와일드카드 (문제 ID: WILDCARD, 난이도: 중)
3. 전통적인 최적화 문제들
4. 합친 LIS (문제 ID: JLIS, 난이도: 하)
5. 원주율 외우기 (문제 ID: PI, 난이도: 하)
6. Quantization (문제 ID: QUANTIZE, 난이도: 중)
7. 경우의 수와 확률
8. 비대칭 타일링 (문제 ID: ASYMTILING, 난이도: 하)
9. 폴리오미노 (문제 ID: POLY, 난이도: 중)
10. 두니발 박사의 탈옥 (문제 ID: NUMB3RS, 난이도: 중)

---

1. 도입

 

• 중복되는 부분 문제
• 메모이제이션을 적용할 수 있는 경우
• 메모이제이션 구현 패턴
• 외발 뛰기 (문제 ID: JUMPGAME, 난이도: 하)
• 동적 계획법 레시피

 

Dynamic Programming이라는 말은 최적화 문제를 연구하는 수학 이론에서 비롯했다고 한다.

그래서 동적 프로그래밍이 아니라 동적 계획법이라 부르는 게 맞다.

(더 골 때리는 건 동적 계획법 고안자인 Bellman은 dynamic이란 단어가 멋있어서 선택...역시 알고리즘 연구하는 사람 중에 정상인 없다.)

 

📌 중복되는 부분 문제

🟡 분할 정복과 차이

• 큰 의미에서는 같지만, 문제를 다누는 방식에서 다르다.
  • 동적 계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는 데 사용될 수 있다.
  • 한 번 계산한 부분 문제의 결과를 재활용한다.
• 캐시(cache) : 이미 계산한 값을 저장해두는 메모리 장소
• 중복되는 부분 문제(overlapping subproblems) : 두 번 이상 계산되는 부분 문제

 

🟡 조합 폭발(Combinatorial Explosion)

(좌) 서로 연관이 없는 부분 문제 / (우) 서로 의존하고 있는 부분 문제

• 오른쪽처럼 나눠진 각 문제들이 같은 부분 문제에 의존하는 경우, 중복 횟수는 분할의 깊이가 깊어질 수록 지수적으로 증가한다.
  • 조합 폭발 : 알고리즘 실행 시간이 조합 함수에 따라 폭발적으로 증가하는 현상
• 가장 유명한 예로 이항 계수(binomial coefficient)의 계산이 있다.

 

🟡 이항 계수(binomial coefficent)

• \(\begin{pmatrix} n \\ k \end{pmatrix} = nCk = \frac{n!}{(n-k)!k!} \) (단, 0 ≤ k ≤ n)
  • \( \begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n \\ n-k \end{pmatrix} \)
  • \( \begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n-1 \\ k \end{pmatrix} + \begin{pmatrix} n-1 \\ k-1 \end{pmatrix} \)
  • \( \sum_{n}^{k=0}\begin{pmatrix} n \\ k \end{pmatrix} = 2^{n} \)
• n개의 서로 다른 원소 중에서 k개의 원소를 순서없이 골라내는 방법의 수를 탐색해야 한다.

 

// 코드 8.1 재귀 호출을 이용한 이항 계수의 계산

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);
}

• 점화식을 그대로 적용하면 중복되는 부분 문제가 빈번히 발생한다.

 

🚨 기하급수적으로 증가하는 연산량

• bino(n, [n/2])의 n이 1 증가할 때마다 호출이 약 2배 정도 증가한다.
• 입력인 n과 k가 정해져 있을 때 bino(n, k)의 반환값이 일정하다는 사실을 이용해 중복 계산을 제거할 수 있다.

 

🟡 메모이제이션(Memoization)

// 코드 8.2 메모이제이션을 이용한 이항 계수의 계산

// -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);
}

n	2	3	4	5	...	18	19	...	24	25
bino() 호출 횟수	3	5	11	19	...	97239	184755	...	5408311	10400599
bino2() 호출 횟수	3	5	8	11	...	99	109	...	168	181

• 함수의 결과를 저장하는 장소(cache)를 마련하고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법
• n, k 조합의 입력에 대한 반환값을 cache 배열에 저장하고, 계산된 값이 존재하는지 먼저 확인하도록 한다.

 

📌 메모이제이션을 적용할 수 있는 경우

int counter = 0;
int count() {
    return counter++;
}

• 참조적 투명 함수(referential transparent function)만 가능하다.
  • 입력이 고정되어 있을 때, 그 결과가 항상 같은 함수

 

📌 메모이제이션 구현 패턴

💡 이 패턴을 꼭 따를 필요는 없지만, 자신만의 방식을 하나 만들어 일관되게 사용하라

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

위와 같은 재귀함수가 있고, someObscureFunction()은 연산 비용이 비싼 참조적 투명 함수라 가정한다.

이를 메모이제이션 하면 아래 코드처럼 된다.

 

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

// 전부 -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로 초기화 한다.
  • -1이면 아직 값이 갱신되지 않았음을 나타낼 수 있다.
• ret는 cache[a][b]에 대한 참조형(reference)이다.
  • cache[a][b]라고 번거롭게 사용하지 않고, 참조라를 사용하면 편하다.
• memset()과 같은 초기화 함수를 기억하면 좋다.
  • 단, memset은 아주 제한적인 경우에만 사용할 수 있으므로 주의하라
    1. 1Byte 변수(char, unsigned char 등)를 제외한 변수를 초기화할 때는 0 이외의 값으로 초기화해선 안 된다.
    2. new, malloc 등을 이용하여 동적으로 배열을 생성하는 변수가 있는 struct, class에서는 사용하지 마라
    3. CString은 절대 memset으로 초기화해선 안 된다.
    4. virtual function을 가지고 있는 sturct, class에서도 쓰지 마라
  • ex. memset(&n, 1, sizeof(int)) ⇒ n = [00000001000000010000000100000001] = 16,843,009

 

⏲️ 시간 복잡도 분석

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

위 식을 bino2()에 적용해보면 다음과 같다.

1. k의 최대치는 n이므로 bino2(n, k)를 계산할 때 최대 O(n^2)의 부분 문제의 수를 만날 수 있다.
2. 각 부분 문제를 계산하는데 걸리는 시간은 O(1)이다.
3. 따라서, bino2(n, k)의 시간 복잡도는 O(N^2)이다.

 

O(n·k)가 맞지 않느냐고 생각할 수도 있다.

좀 더 직관적으로 이해해보기 위해 반복문으로 코드를 재구성하면 다음과 같다.

// 파스칼의 삼각형
1
1   1
1   2   1
1   3   3   1 
1   4   6   4  1 
1   5  10  10  5  1

// 반복 문으로 구현해본다면

int cache[30][30];
int binoLoop(int n, int k) {
    for (int i=0; i<=n; i++) for (int j=0; j<=min(i, k); j++)
        cache[i][j] = (j==0 || j==i) ? 1 : cache[i-1][j-1] + cache[i-1][k];
    return cache[n][k];
}

i	j 반복 횟수
0	1
1	2
⋯	⋯
k	k+1
k + 1	k+1
⋯	⋯
n	k+1

이 때, k+1은 (n-k+1)번 반복하므로,

$$ \begin{align} W(n, k) &= 1 + 2 + 3 + \cdots + k + (k+1) + \cdots + (k+1) \\&= \frac{k(k+1)}{2} + (n-k+1)(k+1) \\&= \frac{(2n-k+2)(k+1)}{2} \in O(n*k) \end{align} $$

이 성립한다.

 

그런데 k의 상한값을 생각해보면 어차피 n^2꼴이 나오게 되므로 O(n^2)으로 봐도 무방하다.

 

📌 외발 뛰기 (문제 ID: JUMPGAME, 난이도: 하)

🟡 문제

algospot.com :: JUMPGAME

 

🌱 내 아이디어

책에서는 재귀 호출을 썼는데, 반복문 긁으면 O(N^2)으로 쉽게 풀 수 있는 문제기도 하다.

(0, 0)은 출발점이므로, 숫자만큼 떨어진 우측과 아래측 인덱스를 true로 바꿔준다. (true : 해당 지점에 도달할 수 있다는 의미)

그 다음부터는 현재 위치가 false라면 건너뛰고, true라면 똑같이 숫자만큼 떨어진 우측과 하단 인덱스에 true를 체크해준다. (범위를 벗어나면 패스)

최종적으로 (n-1, n-1)이 true면 "YES"를 출력하면 된다.

 

그렇다. 재귀를 쓰면 시간이 좀 더 빨라지긴 하겠지만, DP 없이도 쉽게 해결할 수 있는 문제였다.

 

1️⃣ 재귀 호출에서 시작하기

// 코드 8.4 외발 뛰기 문제를 해결하는 재귀 호출 알고리즘

int n, board[100][100];
bool jump(int y, int x) {
    // 기저 사례: 게임판 밖을 벗어난 경우
    if (y >= n || x >= n) return false;
    // 기저 사례: 마지막 칸에 도착한 경우
    if (y == n - 1 && x == n - 1) return true;
    int jumpSize = board[y][x];
    return jump(y + jumpSize, x) || jump(y, x + jumpSize);
}

• 동적 계획법 알고리즘을 만드는 첫 단계는 해당 문제를 재귀적으로 해결하는 완전 탐색 알고리즘을 만들어보면 된다.
  • \(jump(y,x)=(y,x)\)부터 맨 마지막 인덱스까지 도달할 수 있는지 여부를 반환한다.
  • 아래쪽 \(jump(y+jumpSize, x)\), 오른쪽 \(jump(y, x+jumpSize)\)을 호출하면 된다.
• 이 문제는 경로를 묻는 게 아니고, 단순히 가능성을 따지고 있으므로 위 방식은 중복 부분 문제가 너무 많아진다.

 

2️⃣ 메모이제이션 적용하기

// 코드 8.5 외발 뛰기 문제를 해결하는 동적 계획법 알고리즘

int n, board[100][100];
int cache[100][100];
int jump2(int y, int x) {
    // 기저 사례
    if (y >= n || x >= n) return 0;
    if (y == n - 1 && x == n - 1) return 1;
    // 메모이제이션
    int& ret = cache[y][x];
    if (ret != -1) return ret;
    int jumpSize = board[y][x];
    return ret = (jump2(y + jumpSize, x) || jump2(y, x + jumpSize));
}

• 전형적인 Bottom up 방식의 dp 해법이다.
  • (0,0)에서 일단 기저 사례까지 jump하고, 거슬러 오면서 true, false를 판가름한다.
  • 이미 탐색이 끝난 위치에 대해서는 저장된 값을 반환받으면 그만이다.

 

3️⃣ 다른 해법

7부에 나오는 그래프로 모델링해보면 아주 간단한 문제가 된다고 하는데, 그게 내가 얘기한 아이디어 같다.

 

📌 동적 계획법 레시피

1. 주어진 문제를 완전 탐색을 이용해 해결한다.
2. 중복된 부분 문제를 한 번만 계산하도록 memoization을 적용한다.

 

---

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

 

• 문제
• *가 문제로다
• 중복되는 부분 문제
• 다른 분해 방법

 

📌 문제

algospot.com :: WILDCARD

 

📌 *가 문제로다

여기서 생각해봐야 할 점은 *가 된다. (?는 쉬우니까 패스)

기준이 애매하다는 것이 걸린다. * 다음에 출연하는 글자가 나올 때까지 대응시키는 방식을 떠올릴 수도 있다.

하지만 다음 경우에 문제가 꼬일 것이다.

• pattern : *bb*
• input : babbbc

 

// 와일드카드 패턴 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;
    ..
}

• 주어진 패턴이 m개의 *를 포함한다면, 부분 문제를 m+1개로 쪼갤 수 있다.
  • 패턴 t*l?*o*r?ng*s → 부분 문제 {*t, l?*, o*, r?ng*, s} 
  • 입력값에 대해 각각의 조각이 대응되는 경우 별로 재귀를 호출하여 나머지 패턴 조각에 대응 여부를 확인하면 된다.
• 패턴을 쪼개지 않고, 위의 코드처럼 현재 위치를 가리키는 "커서"를 옮길 수도 있다.

 

// 코드 8.6 와일드카드 문제를 해결하는 완전 탐색 알고리즘

// 와일드카드 패턴 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;
}

이전의 미완성 코드를 보완한 내용이다.

1. s[pos]와 w[pos]가 대응되지 않는 경우
   • 대응 실패한 경우 → *인지 판단
2. w 끝에 도달한 경우
   • 패턴에 *이 하나도 없는 경우
   • 패턴과 문자열의 길이가 정확히 같아야만 한다.
3. s 끝에 도달한 경우
   • 패턴은 남았으나, 문자열이 끝난 경우
   • 패턴이 전부 *로 구성되어 있다면 가능하지만, 그 외는 모두 false를 리턴한다.
   • (4)를 호출할 때, 자동으로 처리된다. → 결국에 (2)에 걸려 true를 반환하면 (4)에서 검증된다.
4. w[pos]가 *인 경우
   • match(w', s')를 호출해서 남은 문자열까지의 모든 가능성을 조사한다.

 

📌 중복되는 부분 문제

위 알고리즘의 문제점은 너무 적나라하다.

 

특히 패턴 ******a에 문자열 aaaaaaaaab 같은 경우가 들어오면 절대로 조합이 불가능함에도

완전 탐색 알고리즘은 a들을 *에 대응시키는 수많은 경우의 수를 하나하나 검사하고 있게 된다.

 

// 코드 8.7 와일드카드 문제를 해결하는 동적 계획법 알고리즘

// -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[w] == 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 (matchMemoized(w + 1, s + skip))
                return ret = 1;
    // 3. 이 외의 경우에는 모두 대응되지 않는다.
    return ret = 0;
}

• w와 s의 종류는 제한되어 있다.
  • w는 언제나 패턴 W의 suffix고, s는 언제나 파일명 S의 suffix가 된다.
  • 문자열 길이 제한이 각각 100이므로, 완전 탐색처럼 101*101 이상 호출되는 것은 부분 문제가 반드시 존재함을 의미한다.
• w는 언제나 W의 접미사이므로, w의 길이가 결정(w == W.size())되면 w 또한 결정된다.
• 문자열이 아닌 W, S의 현재 위치를 가리키는 w, s를 인자로 전달한다.

 

만약 이해가 안 간다면, 아래의 cache 테이블을 직접 채워보면서 동작을 확인해보면 된다.

	a	a	a	a	a	a	b
*
*
*
*
a

 

⏲️ 시간 복잡도

(부분문제의 수) * (부분 문제 하나 풀 때 반복 횟수)

 

패턴과 문자열 길이가 모두 n이면, 부분문제의 수는 n^2개가 된다.

한 문제 당, 반복문이 쓰이고 있으므로 이 알고리즘의 시간 복잡도는 O(N^3)이 된다.

 

📌 다른 분해 방법

재귀 함수 내부의 두 개의 반복문을 모두 제거하면 시간 복잡도를 O(N^2)으로 줄일 수 있다.

 

🟡 첫 *을 찾는 while문

// W[w]와 S[s]를 맞춰나간다
while(s < S.size() && w < W.size() && (W[w] == '?' || W[w] == S[s]))) {
    ++w;
    ++s;
}

if (s < S.size() && w < W.size() && (W[w] == '?' || W[w] == S[s])))
    return ret = matchMemozied(w+1, s_1);

• w, s를 1씩 증가시키지 않고, 재귀 호출로 탐색이 끝난 결과를 바로 가져올 수 있다.

 

🟡 *가 몇 글자 대응하는지 탐색하는 for문

// 4. *를 만나서 끝난 경우: *에 몇 글자를 대응해야 할지 재귀 호출하면서 확인한다.
if (W[w] == '*') {
    if (matchMemoized(w+1, s) || (s < S.size() && matchMemoized(w, s+1)))
        return ret = 1;
}

• for문을 두 개의 재귀로 나눈다.
  • *에 아무 글자도 대응시키지 않은 경우
  • 한 글자를 더 대응시킨 경우

 

그러면 대충 이런 느낌으로 결과를 탐색하게 된다!

 

---

3. 전통적인 최적화 문제들

 

• 삼각형 위의 최대 경로 (문제 ID: TRIANGLEPATH, 난이도: 하)
• 최적 부분 구조(Optimal Substructure)
• 최대 증가 부분 수열 (문제 ID: LIS, 난이도: 하)
• 최적화 문제 동적 계획법 레시피

 

동적 계획법은 처음에 최적화 문제 해답을 빠르게 구하기 위해 고안되었다.

물론 이항 계수처럼 최적화 문제가 아닌 곳(두 개 이상의 답 중에 가장 좋은 것을 선택하는 게 아니므로)에서도 쓰일 수 있다.

최적화 문제에서도 완전 탐색에서 시작하지만, 특정 성질이 성립할 경우 memoization을 좀더 효율적으로 사용할 수 있다.

 

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

🟡 문제

algospot.com :: TRIANGLEPATH

그냥 DFS 써서 bottom up 방식으로 쉽게 해결할 수 있는 문제.

 

1️⃣ 완전 탐색으로 시작하기

그냥 아래와 오른쪽 아래로 향하는 재귀를 계속해서 호추해주면 된다.

그래도 좀 있어보이게 점화식을 가져다 놓으면 이렇다.

\( pathSum(y, x, sum) \)은 현재 위치 (y, x)이고, 지금까지 만난 수의 합이 sum일 때 최대합을 반환한다.

$$ \begin{align} path1(y, x, sum) = max\left\{\begin{matrix} path(y+1, x, sum+triangle[y][x]) \\ path(y+1, x+1, sum+triangle[y][x])\end{matrix}\right. \end{align} $$

 

물론 n개의 가로줄이 있을 때, 가능한 경로의 수가 2^(n-1)이므로 합리적이지 않다.

 

2️⃣ 무식하게 메모이제이션 적용하기

// 코드 8.8 삼각형 위의 최대 경로 문제를 푸는 메모이제이션 코드 (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, sum), path1(y + 1, x + 1, sum));
}

• Top down 방식으로 최대합을 조합하면서 내려가는 방식
• 두 가지 문제점이 존재한다.
  1. cache 크기가 입력값에 의존하므로 사용해야 하는 메모리가 너무 크다.
  2. 내려오는 결과에 따라 다 다른 합을 가지므로 중복이 없다. 사실상 완전 탐색과 다를 바가 없다.

책에서는 멀쩡해보인다고 하지만, 언뜻 보기에도 멀쩡하지가 않다.

 

3️⃣ 입력 걸러내기

// 코드 8.9 삼각형 위의 최대 경로 문제를 푸는 동적 계획법 알고리즘 (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];
}

책에서 나름 친절하게 설명해보려고 길게 풀어놨는데, 요점은 Top down을 쓸 때가 있고, Bottom up을 쓸 때가 따로 있다는 얘기다.

 

예전에 자료구조 수업에서 누가 나한테 이 내용으로 질문을 했던 기억이 있다.

왜 Top down 방식과 Bottom Up 방식 모두 답은 구하는데, 전자로 구했을 때 훨씬 동작이 느리냐는 거였다.

그 때도 책을 읽기 전과 같은 답변을 했었는데, 그게 딱 이 케이스였다.

 

위 예시의 경우 전체 경로의 최대 합이 아닌, 부분 문제에 대한 결과를 차곡차곡 쌓아 최종적으로 최대합을 구하는 게 효율적이다.

왜냐면 (y, x)에서 맨 아래줄까지 내려가는 최대 경로는 sum과 관련이 없기 때문이다.

 

$$ \begin{align} path2(y, x) = triangle[y][x] + max\left\{\begin{matrix} path2(y+1, x) \\ path(y+1, x+1)\end{matrix}\right. \end{align} $$

 

따라서 이 알고리즘의 부분 문제 수 N^2개와 상수 시간 계산이 걸리는 것으로 판단했을 때, 시간 복잡도는 O(N^2)이 된다.

 

📌 최적 부분 구조(Optimal Substructure)

💡 각 부분 문제의 최적해만으로 전체 문제의 최적해를 구할 수 있을 때 성립한다.

• 최적화가 가능했던 이유
  • sum이라는 정보가 아무런 의미가 없음을 알았기 때문이다.
  • sum은 지금까지 풀었던 조각들에 대한 정보를 주는 입력인데, 앞으로 남은 조각들을 푸는데 도움이 안 된다.
• 더 작은 문제의 최적해로 전체 문제의 최적해를 구할 수 없을 때, 최적 부분 구조가 존재하지 않는다고 한다.
  • 경로 A(대전 → 부산) : 통행 시간 2시간, 통행료 1만 원
  • 경로 B(대전 → 부산) : 통행 시간 1시간, 통행료 2만 원
  • 위 두 경우만 놓고 보면 최적 경로는 언제가 경로 B가 된다.
  • 만약 경로 C(서울→대전) 통행료가 1만 5천원이고 3만 원이라는 비용 제한이 걸리면 경로 A를 택해야 한다. 
• 최적 부분 구조가 직관적이지 않은 경우 대개 귀류법 혹은 대우를 이용해 증명한다.

 

📌 최대 증가 부분 수열 (문제 ID: LIS, 난이도: 하)

🟡 문제

algospot.com :: LIS

와 ㅋㅋㅋㅋㅋ 진짜 오랜만에 보는 문제다.

코테 처음 공부할 때 1달 차 쯤에 풀었던 문제 같은데, 간만에 보니 추억이 새록새록

이 문제는 조건에 따라 푸는 방법이 워낙 다양해서 재밌다.

 

1️⃣ 완전 탐색에서 시작하기

// 코드 8.10 최대 증가 부분 수열 문제를 해결하는 완전 탐색 알고리즘

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;
}

2중 반복으로 긁어버리면 가장 단순 무식한 알고리즘을 구현할 수 있다.

..라고 쓰고 넘어갔었는데, 그것보다도 더 무식한 알고리즘을 만들어 놨네.

너무 과하게 꼬아놓은 느낌이 강하다.

 

2️⃣ 입력 손보기

// 코드 8.11 최대 증가 부분 수열 문제를 해결하는 동적 계획법 알고리즘(1)

int n;
int cache[100], S[100];
// S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환한다.
int lis2(int start) {
    int& ret = cache[start];
    if (ret != -1) return ret;
    // 항상 S[start]는 있기 때문에 길이는 최하 1
    ret = 1;
    for (int next = start + 1; next < n; ++next)
        if (S[start] < S[next])
            ret = max(ret, lis2(next) + 1);
    return ret;
}

• 기존의 정수 배열 입력을 전역으로 빼고, 인덱스 값을 인자로 받게 바꾸었다. (memoziation 적용을 위해)
• 기존의 A의 정의는 항상 다음 두 가지 중 하나만 된다.
  1. 원래 주어진 수열 S가 되는 경우
  2. 원래 주어진 수열의 원소 S[i]에 대해, S[i+1 ...] 부분 수열에서 S[i]보다 큰 수들만을 포함하는 부분 수열
     
     • S[i] 이전에 선택된 수들은 어차피 마지막에 선택한 수보다 작으므로 2번 조건으로 모두 만족한다.
     • 2번 조건에 포함되는 A는 S와 1대1 대응이 된다.
     • 따라서, lis(start)를 S[start]에서 시작하는 부분 증가 수열 중 최대의 길이로 볼 수 있다.
• 별도의 기저 사례가 없고, 마찬가지로 O(n^2)의 시간 복잡도를 가진다.

사실 이 문제를 O(N^2)으로 풀 거 같으면 이중 반복을 쓰는 게 더 편하다.

 

3️⃣ 시작 위치 고정하기

lis2()를 호출할 때 어떻게 해야할지에 대한 내용이다.

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

 

항상 증가하는 부분 수열 시작 위치를 지적해주어야 하므로, 각 위치를 순회하도록 할 수 있다.

 

// 코드 8.12 최대 증가 부분 수열 문제를 해결하는 동적 계획법 알고리즘(2)

int n;
int cache[101], S[100];
// S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환한다.
int lis3(int start) {
    int& ret = cache[start + 1];
    if (ret != -1) return ret;
    // 항상 S[start]는 있기 때문에 길이는 최하 1
    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;
}

그마저도 귀찮다면 S[-1] 영역을 (논리적으로) 확장시키면 된다.

최종 결과는 list3(-1) - 1이 되어야 한다. (S[-1]은 가상의 영역이므로)

인덱스 값에 유의해서 써야 한다.

 

4️⃣ 더 빠른 해법

[Python] 12015 - 가장 긴 증가하는 부분 수열 2 (골드2)

O(nlgn)으로 해결하는 알고리즘은 좀 재밌는 발상을 가진다.

최대 길이만 구하면 되므로, 최종적으로 구한 최대 수열의 순서까지는 보장할 필요가 없다.

"아무튼 빨랐죠?"같은 느낌.

 

설명은 해당 문제를 보고 이해하는 게 나을 것이다. (와, 근데 저 문제 푼 지도 1년이 넘었네..)

책에 있는 설명이 오히려 어려웠던 것 같다.

 

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

모든 문제를 해결해주지는 않지만, 대략적인 지침은 될 수 있을 것이다.

1. 모든 답을 만들어 보고 그 중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계한다.
2. 전체 답의 점수가 아닌, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꾼다.
3. 재귀 호출 입력에 이전의 선택에 관련된 정보는 꼭 필요한 것을 남기고 지워야 한다.
   • 최적 부분 구조가 성립하면 완전히 없앨 수도 있다.
   • 입력의 종류가 적어질 수록 중복된 부분 문제가 많아지므로, memoization을 최대 한도로 활용 가능하다.
4. 입력이 배열이나 문자열이면 적절히 바꿔라
5. memoization을 적용한다.

 

✒️ 삼각형 위의 최대경로 문제에 레시피 대입해보기

1. 모든 경로를 만들어, 전체 합 중 최대치를 반환하는 전탐색 알고리즘 path1()을 만들었다.
2. 전체 경로 최대합이 아닌, (y, x) 이후의 최대 합만을 바꾸도록 만들었다.
3. 이전에 선택한 정보인 sum을 입력받을 필요가 없어졌으므로 제거했다. (최적 부분 구조 성립)
4. 필요 없던 항목
5. memoization 적용

 

---

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

 

• 문제
• 탐욕법으로는 안 된다
• 비슷한 문제와 비교

 

📌 문제

algospot.com :: JLIS

 

📌 탐욕법으로는 안 된다

처음 보고 '두 수열의 LIS를 찾고 합치면 되지 않을까'

그렇다면 두 LIS를 합치는 시간을 줄여야 하는 건가 싶었는데, 애초에 성립이 안 된다.

 

10 20 30 1 2
10 20 30

입력이 이렇게 들어와버리면 '1 2 10 20 30'을 택해야 하는데, 이는 수열 A의 LIS가 아니기 때문이다.

 

📌 비슷한 문제와 비교

LIS 문제의 lis3()의 정의는 아래와 같았다.

• lis3(start) = S[start]에서 시작하는 LIS

수열이 2개로 늘었으니, 재귀 함수 또한 두 개의 입력을 받아야 할 것이다.

• jlis(indexA, indexB) = A[indexA]와 B[indexB]에서 시작하는 JLIS
• indexA ≤ indexB 라고 가정한다.

어떤 indexA와 indexB에서 JLIS를 찾아냈다고 한다면, 

• 다음 숫자는 A[indexA+1] (혹은, B[indexB+1]) 이후의 수열 중 max(A[indexA], B[indexB])보다 큰 수 중 하나가 된다.
• A[nextA]를 다음 숫자로 선택한 경우, JLIS 최대 길이는 1 + jlis(nextA, indexB)가 된다.

(말이 어려워서 그렇지, 찬찬히 생각해보면 너무 당연한 말을 하고 있다.)

따라서 아래의 점화식을 구할 수 있다.

• \( jlis(indexA, indexB) = max\left\{\begin{matrix} max_{nextA\in NEXT(indexA)}jlis(nextA, indexB) + 1 \\ max_{nextB\in NEXT(indexB)}jlis(indexA, nextB) + 1 \end{matrix}\right. \)
  • 단, NEXT(indexA)와 NEXT(indexB)는 증가 부분 수열 다음 위치에 올 A와 B 원소의 인덱스

 

// 코드 8.13 합친 LIS 문제를 해결하는 동적 계획법 알고리즘

// 입력이 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 = indexA + 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;
}

위 문제는 입력 범위가 32bit 부호 있는 정수(unsigned int) 전체라고 나와 있다.

따라서 최솟값(입력에 등장하지 않는 임의의 값)으로 초기화 하기 위해서는 64bit 정수의 최솟값을 사용해야 한다.

 

✒️ const long long NEGINF = numeric_limits<long long>::min();

long long 타입에서 가장 작은 음의 무한대를 표현하는 방법
<limits> 헤더에 정의되어 있으며, 보통 DP 등의 알고리즘 초기화나 비교에서 사용한다.

 

---

5. 원주율 외우기 (문제 ID: PI, 난이도: 하)

 

• 문제
• 일만 자리나 외우라고?
• 메모이제이션 적용
• 구현

 

📌 문제

algospot.com :: PI

 

뭐, 대충 3, 4, 5 조각으로 잘랐을 때에 대해서 Bottom up으로 조합을 찾아내면 될 것 같다.

정확히는 (1), (2), (3), (4), (5) case를 판별하는 함수를 정의해두고, 우선 3조각, 4조각, 5조각으로 나누어 재귀를 호출한다.

잘라냈을 때의 부분문제에 대한 난이도를 판단하고, 최소가 되는 경우를 결정하면 된다.

 

📌 일만 자리나 외우라고?

• 테스트 케이스 수 C가 최대 50, 8글자 이상 10,000글자 이하의 숫자가 주어지므로 완전 탐색으로 풀긴 힘들 것이다.
• 답의 하한을 계산해보면 불가능한 이유를 증명할 수 있다.
  1. 문제 규칙에 따라 길이 7인 수열 '1111222'를 자르는 방법은 2가지다.
  2. 따라서 길이 7인 수열이 n개 있으면, 쪼개는 방법이 2^n개가 된다.
  3. 길이 10,000인 수열에는 길이 7인 수열이 1,428개 들어갈 수 있으므로, 이것만 해도 2^(1,428)의 경우가 나온다.

 

📌 메모이제이션 적용

전체 문제의 최적해는 다음 세 경우 중 가장 작은 값이 된다.

1. 길이 3인 조각의 난이도 +3글자를 제외한 나머지 수열에 대한 최적해
2. 길이 4인 조각의 난이도 +4글자를 제외한 나머지 수열에 대한 최적해
3. 길이 5인 조각의 난이도 +5글자를 제외한 나머지 수열에 대한 최적해

이를 점화식으로 표현하면,

$$ \begin{align} memorize(begin) = \overset{5}{\underset{L=3}{min}}(memorize(begin+L) + classify(N_{begin, L})) \end{align} $$

• \(N_{begin, L}\) : N[begin]에서 시작하는 길이 L인 부분 문자열
• classify() 해당 부분 문제의 난이도를 반환하는 함수

 

내 예상이 맞았군 😎

 

📌 구현

// 코드 8.14 원주율 외우기 문제를 해결하는 동적 계획법 알고리즘

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;
    // 등차수열이고 공차가 1 혹은 -1이면 난이도는 2
    if (progressive && abs(M[1] - M[0]) == 1)
        return 2;
    // 두 수가 번갈아 등장하는지 확인한다.
    bool alternating = true;
    for (int i = 0; i < M.size(); ++i)
        if (M[i] != M[i % 2])
            alternating = false;
    if (alternating) return 4; // 두 수가 번갈아 등장하면 난이도는 4
    if (progressive) return 5; // 공차가 1 아닌 등차수열의 난이도는 5
    return 10; // 이 외는 모두 난이도 10
}

int cache[10002];
// 수열 N[begin..]를 외우는 방법 중 난이도의 최소 합을 출력한다.

int memorize(int begin) {
    // 기저 사례: 수열의 끝에 도달했을 경우
    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, memorize(begin + L) + classify(begin, begin + L - 1));
    return ret;
}

그렇게 어려운 구현은 아니니, 쉽게 이해할 수 있다.

난이도를 판정하는 classify()는 번거롭긴 하지만 시간 소모가 큰 작업은 아니므로 효율성보단 구현 용이성과 간결함에 초점을 맞추는 것이 유용하다.

해당 코드의 시간 복잡도는 O(N)이 된다.

 

---

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

 

• 문제
• 하던 대로는 안 된다
• 답의 형태 제한하기
• 한 개의 구간에 대한 답 찾기
• 구현

 

📌 문제

algospot.com :: QUANTIZE

이 문제의 함정은..양자화를 하기 위해서 연속된 수열일 필요가 없었다는 점이다.

풀이가 이해가 안 가서 한참을 봤는데, 연속된 수열에 대해서만 양자화가 가능하단 이야기가 없다. ㅠ

 

📌 하던 대로는 안 된다

이모저모 고민을 해봤는데, 경우의 수가 너무 많아서 어쩔 수 없이 무식한 경우부터 떠올리게 된다.

수열 A를 하나씩 자르고 나머지 수열을 어떻게 표현할 거냐가 관건이 되는데 제법 어렵다.

• quantize(A) : A에 속한 수를 양자화해서 얻을 수 있는 최소 오차 제곱의 합
  • 양자화 하려는 숫자가 '이전'과 겹치면 안된다.
  • '이전'이라는 다른 상태에 영향을 받으므로 최적 부분 조건이 성립하지 않는다.
  • quantize는 이전 숫자들이 어떤 숫자로 양자화 했는지도 파악해야 한다. (매개변수 추가)
• quantize(A, U)
  • U는 한 번 이상 사용한 숫자들의 집합
  • U의 크기가 10이어도, \(\begin{pmatrix} 1000 \\ 10 \end{pmatrix}\)개의 부분 문제가 나온다.
  • 구해야 하는 경우의 수가 너무도 방대하다.

 

📌 답의 형태 제한하기

💡 부분 문제의 개수가 너무 많을 때, 답이 항상 어떤 구조를 가질 것이라 예측하고 강제해봐라

물론 어디까지나 다양한 방법 중 한 가지 테크닉일 뿐이다.

• 두 숫자 a<b에 대해 a에 대응되는 숫자가 b에 대응되는 숫자보다 크면 안 된다.
  • 1을 7로 바꿨는데, 9를 6으로 바꾸면 절대 최적해가 될 수 없다.
  • 대응되는 두 숫자를 바꾸면 언제나 더 작은 오차를 얻을 수 있기 때문이다.
• 즉, 주어진 수열을 정렬하면, 같은 숫자로 양자화되는 순자들은 항상 인접해있다.
  • 입력된 수열을 정렬 → 인접한 숫자끼리 묶음으로 적절히 분할 → 양자화 (오류 최소화)
  • 어차피 오차 제곱의 합은 각 숫자의 순서가 변하더라도 상관이 없다.
• 따라서 이 문제는 수열을 s개의 묶음으로 나누는 문제가 된다.
  • 첫 묶음을 정하면 나머지 s-1 묶음의 오류 합이 최소여야 전체도 최소 오류가 된다.
  • 최적 부분 구조가 성립하게 되었다.
• \( quantize(from, parts) = \overset{n-from}{\underset{size=1}{min}}[minError(from, from+size-1) + quantize(from+size, parts-1)]\)
  • quantize(from, parts) : from번째 이후 숫자들을 parts개의 묶음으로 묶을 때, 최소 오류 제곱 합을 반환하는 함수
  • 첫 번째 묶음의 크기(size)는 1이상 n-from 이하의 값을 가진다.
  • minError(a, b) : a부터 b번째 숫자까지를 하나의 수로 표현했을 때의 최소 오류 반환 함수
  • 따라서 첫 번째 묶음 크기(size)일 때, 최소 오류는 \(minError(from, from+size-1) + quantize(from+size, parts-1) \) 

변형에 의해 quantize()가 이전 묶음 정보를 전혀 받지 않으므로 최적 부분 조건이 성립한다.

 

📌 한 개의 구간에 대한 답 찾기

그럼 대체 minError()는 어떻게 구현할 것인가? 우선 minError는 다음과 같은 기능을 담당한다.

1. 주어진 구간을 어떤 수로 표현해야 할지 결정한다.
2. 결정한 수 m으로 해당 구간을 표현했을 때의 오차를 계산한다.

(시간제한이 널널해서 단순하게 구현해도 풀리긴 한다.)

 

1️⃣ 주어진 구간을 어떤 수로 표현할지 결정하는 방법

가장 무식한 방법은 {74, 81, 96, 100}의 부분집합에서 74부터 100까지 모든 숫자로 계산해보는 것이다.

• n^(3) * 1,000 에 비례하는 반복수가 나온다.
• 하지만 대부분 구간 길이가 n보다 짧고, 사용 가능 종류 수가 1,000보다 작아서 시간 안에 나올 수도 있다.

하지만 좀 더 간단하고, 빠른 알고리즘을 원한다면 미분을 사용하면 된다.

길이 2 이상인 구간 수열 A[a⋯b]에 대한 오차 제곱합을 최소화하는 m을 아래와 같이 구할 수 있다.

• \(\sum_{i=a}^{b}(A[i]-m)^{2}=(b-a+1)*m^{2}-2(\sum_{i=a}^{b}A[i])m+\sum_{i=a}^{b}(A[i]^{2})\)
  • m에 대한 2차식 (그냥 오차 제곱합을 풀었을 뿐이다.)
  • 2차항 계수가 양수이므로 미분으로 최소점을 찾아낼 수 있다. (기울기가 0인 지점)

위 식을 m에 대해 미분하면,

• \(1*(b-a+1)*m-2(\sum_{i=a}^{b}A[i])\)
• \(m = \frac{\sum_{i=a}^{b}A[i]}{b-a+1}\)

즉, 모든 값의 평균을 이용해서 오차를 최소화 할 수 있다!

이 과정은 보통 O(n) 과정이 걸리지만, 부분 합 기법을 적용하면 O(1)만에 계산 가능하다.

• A의 부분합 : \(pSum[k] = \sum_{i=0}^{k}A[i] \)
• A[a]부터 A[b]까지 부분합 : \(pSum[b]-pSum[a-1]=\sum_{i=0}^{b}A[i]-\sum_{i=0}^{a-1}A[i]=\sum_{i=a}^{b}A[i]\)
  • a=0일 때 예외
  • 해당 결과를 (b-a+1)로 나누면 된다.

 

2️⃣ 오차 제곱의 합 구하기

무식하게 구할 수도 있으나, 오차 제곱을 구하는 식을 다시 전개해볼 수 있다.

• \(\sum_{i=a}^{b}(A[i]-m)^{2}=(b-a+1)*m^{2}-2(\sum_{i=a}^{b}A[i])m+\sum_{i=a}^{b}(A[i]^{2})\)
  • 시간이 오래 걸리는 A[]^2과 A[]는 m과 관련이 없다.
  • 한 번 더 부분 합을 사용해 O(1)으로 식을 계산할 수 있다.
  • A의 부분합 : \(pSum[k] = \sum_{i=0}^{k}A[i] \)

 

📌 구현

// 코드 8.15 Quantization 문제의 구현

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 ret = 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;
}

 

⏲️ 시간 복잡도

• \(O(N^{2}S)\)
  • minError(a, b) : O(1)
  • 부분 문제의 수 O(NS)
  • 각 부분 문제를 계산하는 시간 O(N)

 

---

7. 경우의 수와 확률

 

• 오버플로에 유의하기
• 타일링 방법의 수 세기 (문제 ID: TILING2, 난이도: 하)
• 삼각형 위의 최대 경로 개수 세기 (문제 ID: TRIPATHCNT, 난이도: 중)
• 우물을 기어오르는 달팽이
• 장마가 찾아왔다 (문제 ID: SNAIL, 난이도: 하)
• 경우의 수 계산하기 레시피

 

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

 

📌 오버플로에 유의하기

• Modulo 연산을 자주 사용한다
  • 보통 경우의 수를 구하는 문제는 입력에 대해 답이 지수적으로 증가한다. (아니라면 완전탐색 쓰지 뭐하러 DP?)
  • 32-bit 정수형의 한계를 뛰어넘는 경우가 많다. 

 

✒️ Modulo Operation

 

정수론에서 정수의 합과 곱을 어떤 주어진 수(MOD)의 나머지에 대하여 정의하는 방법

• modulo
  • modulo operation에서 연산자를 의미한다. (보통 mod라고 표현, % 연산자가 이 역할을 수행)
• modulo operation
  • A mod B
• modulus
  • 나누는 수(제수)
  • A mod B에서 B가 modulus

수학 얘기와 증명 단계는 모두 건너뛰고, Modulo 사칙 연산에 대해서 아래 식이 성립한다.

• 덧셈 : \((a+b) % M = ((a % M) + (b % M)) % M \)
• 뺄셈 : \((a-b) % M = ((a % M) - (b % M)) % M  \)
• 곱셉 : \((a*b) % M = ((a % M) * (b % M)) % M  \)

나눗셈의 경우엔 곱셈 역원(muliplicative inverse) 개념이 들어가서 패스

 

📌 타일링 방법의 수 세기 (문제 ID: TILING2, 난이도: 하)

algospot.com :: TILING2

 

이 문제도 디게 오랜만이다.

[Python] 1793 - 타일링 (실버2)

// 코드 8.16 타일링의 수를 세는 동적 계획법 알고리즘

const int MOD = 1000000007;
int cache[101];
// 2 * width 크기의 사각형을 채우는 비대칭 방법의 수를 MOD로 나눈 나머지를 반환한다
int tiling(int width) {
    // 기저 사례: width가 1 이하일 때
    if (width <= 1) return 1;
    // 메모이제이션
    int& ret = cache[width];
    if (ret != -1) return ret;
    return ret = (tiling(width - 2) + tiling(width - 1)) % MOD;
}

엄청 오랜만에 보는 문제. 사실 요건 반복문으로 풀면 진짜 깔끔하고 직관적이다.

예전에 풀어본 문제기도 하고, 귀찮으니 바로 동적 계획법으로 설계해보자. (정작 그땐 이렇게 안 풀었는데)

 

• 기저 사례는 총 두 가지 (맨 왼쪽 세로줄 타일 배치에 따라 결정 된다.)
  1. n == 1 : 한 가지 경우밖에 없다 (| 형태)
  2. n == 2 : 두 가지 경우가 나온다. (= 형태)
• 이때 다음 두 조건이 성립한다.
  • 이 두 가지 분류는 타일링하는 방법을 모두 포함한다.
  • 두 가지 분류에 모두 포함되는 타일링 방법은 없다.
• 아래 점화식을 새울 수 있다.
  • \(tiling(n) = 2*n\) 크기의 사각형을 타일로 덮는 방법을 반환한다.
  • \(tiling(n) = tiling(n-1)+tiling(n-2)\)

 

⏲️ 시간 복잡도

이 알고리즘에서 부분 문제 수는 O(n)이고, 계산 수행 시간이 O(1)이므로 전체 시간 복잡도는 O(n)이 된다.

 

📌 삼각형 위의 최대 경로 개수 세기 (문제 ID: TRIPATHCNT, 난이도: 중)

algospot.com :: TRIPATHCNT

 

이 문제를 해결하기 위해서는 다른 두 개의 동적 계획법 문제를 해결해야 한다.

1. 바탕이 되는 최적화 문제를 해결한다.
2. 각 부분 문제마다 최적해의 개수를 계산하는 동적 계획법 알고리즘을 작성한다.

 

1번은 코드 8.9의 path2로 구할 수 있다.

9             24
5  7          13  15
1  3  2        6   8    8
3  5  5  6     3   5    5    6

path2로 구한 구간별 최대 경로를 알고 있다면 탐욕법으로 최대 경로를 파악할 수 있다.

count(y, x) = (y, x)에서 시작해 맨 아래줄까지 내려가는 최대 경로의 수

$$ \begin{align} count(y, x) = max\begin{cases} count(y+1, x) & (path2(y+1,x) > path2(y+1,x+1)) \\ count(y+1, x+1) & (path2(y+1,x) < path2(y+1,x+1)) \\ count(y+1,x)+count(y+1,x+1) & (path2(y+1,x)=path2(y+1, x+1)) \end{cases} \end{align} $$

 

// 코드 8.17 삼각형 위의 최대 경로의 수를 찾는 동적 계획법 알고리즘

int countCache[100][100];
// (y, x)에서 시작해서 맨 아래줄까지 내려가는 경로 중 최대 경로의 수를 반환한다.
int count(int y, int x) {
    // 기저 사례: 맨 아래줄에 도달한 경우
    if (y == n - 1) return 1;
    // 메모이제이션
    int& ret = countCache[y][x];
    if (ret != -1) return ret;
    ret = 0;
    if (path2(y + 1, x + 1) >= path2(y + 1, x))
        ret += count(y + 1, x + 1);
    if (path2(y + 1, x + 1) <= path2(y + 1, x))
        ret += count(y + 1, x);
    return ret;
}

 

📌 우물을 기어오르는 달팽이

🟡 문제

 

깊이가 n미터인 우물 맨 밑바닥에서 달팽이가 올라오고 있다.

하루에 2미터 씩 올라올 수 있으나, 비가 내리면 1미터밖에 올라오지 못한다.

앞으로 m일간 각 날짜에 비가 올 확률이 정확히 50%일 때, m일 안에 달팽이가 우물 끝까지 올라갈 확률은?

 

1️⃣ 경우의 수로 확률 계산하기

 

m일 간 가능한 날씨 조합은 {1, 1, 1, 1, ⋯, 1, 1} 부터 {2, 2, 2, 2, ⋯, 2, 2}까지 다양하다.

각 조합이 출현할 확률 또한 모두 동일하다.

따라서 위 날씨 조합 중 합이 n 이상인 조합의 수를 확인하여, 전체 조합의 수 2^n으로 나누면 된다.

 

2️⃣ 완전 탐색 알고리즘

// 코드 8.18 우물을 기어오르는 달팽이 문제를 해결하는 동적 계획법 알고리즘

int n, m;
int cache[MAX_N][2 * MAX_N + 1];
// 달팽이가 days일 동안 climbed미터를 기어올라 왔다고 할 때,
// m일 전까지 n미터를 기어올라갈 수 있는 경우의 수
int climb(int days, int climbed) {
    // 기저 사례: m일이 모두 지난 경우
    if (days == m) return climbed >= n ? 1 : 0;
    // 메모이제이션
    int& ret = cache[days][climbed];
    if (ret != -1) return ret;
    return ret = climb(days + 1, climbed + 1) + climb(days + 1, climbed + 2);
}

• climb(C')
  • 지금까지 만든 날씨 조합 C'에서 원소의 합이 n 이상인 경우의 수
• \(climb(C')=climb(C'+[1])+climb(C'+[2])\)
  • C'의 종류가 너무 많으므로 Memoization을 적용할 수 없다.
  • 과거에 한 선택에 대한 정보는 최소한도로 줄이는 것이 좋다.
• climb(days, climbed)
  • 지금까지 만든 날씨 조합 C' 크기가 days이고 그 원소들의 합이 climbed일 때
  • C'를 완성해서 원소의 합이 n 이상인 경우의 수
  • 즉, days만큼 지났을 때 climbed까지 올라왔다면 그 뒤로는 이미 계산된 결과를 사용하면 된다.

 

📌 장마가 찾아왔다 (문제 ID: SNAIL, 난이도: 하)

algospot.com :: SNAIL

 

가중치를 주면 쉽게 풀리는 문제가 된다.

약간 머신 러닝하는 느낌으로다가..

$$ \begin{align} climb2(days, climbed) = 0.75+climb2(days+1, climbed+1) + 0.25*climb2(days+1, climbed+2) \end{align} $$

 

📌 경우의 수 계산하기 레시피

1. 모든 답을 직접 만들어서 세어보는 완전 탐색 알고리즘을 설계한다.
   • 재귀 호출 각 단계에서 고르는 각 선택지는 다음과 같은 속성이 성립해야 한다.
     • 모든 경우는 해당 선택지에 포함된다.
     • 어떤 경우도 두 개 이상의 선택지에 포함되지 않는다.
2. 최적화 문제를 해결할 때처럼 이전 조각에서 결정한 요소들에 대한 입력을 없애거나 변형해서 줄인다.
   • 재귀 함수는 앞으로 남아 있는 조각들을 고르는 경우의 수만을 반환해야 한다.
3. Memoization을 적용한다.

 

---

8. 비대칭 타일링 (문제 ID: ASYMTILING, 난이도: 하)

 

• 문제
• 완전 탐색의 함정
• 직접 비대칭 타일링 수 세기
• 스캐폴딩으로 테스트하기

 

📌 문제

algospot.com :: ASYMTILING

 

📌 완전 탐색의 함정

💡 기존에 풀어본 문제의 변형된 형태는 좀 더 단순화된 해법을 이용해서 더 쉽게 풀 수 있는 경우가 있다.

2*n 크기 사각형을 덮는 대칭 타일링 방법

• (비대칭 타일링 수) = (전체 타일링 수) - (대칭 타일링 수)
• 대칭 타일링 수를 세는 단계
  1. n이 짝수인 경우와 홀수인 경우를 나눈다.
     • n이 홀수, 정가운데 세로운은 세로 타일 하나로 덮여야 한다.
     • n이 짝수, 정가운데 세로줄 둘을 가로 타일로 덮거나, 절만을 기준으로 대칭인 경우다.
  2. 경계를 나누고 한쪽을 채우면, 다른 한쪽은 자연스럽게 결정된다. (대칭이므로)

 

// 코드 8.16 타일링의 수를 세는 동적 계획법 알고리즘

const int MOD = 1000000007;
int cache[101];
// 2 * width 크기의 사각형을 채우는 비대칭 방법의 수를 MOD로 나눈 나머지를 반환한다
int tiling(int width) {
    // 기저 사례: width가 1 이하일 때
    if (width <= 1) return 1;
    // 메모이제이션
    int& ret = cache[width];
    if (ret != -1) return ret;
    return ret = (tiling(width - 2) + tiling(width - 1)) % MOD;
}

// 8.19 비대칭 타일링 문제를 해결하는 동적 계획법 알고리즘

// 2 * width 크기의 사각형을 채우는 비대칭 방법의 수를 반환한다.
int asymmetric (int width) {
    if (width % 2 == 1)
        return (tiling(width) - tiling(width / 2) + MOD) % MOD;
    int ret = tiling(width);
    ret = (ret - tiling(width / 2) + MOD) % MOD;
    ret = (ret - tiling(width / 2 - 1) + MOD) % MOD;
    return ret;
}

• tiling() 반환 값은 반드시 양수지만 뺄셈의 결과는 음수일 수 있으므로 MOD로 나누기 전에 MOD를 미리 더해준다.

 

🤔 대체 MOD를 왜 더하는 건데?

이 부분이 이해가 안 가서 제법 시간이 오래 걸렸다.
요지는 이렇다. tiling은 경우의 수를 반환하는 함수이므로 절대 음수가 나오지는 않는다.
그러나 문제는 tiling이 MOD의 나머지 값을 반환하는 데 있다.

예를 들어, 다음과 같은 경우가 나올 수 있다는 것이다.
• MOD = 100
• tiling(width) = (MOD + 1) % MOD
• tiling(width) = (50) % MOD
=> tiling(width) + tiling(width/2) = -49

이렇게 되면 최종 답이 -49가 된다.
\((tiling(width) + tiling(width/2)) % MOD\)

그렇다면 이 상황을 어떻게 고쳐야 할까? tiling의 MOD 연산을 제거하는 건 무리가 있다.
이럴 때는 MOD 연산의 성질을 이용하면 쉽게 해결된다.

[Modulo Distributive Law]
• (a + b) % MOD = (a % MOD + b % MOD) % MOD
• (a * b) % MOD = (a % MOD * b % MOD) % MOD

이를 이용하면 아까의 식은 이렇게 다시 풀 수 있다.
\( (tiling(width) + tiling(width/2) + MOD) % MOD ( \because \text{MOD % MOD = 0} ) \) 

 

⏲️ 시간 복잡도

asymmetric() 자체는 상수 시간에 이루어지므로, tiling의 시간 복잡도인 O(N)과 동일하다.

 

📌 직접 비대칭 타일링 수 세기

2*n 사각형을 덮는 타일링 방법

귀찮긴 하지만 불가능하진 않다.

우선, 전체 타일링 수를 세고 비대칭인 경우를 걸러내는 것은 Memoization을 적용할 수 없다.

비대칭인지 아닌지를 판단하기 위해서 과거의 모든 선택한 조각을 불러와야 하기 때문이다.

 

대신 양방향에서 타일링을 진행하면 된다.

위 이미지에서 a, b와 c, d인 케이스 두 가지로 분류하면 다음처럼 로직을 작성할 수 있다.

• a, b : 가운데 남은 회색 부분을 탐색하는 방법을 재귀호출로 찾는다. 대칭이 아닌 경우여야 한다.
• c, d : 가운데 남은 회색 부분을 탐색하는 방법을 찾는다. 대칭이어도 상관없다.

 

// 코드 8.20 직접 비대칭 타일링의 수를 세는 동적 계획법 알고리즘

int cache2[101];
// 2 * width 크기의 사각형을 채우는 비대칭 방법의 수를 반환한다
int asymmetric2(int width) {
    // 기저 사례: 너비가 2 이하인 경우
    if (width <= 2) return 0;
    // 메모이제이션
    int& ret = cache2[width];
    if (ret != -1) return ret;
    ret = asymmetric2(width - 2) % MOD;
    ret = (ret + asymmetric2(width - 4)) % MOD;
    ret = (ret + tiling(width - 3)) % MOD;
    ret = (ret + tiling(width - 3)) % MOD;
    return ret;
}

 

⏲️ 시간 복잡도

놀랍게도 asymmetric2()도 O(N)이라는 시간 복잡도가 소요된다.

그 이유는 tiling 또한 memoization을 통해 값을 기록하고 있으므로, 가장 처음 계산을 제외하고는 모두 O(1)이라고 취급할 수 있다.

즉, 상수 시간으로 대체하면 asymmetric2의 부분 문제 수인 O(N)이 최종 시간 복잡도가 된다.

(tiling이 memoization으로 인해 O(1)이 된다는 걸 놓쳐서 한참 고민했다.)

 

📌 스캐폴딩으로 테스트하기

이 문제는 입력을 생성하기 쉽고, 느리지만 확실히 정답임을 보일 수 있는 알고리즘이 존재한다.

• 모든 타일링 방법을 만들어보고 대칭인지 확인하기

따라서 스캐폴딩을 통해 테스트를 거치면 알고리즘의 정당성을 증명할 수 있다.

 

---

9. 폴리오미노 (문제 ID: POLY, 난이도: 중)

 

• 문제
• 완전 탐색에서 시작하기
• 동적 계획법으로 바꾸기

 

📌 문제

algospot.com :: POLY

문제 이해하는 게 더 오래 걸렸다! ㅋㅋㅋ

 

📌 완전 탐색에서 시작하기

세로로 단조라는 말은 가로는 언제나 일렬로 연속되어야 한다는 의미가 된다.

그 말은 즉슨 각 row마다 정사각형이 몇 개가 들어갈 지 정하고, 이 가로 블럭을 좌우로 왔다갔다 하면서 배치해보면 된다는 말이 된다.

1. 첫 줄에 i개의 정사각형이 속한 폴리오미노
2. 나머지 n-i개로 구성된 정사각형들로 폴리오미노를 만든다.
3. 생성된 폴리오미노를 윗 줄에 붙인다.

즉, poly(n)은 다음과 같이 정의할 수 있을 것이다.

$$ \begin{align} poly(n) = \text{n개의 정사각형으로 만들 수 있는 세로 단조 폴리오미노의 수를 반환한다.} \end{align} $$

 

그러나 부분 문제의 맨 윗 줄에 정사각형의 개수가 몇 개인지에 따라서 결과가 또 달라진다.

그 말은 즉슨, 나머지 사각형으로 만든 폴리오미노의 첫 번째 줄의 정사각형 수 별로 폴리오미노 수를 돌려받아야 한다는 의미다.

그러기 위해선 poly의 매개변수에 첫 줄에 들어갈 정사각형의 수 first를 추가하면 된다. 

 

$$ \begin{align} poly(n, fisrt) = \text{n개의 정사각형을 포함하되, 첫 줄에 first개의 정사각형이 들어가는 폴리오미노의 수} \end{align} $$

 

첫 줄에 들어갈 정사각형의 수가 정해졌으므로, n-first 개의 정사각형들로 폴리오미노를 마저 만들어주면 된다.

 

$$ \begin{align} poly(n-fisrt, 1) + poly(n-first 2) + \cdots + poly(n-first, n-first) \end{align} $$

 

어떻게 잘 나머지 폴리오미노들로 조합을 완성시켜 왔을 때, first의 가로줄과 매핑시킬 수 있는 방법을 고려해보면 된다.

굳이 따지면 Merge 하는 과정에 속한다고 볼 수 있다.

몇 개의 경우의 수를 대조해보면 merge하는 방법의 수는 언제나 first + second - 1이 된다는 것을 알 수 있다.

 

$$ \begin{align} poly(n-first, 1) &= fisrt*poly(n-first, 1) + (first+1)*poly(n-first, 2) + \cdots + (n-1)*poly(n-first, n-first) \\&= \sum^{n-first}_{second=1}(second + first - 1)*poly(n-first, second) \end{align} $$

 

🚨 Overflow

(second+first-1)*poly(n-first, second)에서 Overflow가 발생할 가능성이 있다.

하지만 poly의 반환 값은 1천만 미만, second+first-1은 n 이하이므로 최대 10억에 불과하다.

따라서 Overflow가 발생하지는 않는다.

 

// 코드 8.21 폴리오미노의 수 구하기

const int MOD = 10 * 1000 * 1000;
int cache[101][101];
// n개의 정사각형으로 이루어졌고, 맨 위 가로줄에 first개의 정사각형을 포함하는 폴리오미노의 수를 반환한다
int poly(int n, int first) {
    // 기저 사례: n == first
    if (n == first) return 1;
    // 메모이제이션
    int& ret = cache[n][first];
    if (ret != -1) return ret;
    ret = 0;
    for (int second = 1; second <= n - first; ++second) {
        int add = second + first - 1;
        add *= poly(n - first, second);
        add %= MOD;
        ret += add;
        ret %= MOD;
    }
    return ret;
}

 

⏲️ 시간 복잡도

• (n과 first 조합의 수) = O(N^2)
• poly의 연산 횟수 = O(N)

따라서 시간 복잡도는 O(N^3)이 된다. 

 

---

10. 두니발 박사의 탈옥 (문제 ID: NUMB3RS, 난이도: 중)

 

• 문제
• 완전 탐색
• Memoization
• 조건부 확률?
• 반대 방향에서 풀기
• 마르코프 연쇄(Markov Chain)

 

📌 문제

algospot.com :: NUMB3RS

한니발이 설마 그 한니발인가 했는데 맞았다.

근데 양들의 침묵에 나왔던 한니발과 공통의 가상 인물이라는 건 이번에 처음 안 사실

한니발(드라마) - 나무위키

진짜 재밌게 봤었는데, 이게 벌써 4년전 ㅠ

 

📌 완전 탐색

// 코드 8.22 두니발 박사의 탈옥 문제를 해결하는 완전 탐색 알고리즘

int n, d, p, q;
// connected[i][j] = 마을 i, j가 연결되어 있나 여부
// deg[i] = 마을 i와 연결된 마을의 개수
double connected[51][51], deg[51];
double search(vector<int>& path) {
    // 기저 사례: d일이 지난 경우
    if (path.size() == d + 1) {
        // 이 시나리오가 q에서 끝나지 않는다면 무효
        if (path.back() != q) return 0.0;
        // path의 출현 확률을 계산한다
        double ret = 1.0;
        for (int i = 0; i + 1 < path.size(); ++i)
            ret /= deg[path[i]];
        return ret;
    }
    double ret = 0;
    // 경로의 다음 위치를 결정한다
    for (int there = 0; there < n; ++there)
        if (connected[path.back()][there]) {
            path.push_back(there);
            ret += search(path);
            path.pop_back();
        }
    return ret;
}

무식한 방법은 간단하다.

주위 연결된 마을을 찾아서 하나씩 쑤셔보고, 끝까지 들어간다.

그리고 마지막에 지나온 마을들에 인접한 마을 수만큼 모두 나누어주면 답이 나온다.

 

내가 처음에 떠올린 아이디어는 path로 관리하지 않고, 그때그때 상황에 맞게 계산하는 걸 떠올렸던 터라 왜 이렇게 하지 싶었는데, 이 다음 과정이 내가 생각한 아이디어였다 ㅎㅎ;

 

📌 Memoization

위 상태로는 Memoization을 할 수 없다.

따라서 선택한 조각들에 대한 정보를 최소한으로 줄여, 중복되는 부분 문제를 극대화할 필요가 있다.

 

path의 용도

1. path의 마지막 원소는 현재 위치 : 다음 마을 결정
2. path의 길이는 탈옥 후 지난 날짜 : 경로가 끝났는지 확인
3. 확률 계산 : 확률을 계산할 때, 지나온 마을 조회

여기서 최소한의 조건을 남기기 위해서 다음과 같은 변화를 적용한다.

1. path 대신 현재 위치 here와 탈옥 후 지난 날짜 days를 재귀 호출에 전달한다.
2. 전체 경로의 확률을 계산하는 게 아니라, 현재 위치에서 시작해 남은 날짜 동안움직여 q에 도달할 확률을 계산한다. 

즉, 너무 많은 정보를 담고 있는 path를 날려버린 것이다.

• search2(here, days) = 두니발 박사가 days일 째에 here번 마을에 숨어 있을 때, 마지막 날에 q번 마을에 있을 조건부 확률

 

$$ \begin{align} search2(here, days)=\frac{\sum_{there \in adj(here)}search2(there, days+1)}{\left|adj(here)\right|} \end{align} $$

 

📌 조건부 확률?

• (동적 계획 레시피 中) 재귀 함수는 앞으로 선택하는 조각들의 결과만을 반환해야 한다.
• 어떤 경로 A = {a0, a1, ..., ad}가 출현할 확률 또한 다음처럼 정의할 수 있다.

 

$$ \begin{align} P(A)&=\frac{1}{\left|adj(a_{0}) \right|}\times \frac{1}{\left|adj(a_{1}) \right|} \times \cdots \times \frac{1}{\left|adj(a_{d-1}) \right|} \\&= \prod_{i=0}^{d-1}\frac{1}{\left|adj(a_{i}) \right|} \end{align} $$

 

이때 search2()가 반환하는 조건부 확률은 각 경로에 대해 다음 값의 합으로 쓸 수 있다.

 

$$ \begin{align} \frac{1}{\left| adj(a_{days}) \right|} \times \cdots \times \frac{1}{\left| adj(a_{d-1}) \right|}  \end{align} $$

 

따라서 앞으로 선택하는 조각들에 대한 답만 반환한다는 원칙에 부합한다.

 

// 코드 8.23 두니발 박사의 탈옥 문제를 해결하는 동적 계획법 알고리즘

int n, d, p, q;
// cache[][]는 -1로 초기화해 둔다
double cache[51][101];
// connected[i][j] = 마을 i, j가 연결되어 있나 여부
// deg[i] = 마을 i와 연결된 마을의 개수
double connected[51][51], deg[51];
// days일째에 here번 마을에 숨어 있다고 가정하고,
// 마지막 날에 q번 마을에 숨어 있을 조건부 확률을 반환한다
double search2(int here, int days) {
    // 기저 사례: d일이 지난 경우
    if (days == d) return (here == q ? 1.0 : 0.0);
    // 메모이제이션
    double& ret = cache[here][days];
    if (ret > -0.5) return ret;
    ret = 0.0;
    for (int there = 0; there < n; ++there)
        if (connected[here][there])
            ret += search2(there, days + 1) / deg[here];
    return ret;
}

 

⏲️ 시간 복잡도

• 부분 문제의 개수 O(nd)
• 계산 시간 O(n)

따라서, 전체 시간 복잡도는 \(O(n^{2}d)\)가 된다

 

📌 반대 방향에서 풀기

위 방법은 테스트 케이스 관점에서 고려하면 조사할 도시의 수(t) 만큼인 \(O(n^{2}dt)\)만큼의 시간이 소요된다.

문제를 통과하는데 지장은 없지만 순서만 바꾸면 더 빠르게 해결할 수 있다.

 

두니발 박사가 도망다니는 경로를 추적해 d일 째에 q를 도달하는 경우를 찾으려면, q가 바뀔 때마다 부분 문제의 답이 바뀐다.

그렇다면 반대로 q부터 경로를 만들어서 그 전날 박사가 숨어 있었을 곳을 역추적해볼 수 있다.

• search3(here, days) = 탈옥 후 days일 째에 두니발 박사가 here번 마을에 숨어 있을 확률

$$ \begin{align}search3(here, days)=\sum_{there\in adj(here)}\frac{1}{adj(there)}\cdot search3(there, days-1)\end{align} $$

 

사실 이 부분에서 대체 왜 q부터 구하는 게 중복을 제거하는 게 더 합리적이라는 건지 도저히 이해가 안 가서 애먹었다.

곰곰히 생각해보면 별 거 아닌 얘기였다.

시작점(p)에서 목적지(q)로 가는 길을 구하는 것은 q가 바뀔 때마다 처음부터 다시 계산을 해야한다.

왜냐하면, 각 부분 문제들이 모두 "q로 향하는 길"을 계산하고 있기 때문이다.

 

반면에 q에서 p로 가는 길을 계산하는 건 조금 다르다.

출발하는 시점으로부터 days에 이르기까지 현재 지점으로 오는 데 부분 문제의 해는 다른 목적지에서도 써먹을 수 있다.

...뭐 그런 간단한 이야기였다. 이해하느라 한참 걸렸음. 

 

// 코드 8.24 두니발 박사의 탈옥 문제를 해결하는 동적 계획법 알고리즘

int n, d, p, q;
double cache[51][101];
double connected[51][51], deg[51];
double search3(int here, int days) {
    // 기저 사례: 0일째
    if (days == 0) return (here == p ? 1.0 : 0.0);
    // 메모이제이션
    double& ret = cache[here][days];
    if (ret > -0.5) return ret;
    ret = 0.0;
    for (int there = 0; there < n; ++there)
        if (connected[here][there])
            ret += search3(there, days - 1) / deg[there];
    return ret;
}

 

📌 마르코프 연쇄(Markov Chain)

https://ko.wikipedia.org/wiki/%EB%A7%88%EB%A5%B4%EC%BD%94%ED%94%84_%EC%97%B0%EC%87%84

뭔가 했는데 인공지능 하다가 봤었던 내용이다.

마크로프 연쇄가 성립하려면 몇 가지 조건을 충족해야 한다.

• 유한 개의 상태가 존재한다.
• 매 시간마다 상태가 변경된다.
• 어떤 상태 a에서 다른 상태 b로 옮겨갈 확률은 현재 상태 a에만 좌우된다.
• a 이전에 어느 상태에 있었는지, 현재 시간은 얼마인지 등은 영향을 주지 않는다.

증명하려다가 별도의 포스트로 다뤄도 모자랄 분량이라 일단 패스했다.