[03 알고리즘 설계 패러다임] 7. 분할 정복

1. 도입

 

분할 정복(Divide & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라는 말로 간단히 설명할 수 있습니다. 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 냅니다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것입니다. 이 차이점은 아래 그림에서 알 수 있습니다. 첫 번째 그림은 항상 문제를 한 조각과 나머지로 쪼개는 일반적인 재귀 호출 알고리즘을 보여주고 두 번째 그림은 항상 문제를 절반씩으로 나누는 분할 정복 알고리즘을 보여줍니다.

출처: https://gamedevlog.tistory.com/58

 

분할 정복을 사용하는 알고리즘들은 대개 세 가지의 구성 요소를 갖고 있습니다.

 

• 문제를 더 작은 문제로 분할하는 과정(divide)
• 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)
• 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)

분할 정복을 적용해 문제를 해결하기 위해서는 문제에 몇 가지 특성이 성립해야 합니다. 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 하며, 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 합니다.

예제: 수열의 빠른 합과 행렬의 빠른 제곱 

앞에서는 1 + 2 + ... + n 의 합을 재귀 호출을 이용해 계산하는 recursiveSum() 함수를 작성했습니다. 여기서는 분할 정복을 이용해 똑같은 일을 하는 fastSum() 함수를 만들어 봅시다. 1부터 n까지의 합을 n개의 조각으로 나눈 뒤, 이들을 반으로 뚝 잘라 n/2 개의 조각들로 만들어진 부분 문제 두 개를 만듭니다.(편의상 n은 짝수라 가정하겠습니다.)

faseSum() = 1 + 2 + ... + n
                 = (1 + 2 + ... + n/2) + ((n/2 + 1) + ... + n)

 

첫 번째 부분 문제는 fastSum(n/2)로 나타낼 수 있지만, 두 번째 부분 문제는 그렇지 않습니다. 문제를 재귀적으로 풀기 위해서는 각 부분 문제를 1부터 n까지의 합의 꼴로 표현할 수 있어야 하는데, 위의 분할에서 두 번째 조각은 'a부터 b까지의 합' 형태를 가지고 있기 때문이지요. 따라서 다음과 같이 두 번째 부분 문제를 fastSum(x)를 포함하는 형태로 바꿔 써야 합니다.

(n/2 + 1) + ... + n = (n/2 + 1) + (n/2 + 2) + ... + (n/2 + n/2)
                            = n/2 * n/2 + (1 + 2 + 3 + ... + n/2)
                            = n/2 * n/2 + fastSum(n/2)

 

공통된 항 n/2을 따로 떼내면 놀랍게도 fastSum(n/2)이 나타납니다! 따라서 다음과 같이 쓸 수 있습니다.

fastSum(n) = 2 * fastSum(n/2) + n^2 / 4 (n이 짝수일때)

 

이런 아이디어를 구현한 것이 아래 코드입니다. 이 함수가 홀수인 n을 어떻게 처리하는지 눈여겨 보세요. 위의 분할은 n이 짝수인 경우에 대해서밖에 동작하지 않기 때문에, 홀수인 입력이 주어질 때는 짝수인 n - 1까지의 합을 재귀 호출로 계산하고 n을 더해 답을 구하게 됩니다.

// 필수 조건: n은 자연수
// 1 + 2 + ... + n 을 반환한다.
int fastSum(int n) {
    // 기저 사례
    if(n == 1) return 1;
    if(n % 2 == 1) return fastSum(n-1) + n;
    return 2 * fastSum(n/2) + (n/2)*(n/2);
}

 

시간 복잡도 분석

fastSum() 이 수행하는 데 걸리는 시간은 recursiveSum() 과 어떻게 다를까요? 두 함수 모두 내부에 반복문이 없기 때문에, fastSum()과 recursiveSum()이 종료하는 데 걸리는 시간은 순전히 함수가 호출되는 횟수에 비례하게 됩니다. recursiveSum()의 경우 n번의 함수 호출이 필요하다는 것을 쉽게 알 수 있습니다. 반면 fastSum()은 호출될 때마다 최소한 두 번에 한 번 꼴로 n이 절반으로 줄어들죠. 그러니 fastSum()의 호출 횟수가 훨씬 적으리란 것을 쉽게 예상할 수 있습니다.

 

주어진 n값을 2씩 나누면서 faseSum() 함수를 호출하기 때문에 faseSum() 함수의 총 호출 횟수는 lgN(밑이 2인 log N) 이라는 것을 알 수 있습니다.

n이 4인 경우 : lg4 = 2
n이 8인 경우 : lg8 = 3
n이 16인 경우 : lg16 = 4
...

 

따라서 이 알고리즘의 실행 시간은 O(lgn)입니다. 뭐 어차피 한 줄이면 짤 수 있는 코드를 왜 이렇게 최적화하나 생각이 들 수도 있습니다. 하지만 1 + ... + n과 달리 간단히 수식으로 표현되지 않는 문제를 풀 때에도 이 원리는 유용하게 사용됩니다. 그 좋은 예가 행렬의 거듭제곱입니다.

 

행렬의 거듭제곱

N x N 크기의 행렬 A가 주어질 때, A의 거듭제곱(power) A^m은 A를 연속해서 m번 곱한 것입니다. 이것을 계산하는 알고리즘 자체는 어려울 것이 없지만, m이 매우 클 때 (약 백만) A^m을 구하는 것은 꽤나 시간이 오래 걸리는 작업입니다. 행렬의 곱셈에는 O(n^3)의 시간이 들기 때문에 곧이 곧대로 m - 1번 곱셈을 통해 A^m을 구하려면 모두 O(n^3m)번의 연산이 필요합니다. n=100, m=1,000,000 이라고 한다면 필요한 연산의 수는 대략 1조 정도가 되는데 이건 분산 컴퓨팅 클러스터를 쓴다면 모를까 1초 안에 계산할 수 없는 양이지요. 그러나 분할정복을 이용하면 눈 깜짝할 새에 이 값을 구할 수 있습니다.

 

이전에 사용한 아이디어를 이용해 A^m 을 구하는데 필요한 m개의 조각을 절반으로 나눠 봅시다.

 

A^m = A^(m/2) x A^(m/2)

 

반으로 자르기만 하면 절반 크기의 부분 문제가 갑자기 툭 튀어나오니 fastSum() 보다 간단하면 간단했지 그다지 다를 것이 없습니다. 다음 코드는 이 알고리즘의 구현을 보여줍니다.

// 정방행렬을 표현하는 SquareMatrix 클래스가 있다고 가정하자.
class SquareMatrix;
// n*n 크기의 항등 행렬(identity matrix)을 반환하는 함수
SquareMatrix identity(int n);
// A^m을 반환한다.
SquareMatrix pow(const SquareMatrix& A, int m) {
    // 기저사례 : A^0 = 1
    if(m == 0)  return identity(A.size());
    if(m % 2 > 0) return pow(A, m-1) * A;
    SquareMatrix half = pow(A, m / 2);
    // A^m = (A^(m/2)) * (A^(m/2))
    return half * half;
}

 

나누어 떨어지지 않을 때의 분할과 시간 복잡도

m이 홀수일 때, A^m = A x A^(m-1) 로 나누지 않고, 좀 더 절반에 가깝게 나누는게 좋지 않을까라는 생각을 할 수도 있습니다. 예를 들어 A^7 을 A x A^6 로 나누느 것이 아니라 A^3 x A^4 로 나누는 것이 더 좋지 않은가 하는 것이지요.실제로 문제의 크기가 매번 절반에 가깝게 줄어들면 기저 사례에 도달하기까지 걸리는 분할의 횟수가 줄어들기 때문에 대부분의 분할 정복 알고리즘은 가능한 한 절반에 가깝게 문제를 나누고자 합니다. 퀵 정렬에서 좀더 좋은 분할을 찾기 위해 여러 노력을 하는 것도 좋은 예이지요. 하지만 이 문제에서 이 방식의 분할은 오히려 알고리즘을 더 느리게 만듭니다. 이런 식으로 문제를 나누면 A^m 을 찾기 위해 계산해야 할 부분 문제의 수가 늘어나기 때문이지요.

 

다음 그림은 두 가지 분할 방식을 이용해 pow(A, 31)을 계산할 때 필요한 부분 문제 간의 의존 관계를 보여줍니다. pow(A, x)를 계산하는 과정에서 pow(A, y)를 호출해야 한다면 두 값은 화살표로 연결되어 있습니다.

 

그림에서 (a)와 (b)는 얼핏 보면 크게 다를 것이 없어 보이지만, 각 부분 문제가 계산되는 횟수가 다르다는 데 큰 차이가 있습니다. (a) 에서 pow(A, 8)은 pow(A, 15)를 계산할 때도 호출되고 pow(A, 16)을 계산할 때도 호출되므로, 모두 두 번 호출된다는 것을 알 수 있지요. 따라서 pow(A, 8)과 pow(A, 7)을 계살 할 때 사용하는  pow(A, 4)는 모두 세 번 호출됩니다. 이와 같이 같은 값을 중복으로 계산하는 일이 많기 때문에, m이 증가함에 따라 pow(A, m)을 계산하는 데 필요한 pow()의 호출 횟수는 m에 대해 선형적으로 증가합니다. pow()가 한 번 호출될 때마다 행렬 곱셈을 한 번 하기 때문에, (a) 가 보여주는 분할 방식은 대문자 O 표기법으로 보면 결국 m-1 번 곱셈하는 것과 다를 바가 없습니다. 반면 (b)에서는 pow() 가 O(lgm) 개의 거듭제곱에 대해 한 번씩만 호출된다는 것을 쉽게 알 수 있지요.

 

이것은 같은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다는 것을 보여주는 좋은 예입니다. 절반으로 나누는 알고리즘이 큰 효율 저하를 불러오는 이유는 바로 여러 번 중복되어 계산되면서 시간을 소모하는 부분 문제들이 있기 때문입니다. 이런 속성을 부분 문제가 중복된다고 하며 이후 다루게될 동적 계획범이 고안된 계기가 됩니다.

 

예제: 병합 정렬과 퀵 정렬

주어진 수열을 크기 순서대로 정렬하는 문제는 전산학에서 가장 유명한 문제 중 하나입니다. 이 문제를 해결하는 수많은 알고리즘 중 가장 널리 쓰이는 것들이 바로 병합 정렬(Merge sort)과 퀵 정렬(Quick sort)인데, 이 두 알고리즘은 모두 분할 정복 패러다임을 기반으로 해서 만들어진 것들입니다. 다음 그림은 두 알고리즘의 동작 과정을 보여줍니다.

 

(a)는 병합 정렬의 동작 과정을 보여줍니다. 각 수열의 크기가 1이 될 때까지 절반씩 쪼개 나간 뒤, 정렬된 부분 배열들을 합쳐 나가는 것을 볼 수 있지요. 병합 정렬의 분할 방식은 아주 단순하고 효율적입니다. 주어진 배열을 가운데서 절반으로 그냥 나누는 것이죠. 따라서 이 과정을 상수 시간인 O(1) 만에 수행할 수 있습니다. 그러나 각각 나눠서 정렬한 배열들을 하나의 배열로 합치기 위해 별도의 병합 과정을 실행해야 합니다. 여기에 O(n)의 시간이 걸립니다.

 

(b)에서 보여진 퀵 정렬은 각 부분 수열의 맨 처음에 있는 수를 기준으로 삼고, 이들보다 작은 수를 왼쪽으로, 큰 것을 오른쪽으로 가게끔 문제를 분해합니다. 그림에서 동그라미로 표시된 수들은 이전 수를 분할하는 데 사용된 기준을 표현합니다. 이 분할은 O(n)의 시간이 걸리는 복잡한 작업인데다, 우리가 어떤 기준을 선택하느냐에 따라서 비효율적인 불할을 불러올 여지가 있지만 그 덕분에 각 부분 배열이 이미 정렬한 상태가 되어 별도의 병합 작업이 필요없다는 장점이 있습니다.

 

시간 복잡도 분석

병합 정렬과 퀵 정렬의 시간 복잡도는 비슷한 방법으로 분석할 수 있습니다. O(n)의 시간이 걸리는 과정을 재귀 호출 전에 하느냐, 후에 하느냐가 다를 뿐 본질적으로 비슷한 형태의 알고리즘이기 때문입니다. 병합 정렬은 각 단계마다 반으로 나눈 부분 문제를 재귀 호출을 이용해 해결한 뒤, 이들의 결과 수열을 합쳐 전체 문제의 답을 계산합니다. 정렬된 두 부분 수열을 합치는 데는 두 수열의 길이 합 만큼 반복문을 수행해야 하기 때문에 병합 정렬의 수행시간은 이 병합 과정에 의해 지배됩니다. 그런데 아래 단계로 내려갈수록 부분 문제의 수는 두 배로 늘고 각 부분 문제의 크기는 반으로 줄어들기 때문에 한 단계 내에서 모든 병합에 필요한 총 시간은 O(n) 으로 항상 일정합니다. 아래 그림은 병합 정렬이 처리하는 부분 문제의 크기를 단계별로 모은 것인데, 각 단계를 나타내느 각 가로줄에 있는 원소의 수는 항상 일정하다는 것을 쉽게 알 수 있지요. 따라서 단계의 수에 n을 곱하면 병합 정렬에 필요한 전체 시간을 얻을 수 있습니다. 문제의 크기는 항상 거의 절반으로 나누어 지기 때문에 필요한 단계의 수는 O(lgn)이 됩니다. 따라서 병합 정렬의 시간 복잡도가 O(nlgn)이라는 사실을 알 수 있습니다.

 

퀵 정렬에서 병합 정렬과 달리 시간 복잡도를 분석하기 까다로운 것은 결과적으로 분할된 두 부분 문제가 비슷한 크기로 나눠진다는 보장을 할 수 없기 때문입니다. 기준으로 택한 원소가 최소 원소나 최대 원소인 경우 부분 문제의 크기가 하나씩만 줄어들 수도 있으니까요. 이런 최악의 경우 퀵 정렬의 시간 복잡도는 O(n^2) 이 됩니다. 다행히 평균적으로 부분 문제가 절반에 가깝게 나눠질 때 퀵 정렬의 시간 복잡도는 병합 정렬과 같은 O(nlgn)이 된다는 것이 알려져 있습니다.

 

예제: 카라츠바의 빠른 곱셈 알고리즘

특히 재미있는 병합 과정을 가진 분할 정복 알고리즘의 한 예가 카라츠바의 빠른 곱셈 알고리즘으로, 두 개의 정수를 곱하는 알고리즘입니다. 물론 32비트 정수 둘을 곱할 때 쓰는 것은 아니고, 수백자리, 나아가 수만 자리는 되는 큰 숫자들을 다룰 때 주로 사용합니다. 이렇게 큰 숫자들은 배열을 이용해 저장해야 하지요. 

 

다음 코드는 두 정수를 곱하는 알고리즘을 보여줍니다. multiply() 가 일반적인 정수형 변수가 아닌 정수형 배열을 입력받는 점을 눈여겨 보시기 바랍니다. 이 배열들은 곱할 수의 각 자릿수를 맨 아래 자리부터 저장하고 있습니다. 이렇게 순서를 뒤집으면 입출력할 때는 불편하지만, A[i]에 주어진 자릿수의 크기를 10^i 로 쉽게 구할 수 있다는 장점이 있습니다. 따라서 A[i]와 B[j]를 곱한 결과를 C[i+j]에 저장하는 등, 훨씬 직관적인 코드를 작성할 수 있습니다. 또 하나 눈여겨볼 점은 자릿수 올림을 처리하는 nomalize()에서 자릿수가 음수인 경우도 처리하고 있는 것입니다. muliply() 에서는 덧셈밖에 하지 않기 때문에, 자릿수가 음수가 될 일이 없지요. 카라츠바 알고리즘의 구현을 보고 나면 왜 이 구현이 필요한지 이해할 수 있습니다.

// num[]의 자릿수 올림을 처리한다.
void normalize(vector<int>& num) {
    num.push_back(0);
    // 자릿수 올림을 처리한다.
    for(int i = 0; i < num.size(); i++) {
        if(num[i] < 0) {
            int borrow = (abs(num[i]) + 9) / 10;
            num[i+1] -= borrow;
            num[i] += borrow * 10;
        }
        else {
            num[i+1] += num[i] / 10;
            num[i] %= 10;
        }
    }
    while(num.size() > 1 && num.back() == 0) num.pop_back();
}

// 두 긴 자연수의 곱을 반환한다.
// 각 배열에는 각 수의 자릿수가 1의 자리에서부터 시작해 저장되어 있다.
// 예: multiply({3,2,1}, {6,5,4}) = 123 * 456 = 56088 = {8, 8, 0, 6, 5}
vector<int> muliply(const vector<int>& a, const vector<int>& b) {
    vector<int> c(a.size() + b.size() + 1, 0);
    for(int i = 0; i < a.size(); i++) {
        for(int j = 0; j < b.size(); j++) {
            c[i+j] += a[i] * b[j];
        }
    }
    normalize(c);
    return c;
}

 

이 알고리즘의 시간 복잡도는 두 정수의 길이가 모두 n이라고 할 때 O(n^2) 입니다. n번 실행되는 for문이 두 번 겹쳐 있기 때문에 이점은 아주 자명하죠. 이 알고리즘은 굉장히 단순합니다만, 이것보다 빠른 알고리즘을 고안하기란 쉽지 않습니다. 이보다 빠른 첫 번째 알고리즘이 카라츠바 알고리즘이었는데, 이 알고리즘도 1960년에야 출현했을 정도죠.

 

카라츠바의 빠른 곱셈 알고리즘은 두 수를 각각 절반으로 쪼갭니다. a와 b가 각각 256자리 수라면 a1과 b1은 첫 128자리, a0와 b0는 그 다음 128자리를 저장하도록 하는 것이죠. 그러면 a와 b를 다음과 같이 쓸 수 있습니다.

a = a1 * 10^128 + a0
b = b1 * 10^128 + b0

 

카라츠바는 이때 a x b를 네 개의 조각을 이용해 표현하는 방법을 살펴보았습니다. 예를 들면 다음과 같이 표현할 수 있지요.

a x b = (a1 * 10^128 + a0) x (b1 * 10^128 + b0)
         = a1 * b1 * 10^256 + (a1 * b0 + a0 * b1) * 10^128 + a0 * b0

 

이 방법에서는 큰 정수 두 개를 한 번 곱하는 대신, 절반 크기로 나눈 작은 조각을 네 번 곱합니다. (10의 거듭제곱과 곱하는 것은 그냥 뒤에 0을 붙이는 시프트 연산으로 구현하면 되니 곱셈으로 치지 않습니다.) 이대로도 각각을 재귀 호출해서 해결하면 분할 정복 알고리즘이라고 할 수 있겠지요. 이 방법의 시간 복잡도는 얼마일까요? 이 방법에서 길이 n인 두 정수를 곱하는 데 드는 시간은 덧셈과 시프트 연산에 걸리는 시간 O(n)과, n/2 길이 조각들의 곱셈 네 번으로 나눌 수 있습니다. 그런데 사실 이 방법의 전체 수행 시간이 O(n^2)이 된다는 사실을 증명할 수 있습니다. 이래서는 분할 정복을 애써 구현한 의미가 없지요.

 

카라츠바가 발견한 것은 다음과 같이 a x b를 표현했을 때 네 번 대신 세 번의 곱셈만으로 값을 계산할 수 있다는 것입니다.

a x b = a1 x b1 x 10^256 + (a1 x b0 + a0 x b1) x 10^128 + (a0 x b0)
            z2                             z1                                             z0

 

조각들의 곱을 각각 위와 같이 z2, z1, z0 이라고 씁시다. 우선 z0와 z2를 각각 한 번의 곱셈으로 구합니다. 그리고 다음 식을 이용하지요.

(a0 + a1) x (b0 + b1) = (a0 x b0) + (a1 x b0 + a0 x b1) + (a1 x b1)
                                      z0               z1                              z2
                                  = z0 + z1 + z2

 

따라서 위 식의 결과에서 z0과 z2를 빼서 z1을 구할 수 있습니다. 다음과 같은 코드 조각을 이용하면 되지요.

z2 = a1 * b1;
z0 = a0 * b0;
z1 = (a0 + a1) * (b0 + b1) - z0 - z2;

 

이 과정은 곱셈을 세 번밖에 쓰지 않지요! 그러고 나면 이 세 결과를 적절히 조합해 원래 두 수의 답을 구해낼 수 있습니다. 다음 코드는 이와 같이 구현한 카라츠바 알고리즘의 구현을 보여줍니다.

// a += b * (10^k); 를 구현한다.
void addTo(vector<int>& a, const vector<int>& b, int k);
// a -= b; 를 구현한다. a >= b 를 가정한다.
void subFrom(vector<int>& a, const vector<int>& b);
// 두 긴 정수의 곱을 반환한다.
vector<int> karatsuba(const vector<int>& a, const vector<int>& a) {
    int an = a.size(), bn = b.size();
    // a가 b보다 짧을 경우 둘을 바꾼다.
    if(an < bn) return karatsuba(b, a);
    // 기저 사례: a나 b가 비어 있는 경우
    if(an == 0 || bn == 0) return vector<int>();
    // 기저 사례 : a가 비교적 짧은 경우 O(n^2) 곱셈으로 변경한다.
    if(an <= 50) return multiply(a, b);
    
    int half = an / 2;
    // a와 b를 밑에서 half 자리와 나머지로 분리한다.
    vector<int> a0(a.begin(), a.begin() + half);
    vector<int> a1(a.begin() + half, a.end());
    vector<int> b0(b.begin(), b.begin() + min<int>(b.size(), half));
    vector<int> b1(b.begin() + min<int>(b.size(), half), b.end());
    
    // z2 = a1 * b1
    vector<int> z2 = karatsuba(a1, b1);
    
    // z0 = a0 * b0
    vector<int> z0 = karatsuba(a0, b0);
    
    // a0 = a0 + a1; b0 = b0 + b1
    addTo(a0, a1, 0); addTo(b0, b1, 0);
    
    // z1 = (a0 * b0) - z0 -z2;
    vector<int> z1 = karatsuba(a0, b0);
    
    subFrom(z1, z0);
    subFrom(z1, z2);
    
    // ret = z0 + z1 * 10^half + z2 * 10^(half * 2)
    vector<int> ret;
    addTo(ret, z0, 0);
    addTo(ret, z1, half);
    addTo(ret, z2, half + half);
    return ret;
}

 

카라츠바 알고리즘은 분할한 부분 문제의 답에서 원래 문제의 답을 병합해내는 부분을 개선함으로써 알고리즘의 성능을 향상시킨 좋은 예입니다. 스트라센(Strassen)의 행렬 곱셈 알고리즘 또한 이와 비슷한 기법을 사용하지요.

 

시간 복잡도 분석

카라츠바 알고리즘은 두 개의 입력을 절반씩으로 쪼갠 뒤, 세 번 재귀 호출을 하기 때문에 재귀 호출을 한 번이나 두 번만 하던 지금까지의 예제와는 다르게 시간복잡도를 분석해야 합니다.

우선 카라츠바 알고리즘의 수행 시간을 병합 단계와 기저 사례의 두 부분으로 나눕시다. 위 구현 코드에서 병합 단계의 수행 시간은 addTo()와 subFrom()의 수행 시간에 지배되고, 기저 사례의 처리 시간은 multiply()의 수행 시간에 지배되는 것을 볼 수 있지요.

 

먼저 기저 사례를 처리하는데 드는 총 시간을 알아봅시다. 위 코드에서는 더 긴 숫자의 길이가 50자리보다 짧아지면 multiply()를 이용해 답을 계산하기로 했지만, 여기서는 편의를 위해 한 자리 숫자에 도달해야만 multiply() 를 사용한다고 가정하지요. 자릿수 n이 2의 거듭제곱 2^k라고 했을 때 재귀 호출의 깊이는 k가 됩니다. 한 번 쪼갤 때마다 해야 할 곱셈의 수가 세 배씩 늘어나기 때문에 마지막 단계에는 3^k개의 부분 문제가 있는데, 마지막 단계에서는 두 수 모두 한 자리니까 곱셈 한 번이면 충분합니다. 따라서 곱셈의 수는 O(3^k)가 됩니다. n = 2^k 라고 가정했으니 k=lgn 이고, 이때 곱셈의 수를 n에 대해 표현하면 다음과 같은 식이 됩니다.

O(3^k) = (3^lgn) = O(n^lg3)

 

lg3 은 약 1.585이기 때문에 카라츠바 알고리즘이 O(n^2) 보다 훨씬 적은 곱셈을 필요로 한다는 것을 알 수 있지요. 만약 n이 10만이라고 하면 곱셈의 수는 대략 100배 정도 차이가 납니다.

 

다음으로 병합 단계에 드는 시간의 총 합을 구해봅시다. addTo()와 subFrom()은 숫자의 길이에 비례하는 시간만이 걸리도록 구현할 수 있습니다. 따라서 각 단계에 해당하는 숫자의 길이를 모두 더하면 병합 단계에 드는 시간을 계산할 수 있습니다. 단계가 내려갈 때마다 숫자의 길이는 절반으로 줄고 부분 문제의 개수는 세 배 늘기 때문에, i번째 단계에서 필요한 연산 수는 (3/2)^i * n 이 됩니다. 따라서 모든 단계에서 필요한 전체 연산의 수는 다음 식에 비례하지요.

 

n * ((3/2) ^ i [i = 0 부터 lgn 까지의 합])

 

이 함수는 n^lg3 과 같은 속도로 증가합니다. 따라서 카라츠바 알고리즘의 시간 복잡도는 곱셈이 지배하며, 최종 시간 복잡도는 O(n^lg3)이 됩니다. 단, 카라츠바 알고리즘의 구현은 단순한 O(n^2) 알고리즘보다 훨씬 복잡하기 때문에 입력의 크기가 작을 경우 O(n^2) 알고리즘보다 느린 경우가 많다는데 유의합시다. 위의 코드에서 입력된 숫자가 짧을 경우 O(n^2) 알고리즘을 사용하는 것도 이런 이유에서지요.

 

2. 문제: 쿼드 트리 뒤집기 (문제 ID: QUADTREE, 난이도: 하)

 

 

 

 

 

3. 풀이: 쿼드 트리 뒤집기

 

 

 

 

 

 

 

4. 문제: 울타리 잘라내기 (문제 ID: FENCE, 난이도: 중)

 

 

 

 

 

 

 

5. 풀이: 울타리 잘라내기

 

 

 

 

 

 

 

6. 문제: 팬미팅 (문제 ID: FANMEETING, 난이도: 상)

 

 

 

 

 

 

 

7. 풀이: 팬미팅