• Divide and Conquer
  • Merge Sort
  • 빠른 거듭 제곱
• Dynamic Programming
  • Memoization : Top Down DP
  • Bottom Up DP
  • DP 예시 : 2차원 경로 문제
• Additional Topics / Problems

* 오늘은 특별한 알고리즘을 배우는 것이 아니라, ‘방법론’ 에 가깝기 때문에, Section과 Additional의 구분이 별로 없고 모두 소문제들로 구성되어 있습니다. 여기 나온 모든 소문제를 고민해 보길 권합니다.

Divide and Conquer

어떤 문제들은 문제 자체가 재귀적입니다. 즉, 어떤 커다란 문제 X를 풀기 위해, X를 여러 개의 작은 문제 $x_1, x_2, \dots x_k$로 나눈 다음, 각각을 풀고, 합칠 수 있습니다. 프로그래밍으로 생각해 보자면, 재귀함수를 쓰는 것이 자연스러운 문제들이 있습니다. 이러한 문제들에 대해, Divide and Conquer (분할 정복) 이라는 기법이 매우 유용합니다.
지금까지 여러분은 분할 정복을 쓰는 알고리즘을 상당히 많이 만나 보았기 때문에, 분할 정복이라는 말이 익숙하지 않더라도 생각하는 방법 자체는 그렇게 낯설지 않을 것입니다. 이 문제를 풀기 어렵지만, 작은 문제를 풀고 합치는 게 더 쉬울 수도 있다면, 분할 정복을 생각해 볼 수 있겠습니다.

Merge Sort

병합 정렬 (Merge Sort) 는 대표적인 분할 정복 기법입니다. 앞서 말한 분할 정복을 쓰는 이유가 가장 잘 나타납니다. $n$ 크기의 배열을 정렬하는 것보다, $n/2$ 크기의 배열 2개를 정렬하고, 두 정렬된 배열을 정렬성을 유지하면서 합치는 것이 더 빠르기 때문입니다.
아래 예시와 Additional (1), (2) 모두 분할 정복을 이용하는 훌륭한 예시입니다.

빠른 거듭 제곱

Divide and Conquer를 사용하는 다른 예시를 생각해 봅시다. 이번의 목표는, 어떤 수 $x$의 $y$제곱을 계산하는 일입니다. 상식적으로, 곱셈을 $y$ 번 하는 일이므로, $O(y)$에 하는 것이 자연스러워 보입니다.
암호학, 특히 RSA 암호 체계에서는 $x^y \pmod{p}$를 계산할 일이 매우 많은데, $y$가 거대한 수인 경우도 많이 있습니다. 만약 $10,702,103$의 $2,718,281,828$ 제곱 같은 것을 계산하려고 한다면, 어떨까요? 이때 우리는 ‘exponentiation by squaring’ 이라는 방법을 쓸 수 있습니다. 만약 $x^y$에서 $y$가 홀수라면, $x^{y-1} \times x$로 식을 정리합니다. 만약 $y$가 짝수라면, $(x^{y/2})^2$ 로 정리합니다. 이 방법이 $\order{\log y}$ 에 제곱을 수행한다는 사실을 생각해 봅시다.

Dynamic Programming

Memoization : Top Down DP

분할 정복은 정말 강력한 도구입니다. 예를 들어, 피보나치 수열도 분할 정복으로 계산할 수 있습니다. fib(n)을 계산하기 위해, fib(n-1) 과 fib(n-2)를 호출하면 됩니다. 그러나 이 방법의 시간 복잡도는 처참합니다. 호출되는 과정을 보면, $f(n)$ 은 한 번 호출하더라도, $f(1)$ 이나 $f(2)$ 같은 함수들을 수없이 많이 호출하고 있기 때문입니다. 우리는 이런 중복되는 과정을, 약간의 메모리를 이용하여, 한번만 계산하고 싶습니다.
이를 위해 사용하는 기법이 Memoization입니다.¹ 미리 배열 fib[]에, 매번 호출될 때마다 내가 계산한 값을 적어 놓습니다. 매번 함수가 호출될 때마다, 혹시 이 값이 내가 본 적 있는 값인지 메모지를 확인하고, 메모지에 적힌 값은 다시 계산하는 대신, 메모지를 보고 바로 답하는 것입니다.
함수 호출의 순서를 보면, 큰 값들 (TOP) 이 먼저 호출되고, 그 과정에서 작은 값들 (DOWN)의 값들의 계산이 필요함을 눈치챈 다음, 내려가면서 이 값들을 계산하고 다시 올라오면서 문제를 해결하는 과정을 볼 수 있습니다. 이 과정을 TOP-DOWN 방식의 Dynamic Programming 이라고 부릅니다.

Bottom Up DP

물론, 피보나치 수열을 계산하기 위해 꼭 저런 방식을 쓸 필요는 없습니다. 작은 값들을 이용해서 큰 값을 계산할 수만 있다면, 다음과 같이 간단하게 코딩해도 됩니다.

for (int i = 2; i<=n; i++)
    fib[i] = fib[i-1] + fib[i-2]

이 방법은, 계산 순서를 볼 때, 작은 값들을 먼저 계산해놓고 그걸 이용해서 위로 올라가며 계산하는 방법입니다. 이를 Bottom-UP 방식의 Dynamic Programming이라고 부릅니다.
Top-Down과 Bottom-Up 중 무엇이 더 구현하기 편하고, 어느쪽이 유리한지는 그때그때 다르기 때문에, 상황에 따라 다른 방법을 사용해야 합니다. 중요한 것은 다음의 원칙입니다.

• Optimal Substructure : 큰 문제 $f(X)$를 해결하기 위해, $f(Y)$ such that $Y < X$의 답을 이용하는 것입니다.² 즉, 작은 문제의 답이 항상 더 큰 문제의 답을 제공하는데 도움이 되는 경우를 의미합니다. 이 조건은 Divide and Conquer과 Dynamic Programming 모두에 적용됩니다.

• Overlapping Subproblem : 위 Overlapping Substructure를 적용함에 있어서, 겹치는 문제를 여러번 풀어야 해서 이를 최적화하고 싶은 경우를 의미합니다. Fibonacci가 대표적입니다. 이 원칙은 Dynamic Programming의 기본 원리입니다.

DP 예시 : 2차원 경로 문제

양수로 이루어진 $n \times n$ 행렬이 주어져 있습니다. 이때, 우리는 $(1, 1)$ 에서 출발하여, $(n, n)$ 위치까지 이동하되, 아래쪽 또는 오른쪽으로만 이동할 수 있습니다. 이동하는 과정에서, 행렬의 방문한 칸에 쓰여 있는 숫자들을 더한 값이 이 경로의 최종 점수입니다. 점수를 최대화하는 이동 경로를 찾아 봅시다.
Optimal Substructure를 생각해 봅시다. 어떤 칸 $(i, j)$ 에 도착하기 위해서는, $(i-1, j)$ 또는 $(i, j-1)$ 에서 와야 합니다. 이때, $(i-1, j)$ 까지 어떻게 왔는지는 별로 관심이 없지만, 이 시점까지 온 점수가 최대가 되면 좋을 것 같습니다. 즉, 경로와 무관하게 일단 어떻게든 최선을 다해 $(i-1, j)$ 또는 $(i, j-1)$ 까지 왔다면, 그 경로들에서 한칸을 연장하여 $(i, j)$ 에 오는 최적 경로가 나타나기 때문입니다. 즉, 다음과 같은 DP를 구상합니다. \(C_{ij} = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0\\ \max({C_{i-1, j}, C_{i, j-1}}) + M_{ij} & \text{otherwise} \end{cases}\) 만약 $C_{44}$를 계산하려고 한다면, $C_{34}$와 $C_{43}$ 을 계산해야하고, 그러면 $C_{33}, C_{24}, C_{33}, C_{42}$ 를 계산해야 합니다. 벌써 $C_{33}$ 을 두번 계산했습니다! Overlapping Substructure가 보입니다. 이를 최적화하여 계산해도 좋고, 아래와 같이 Bottom-Up DP를 생각해도 됩니다.

for (int i = 1; i<=n; i++)
    for (int j = 1; j<=n; j++)
        C[i][j] = M[i][j] + max(C[i-1][j], C[i][j-1]);

이렇게 하면 Dynamic Programming을 이용, $O(n^2)$ 에 계산하게 됩니다.
방금 본 것처럼, 2차원 그리드 위에서도 합리적인 DP 순서를 줄 수 있으면 (왼쪽 위부터 오른쪽 아래) 다이나믹 프로그래밍이 가능합니다. 이외에도 DP는 정말 다양한 형태로 등장하고, 유용하기 때문에 많은 연습이 필요합니다.

추천문제 : 아래 (3), (4), (5) 이후에도 더 풀어보고 싶다면, BOJ 기준 1005, 11066, 9251번을 확인해 보세요.

Additional Topics / Problems

1. Karatsuba Algorithm 우리가 곱셈은 $O(1)$에 수행된다고 믿었지만, 사실 생각해 보면 상식적으로 그럴 리가 없습니다. 10억 자리 수를 곱하는 일과 $3 \times 5$를 하는 일이 같은 시간에 수행될 리는 없기 때문입니다. 일상적으로 사용하는 수의 범위에서, 특히 C++의 int 나 long long 범위에서 곱셈이 자연스럽게 상수 비슷한 시간에 수행되기 때문에 우리는 앞으로도 $O(1)$에 기본 사칙연산이 작동한다는 믿음을 갖고 말하겠지만, 여기서는 잠깐만 이 부분을 의심해 봅시다. 다음 흐름을 따라가며, Karatsuba의 아이디어와, 이 아이디어를 처음 들었던 유명한 수학자 Kolmogorov³가 받았던 충격을 느껴봅시다.

   (1) 초등학교에서 배운 방법대로 $139 \times 312$를 계산해 보고, 이 방법을 그대로 컴퓨터로 구현해 낸다면 $n$자리 수를 곱셈하는데 어느정도의 시간이 들지 예측해 보세요.

   (2) 이하, $x, y$는 $B$진법의 $n$자리 수라고 합시다. 먼저, 적당한 $m < n$을 골라, $x = x_1 B^m + x_0$, $y = y_1 B^m + y_0$ 이라고 씁시다. $m$을 $n$의 절반이 되게 고르면 됩니다.⁴

   (3) 이제, $xy$ 가 $(x_1 B^m + x_0) (y_1 B^m + y_0)$ 이므로, $x_1y_1 B^{2m} + (x_1y_0 + x_0y_1)B^m + x_0y_0$으로 나타납니다. $x_1y_1, x_0y_0$은 그대로 계산하고, 가운데 항을 계산하는 대신, $(x_1 + x_0) (y_1 + y_0)$을 계산하고 앞 두개를 빼면 같은 항을 얻습니다.

   (4) 이 알고리즘의 시간 복잡도를 증명하세요. Week 1의 Master Theorem.

2. ($\star$)Closest Pair Problem : BOJ 2261
   다음 문제를 고민하고 해결해 봅시다. $\R^2$ 상의 점 $n$개에 대하여, 가장 가까운 두 점 간의 거리를 찾고자 합니다. 조금 더 수학적으로는, $l = \min_{i, j} d(p_i, p_j)$ 을 찾는 문제입니다. 흐름을 따라가며, 분할 정복이 얼마나 강력한 툴인지 다시한번 느껴봅시다.

   (1) 자명한 ‘쉬운 알고리즘’ 은 $O(n^2)$ 입니다. 우리는 이 문제에 대해 $O(n \log^2 n)$, 나아가 $O(n \log n)$ 알고리즘을 생각하려고 합니다.

   (2) 먼저, Divide and Conquer를 생각하기 위해, $x$축을 기준으로 반으로 자르겠습니다.

   (3) 그러면, [두 점이 왼쪽에 있는 경우], [두 점이 오른쪽에 있는 경우], [양쪽에서 하나씩 뽑는 경우] 를 각각 풀면 됩니다. 이 방법이 시간 복잡도에 전혀 발전이 없음을 보이세요.

   (4) 그러나, [양쪽] 케이스를 정말 모두 확인해야 할까요? 얇은 Strip만 보면 충분함을 관찰하세요.

   (5) Challenge 양쪽 케이스에서, Strip 안의 점 $p_i$에 대해, 최대 7번의 비교로 충분함을 보이세요.

   (6) 이 방법의 시간 복잡도를 증명하고, 어떻게 더 줄일지 생각해 보세요.

3. 행렬 곱셈 순서 : BOJ 11049
   BOJ 11049번을 보고, 이 문제를 어떻게 해결할 수 있는지 생각해 봅시다.

   (1) 단순하게는 풀 방법이 잘 떠오르지 않습니다. 하나 가능한 방법은 모든 가능한 행렬 곱셈 순서를 Naive하게 나열하고 확인하는 것인데, 이 방법에서 확인해야 할 곱셈 순서가 몇 가지일까요? 이걸 계산하는 문제는 상당히 어렵습니다. 언젠가 수학 세션을 하게 되면 생각해 보기로 합시다.

   (2) 마지막 곱셈의 위치를 기준으로 생각해 봅시다.
   마지막 곱셈의 위치가 $(A_1 A_2 \dots A_k)$와 $(A_{k+1} A_{k+2} \dots A_n)$ 을 곱하는 것일 때...

   (3) DP[i][j] = i번째부터 j번째까지의 행렬을 최대한 잘 곱했을 때의 최소 비용 이라고 정의합시다. 점화식을 세워 보고, 그 점화식을 어떻게 빨리 계산할 수 있을지 고민해 보세요.

4. Knapsack Problem : BOJ 12865
   이 문제는 매우 유명한 0-1 Knapsack이라는 문제입니다. 각 물품마다 $w_i$의 무게와 $v_i$의 가치가 있고, 가방에 무게가 $W$ 이하가 되게 넣어야 할 때 가치를 최대화하세요.

   (1) Heuristic은 매우 중요한 알고리즘의 일부이지만 이 문제에서 먹히지 않습니다. 혹시 Naive하게 $v_i / w_i$ 가 최대인것부터 밀어넣는다는 생각을 하셨나요? 가방에 2의 무게만 넣을 수 있고, 무게가 1, 가치가 5인 물건과 무게가 2, 가치가 6인 물건이 있는 경우를 생각해 보세요.

   (2) DP 문제를 접근하는 좋은 방법은, DP 테이블을 먼저 구상하는 것입니다. DP[i][j] 를 다음과 같이 정의할 때... 라고 시작합시다. 어떻게 정의해야 할까요? 힌트 : DP 칸수를 $N \times W$ 로 시도해 봅시다.

5. DP on data structures : BOJ 15681
   고정관념을 버리면 쉽게 풀 수 있습니다. 루트 있는 트리에서, 노드 $x$에 대해, 그 노드를 루트로 하는 서브트리의 정점의 수를 빠르게 답하려면 어떻게 할까요?

   • 이 문제는 쿼리형 문제 라고 부르는 형태인데, “쿼리” 라고 불리는 “질문”이 $Q$개 주어지고 이 쿼리들에 답해야 하는 상황입니다. 자료구조에 대해 얘기할 때, OO에 대한 쿼리를 빠르게 처리하는 자료구조 라는 식으로 이해한 기억이 있을 것입니다.

   • 쿼리가 들어올 때마다 트리를 돌아보면서 대답하면, 한 쿼리를 해결하는 데 $O(n)$ 시간이 들고 (루트만 계속 물어볼 수도 있으니까), 전체 $O(qn)$ 시간이 든다는 의미입니다. 당연히 이 복잡도는 용납할 수 없습니다.

   • 쿼리당 $O(1)$ 에 해결하기 위해, 미리 시간을 좀 써서 전처리 (Preprocessing) 하고, 쿼리가 들어오면 그때그때 답해주면 어떨까요? 즉, $O(n + q)$ 에 해결하겠다는 의미입니다.