Computer Sci./Algorithms

[알고리즘 문제 해결 전략] Ch03-2. 알고리즘 설계 패러다임 (분할 정복)

DevOwen 2022. 3. 21. 09:00

7 분할 정복

7.1 분할 정복

분할 정복(Divide & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라는 말로 간단히 설명할 수 있다. 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다.

분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다. 이 차이점이 아래 그림이다. 그림 (a)는 항상 문제를 한 조각과 나머지로 쪼개는 일반적인 재귀 호출 알고리즘을 보여주고, 그림 (b)는 항상 문제를 절반씩으로 나누는 분할 정복 알고리즘을 보여준다.

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

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

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

분할 정복의 장점은 많은 경우에 같은 작업을 더 빠르게 처리를 해 준다. 관련된 예제를 살펴 보도록 하자.

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

1부터 n까지의 합을 구하는 함수 fastSum(n)을 분할정복을 가지고 만들어 보자.

$$
fastSum(n) = 1 + 2 + 3 + ... + n = (1 + 2 + ... + n/2) + ((n/2 + 1) + ... + n) = fastSum(n/2) + ((n/2 + 1) + (n/2 + 2) + ... + (n/2 + n/2)) = fastSum(n/2) + (n/2)_(n/2) + (1 + 2 + ... + n/2) = 2_fastNum(n/2) + n^2/4
$$

따라서 다음과 같이 점화식을 만들 수가 있다.

$$
fastSum(n) = 2*fastSum(n/2) + n^2/4 (단 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()이 한 번 호출 될 때마다 최소한 두 번에 한 번 꼴로 n이 절반으로 줄어든다는 것을 알 수 있다. 따라서 N이 충분히 큰 수라 하면 분할 정복의 시간복잡도는 O(lgN)이 된다.

예제: 병합 정렬과 퀵 정렬

주어진 수열을 크기 순서대로 정렬하는 문제는 전산학에서 가장 유명한 문제 중 하나이다. 이 문제를 해결하는 수 많은 알고리즘 중 가장 널리 쓰이는 것이 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이다. 이 두 알고리즘은 모두 분할 정복 패러다임을 기반으로 해서 만들어 졌다. 여기서는 직접적인 구현이나 증명은 생략하고 동작 원리와 시간 복잡도만을 알아 본다.

병합 정렬 알고리즘은 주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두 개로 만든 뒤 이들을 재귀 호출해서 각각 정렬한다. 그 후 정렬된 배열을 하나로 합쳐서 전체 수열을 얻는다.

반대로 퀵 정렬 알고리즘은 배열을 단순히 가운데서 쪼개는 대신, 병합 과정이 필요 없도록 한쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열을 분할한다. 이를 위해 퀵 정렬은 파티션(partition)이라 부르는 단계를 도입하는데, 이는 배열에 있는 수 중 임의의 '기준 수(pivot)'를 지정한 후 기준보다 작거나 같은 숫자를 왼쪽, 더 큰 숫자를 오른쪽으로 보내는 과정이다.

아래 그림은 병합 정렬과 퀵 정렬의 분할 방식을 보여주는 그림이다.

먼저 왼쪽의 동작 과정은 각 수열의 크기가 1이 될 때까지 절반씩 쪼개 나가고, 정렬된 부분 배열들을 합쳐 나가는 것을 볼 수 있다. 절반을 나누는 과정은 O(1), 나눠진 배열을 하나로 합치는 과정은 O(N)이 걸린다.

퀵 정렬은 각 부분 수열의 맨 처음에 있는 수를 기준으로 삼고, 이들보다 작은 수를 왼쪽으로, 큰 것을 오른쪽으로 가게끔 문제를 분해한다. 이 분할은 O(N)의 시간복잡도가 걸리고 기준을 어떻게 가져가느냐에 따라 비효율적일 수 있지만, 이로 인해 각 부분배열이 이미 정렬한 상태가 되어 별도의 병합 작업이 필요없다는 장점이 있다.

시간 복잡도 분석

병합 정렬의 경우 한 단계에서 필요한 총 시간은 O(N)이고 이는 일정하다. 그리고 문제의 크기는 항상 거의 절반으로 나누어 지기 때문에, 필요한 단계의 수는 O(lgN)이 된다. 따라서 병합 정렬의 전체 시간복잡도는 O(NlgN)이 된다.

퀵 정렬의 경우 대부분의 시간을 차지하는 것은 주어진 문제를 두 개의 부분 문제로 나누는 부분이다. 병합 정렬과 달리 퀵 정렬의 시간 복잡도를 분석하기 어려운 것은 결과적으로 분할된 두 부분 문제가 비슷한 크기로 나눠진다는 보장을 할 수 없기 때문이다. 기준으로 택한 원소가 최소 원소나 최대 원소인 경우 부분 문제의 크기가 하나씩만 줄어들 수 있기 때문이다. 최악의 경우 퀵 정렬의 시간 복잡도는 O(N^2)이 된다. 다행히 평균적으로 부분 문제가 절반에 가깝게 나눠질 때 퀵 정렬의 시간 복잡도는 병합 정렬과 같은 O(NlgN)이 된다. 따라서 대부분의 퀵 정렬 구현은 가능한 한 절반에 가까운 분할을 얻기 위해 좋은 기준을 뽑는 다양한 방법들을 사용한다.

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

카라츠바의 빠른 곱셈 알고리즘은, 두 개의 정수를 곱하는 알고리즘이다. 이 연산은 수백 자리나 수만 자리 정도의 큰 숫자들을 다룰 때 주로 사용한다. 이렇게 큰 숫자들은 배열을 이용해 저장해야 한다.

두 정수를 곱한다고 했을 때 이를 코드로 나타내 보자. multiply()는 일반적인 정수형 변수가 아닌 정수형 배열을 입력받는다. 이 배열들은 곱할 수의 각 자리수를 맨 아래 자리부터 저장하고 있다. 이렇게 순서를 뒤집으면 입출력 할 때는 불편하지만 A[i]에 주어진 자릿수의 크기를 $10^i$로 쉽게 구할 수 있다는 장점이 있다. 따라서 A[i]와 B[j]를 곱한 결과를 C[i+j]에 저장하는 등 훨씬 직관적인 코드를 작성할 수 있다.

또 하나 잘 보아야 하는 점은 자리수 올림을 처리하는 normalize()에서 자릿수가 음수인 경우도 처리하고 있다는 점이다. 이 부분은 카라츠바 알고리즘의 구현을 보고 나면 이해할 수 있다.

// num[]의 자릿수 올림을 처리한다
void normalize(vector<int>& num) {
    num.push_back(0);
    // 자리수 올림을 처리한다.
    for(int i = 0; i+1 < 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> multiply(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자리 수라면 $a_1$과 $b_1$은 첫 128자리, $a_0$과 $b_0$은 그 다음 128자리를 저장하도록 하는 것이다. 그러면 a,b를 다음과 같이 쓸 수 있다.

$$
a = a_1 \times 10^{128} + a_0\
b = b_1 \times 10^{128} + b_0
$$

카라츠바는 이 때 $a \times b$ 를 네 개의 조각을 이용해 표현하는 방법을 살펴보았다. 예를 들어 다음과 같이 표현할 수 있다.

$$
a \times b = (a_1 \times 10^{128} + a_0) \times (b_1 \times 10^{128} + b_0) = a_1 \times b_1 \times 10^{256} + (a_1 \times b_0 + a_0 \times b_1) \times 10^{128} +a_0 \times b_0
$$

이 방법에서 우리는 큰 정수 두 개를 한 번 곱하는 대신, 절반 크기로 나눈 작은 조각을 네 번 곱한다. 이대로 각각을 재귀 호출해서 해결하면 분할 정복 알고리즘이라고 할 수 있다. 이 방법의 시간복잡도는 계산해 보면 O($n^2$)이 된다. 결국 시간복잡도가 줄어들지 않았으므로 의미가 없다.

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

$$
a \times b = a_1 \times b_1 \times 10^{256} + (a_1 \times b_0 + a_0 \times b_1) \times 10^{128} +a_0 \times b_0 = z_2 \times 10^{256} + z_1 \times 10^{128} + z_0
$$

이렇게 되면 곱셈을 세 번밖에 쓰지 않는다. 이 세 결과를 다시 적절히 조합해 원래 두 수의 답을 구해낼 수 있다. 아래는 카라츠바 알고리즘의 구현이다.

// 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>& b) {
    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()와 subForm()의 수행 시간에 지배되고, 기저 사례의 처리 시간은 multiply()의 수행 시간에 지배된다.

자릿수 n이 2의 거듭제곱 $2^k$라고 했을 때, 재귀 호출의 깊이는 k가 된다. 한 번 쪼갤 때 마다 해야 할 곱셈의 수가 세 배씩 늘어나기 때문에 마지막 단계에는 $3^k$개의 부분 문제가 있는데, 마지막 단계에서는 두 수 모두 한 자리니까 곱셈 한 번이면 충분하다. 따라서 곱셈의 수는 O($3^k)$가 된다. $n = 2^k$라고 가정했으니 $k=\log n$ 이고 이 때 곱셈의 수를 n에 대해 표현하면 다음과 같은 식이 된다.

$$
O(3^k) = O(3^{\log n}) = O(n^{\log 3})
$$

log3 = 1.585 정도의 값이기 때문에 카라츠바 알고리즘이 O($n^2$)보다 훨씬 적은 곱셈을 필요로 한다.

병합 단계에 드는 시간을 구해보자. addTo()와 subFrom()은 숫자의 길이에 비례하는 시간만이 걸리도록 구현할 수 있다. 따라서 각 단계에 해당하는 숫자의 길이를 모두 더하면 병합 단계에 드는 시간을 계산할 수 있다. 단계가 내려갈 때마다 숫자의 길이는 절반으로 줄고 부분 문제의 갯수는 세 배 늘기 때문에 i 번째 단계에서 필요한 연산의 수는 $({3 \over 2})^i \times n$ 이 된다. 따라서 이 함수는 결국 $n^{\log 3}$과 같은 속도로 증가한다. 따라서 카라츠바 알고리즘의 시간 복잡도는 곱셈이 지배하며, 최종 시간 복잡도는 O($n^{\log 3}$)이 된다.

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

문제

이 문제를 풀 수 있는 가장 무식한 방법은 주어진 그림의 쿼드 트리 압축을 풀어서 실제 이미지를 얻고 상하 반전한 뒤 다시 쿼드 트리 압축하는 것이다. 하지만 문제에서 주어진 크기 제한을 보면 이를 곧이곧대로 구현할 수는 없음을 알 수 있다. 따라서 이러한 경우 우리가 선택할 수 있는 접근 방법은 보통 두 가지이다.

  • 큰 입력에 대해서도 동작하는 효율적인 알고리즘을 처음부터 새로 만들기
  • 작은 입력에 대해서만 동작하는 단순한 알고리즘으로부터 시작해서 최적화 해 나가기

쿼드 드리 압축 풀기

쿼드 트리가 재귀적으로 정의되어 있기 때문에 쿼드 트리를 압축하거나 해제하는 과정은 재귀 호출로 구현하는 것이 가장 자연스럽다. 문자열 s의 압축을 해제해서 NXN 크기 배열에 저장하는 함수 decompress()를 구현하자. 기저 사례는 s의 첫 글자가 w나 b인 경우이고, 이 때는 배열 전체에 해당 색을 칠하고 곧장 종료한다. 만약 첫 글자가 x라면 decompress()는 s의 나머지 부분을 넷으로 쪼개 재귀 호출한다.

압축 문자열 분할하기

각 부분의 길이가 일정하지 않기 때문에 s의 나머지 부분을 넷으로 쪼개기는 까다롭다. 이를 해결하기 위해 생각할 수 있는 첫 번째 방법은 주어진 위치에서 시작하는 압축 결과의 길이를 반환하는 getChunkLength()를 만드는 것이다. 하지만 이 방법은 비슷한 일을 하는 두 개의 함수를 각각 만들어준다는 점에서 엄청 좋은 방법은 아니다.

유용하게 쓸 수 있는 패턴은 s를 미리 쪼개는 것이 아니라 decompress() 함수에서 ‘필요한 만큼 가져다 쓰도록'하는 것이다. decompress() 함수에 s를 통째로 전달하는 것이 아니라, s의 한 글자를 가리키는 포인터를 전달한다. 함수 내에서는 한 글자를 검사할 때마다 이 포인터를 앞으로 한 칸씩 옮긴다. 코드는 아래와 같다.

char decompressed[MAX_SIZE][MAX_SIZE];
void decompress(string::iterator& it, int y, int x, int size) {
    // 한 글자를 검사할 때마다 반복자를 한 칸 앞으로 옮긴다.
    char head = *(it++);
    // 기저 사례 : 첫 글자가 b 또는 w인 경우
    if(head == 'b' || head == 'w') {
        for(int dy == 0; dy < size; ++dy)
            for(int dx == 0; dx < size; ++dx)
                decompressed[y+dy][x+dx] = head;
    }
    else {
        // 네 부분을 각각 순서대로 압축 해제한다.
        int half = size/2;
        decompress(it, y, x, half);
        decompress(it, y, x+half, half);
        decompress(it, y+half, x, half);
        decompress(it, y+half, x+half, half);
    }
}

STL의 문자열에서 지원하는 반복자(iterator)를 재귀 호출에 전달하는 점에 주목하자. 이 때 반복자가 참조형으로 전달되기 때문에 재귀 호출 내부에서 반복자를 옮기면 밖에도 그 변화가 전달되게 된다.

압축 다 풀지 않고 뒤집기

압축을 푼 결과를 그대로 다 사용하기에는 문제에서 주어진 조건이 너무 크다. 이런 경우 압축 해제한 결과를 메모리에 다 저장하는 대신 결과 이미지를 뒤집은 결과를 곧장 생성하는 코드를 작성하는 것이다.

그림 7.6은 이 병합 과정을 어떻게 해야 할지 보여준다. 원본 그림을 4등분 해서 각 부분을 그림 (a)와 같이 1,2,3,4로 부르기로 했다고 가정하자. 이 때 재귀 호출을 이용해 네 부분을 각각 상하로 뒤집은 압축 결과를 얻었다고 하자. 각 부분을 합치면 (b)와 같이 각 부분이 상하로 뒤집힌 그림이 된다. 여기에서 위 두 조각과 아래 두 조각을 각각 바꾸면 그림 (c)를 얻을 수 있는데, 이것이 애초에 우리가 원하던 전체가 뒤집힌 그림이 된다. 이 아이디어에 기초에 코드를 작성하면 아래와 같다.

string reverse(string::iterator& it) {
    char head = *it;
    ++it;
    if(head == 'b' || head == 'w')
        return string(1, head);
    string upperLeft = reverse(it);
    string upperRight = reverse(it);
    string lowerLeft = reverse(it);
    string lowerRight = reverse(it);
    // 각각 위와 아래 조각들의 위치를 바꾼다.
    return string("x") + lowerLeft + lowerRight + upperLeft + upperRight;
}

시간 복잡도 분석

reverse() 함수는 한 번 호출 될 때마다 주어진 문자열의 한 글자씩을 사용한다. 따라서 함수가 호출되는 횟수는 문자열의 길이에 비례하므로 O(n)이 된다. 각 문자열을 합치는데 O(n)의 시간이 든다 해도 시간 안에 충분히 수행할 수 있다.

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

문제

무식하게 풀 수도 있지만 그렇게 될 경우 시간복잡도는 O($n^2$) 이며, 입력의 최대 크기가 20,000이기에 시간초과가 나오게 된다.

분할 정복 알고리즘의 설계

분할 정복 알고리즘을 설계하기 위해서는 문제를 어떻게 분할할지 가장 먼저 결정해야 한다. n개의 판자를 절반으로 나누어 부분 문제를 만든다. 그러면 우리가 찾는 최대 직사각형은 다음 세 가지 중 하나이다.

  • 가장 큰 직사각형은 왼쪽 부분 문제에서만 잘라낼 수 있다.
  • 가장 큰 직사각형은 오른쪽 부분 문제에서만 잘라낼 수 있다.
  • 가장 큰 직사각형은 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐 있다.

첫 번째와 두 번째는 반으로 나눈 부분 문제를 재귀 호출하여 해결할 수 있다. 세 번째 경우에 대해서만 답을 빠르게 구할 수 있다면 분할 정복 알고리즘은 완성된다.

양쪽 부분 문제에 걸친 경우의 답

양쪽 부분 문제에 모두 걸치는 직사각형 중 가장 큰 것을 찾는 방법은 더 높은 오른쪽 판자를 포함하게끔 확장하는 것이다. 가장 큰 사각형을 찾으려면 항상 사각형의 높이를 최대화 하는 방향으로 확장해야 한다. 아래 그림은 예제 입력에서 어떠한 순서대로 사각형을 고려해야 하는지를 보여준다.

이 때 재귀 호출 함수 solve()는 판자의 높이를 저장하는 전역 배열 h[]의 구간 [left, right]을 넘겨받아 해당 구간에서 잘라낼 수 있는 최대 사각형의 너비를 반환한다.

// 각 관자의 높이를 저장하는 배열
vector<int> h;
// h[left, right] 구간에서 찾아낼 수 있는 가장 큰 사각형의 넓이를 반환한다.
int solve(int left, int right) {
    // 기저 사례 : 판자가 하나밖에 없는 경우
    if(left == right) return h[left];
    // [left, mid], [mid+1, right]의 두 구간으로 문제를 분할한다.
    int mid = (left + right) / 2;
    // 분할한 문제를 각개격파
    int ret = max(solve(left, mid), solve(mid+1, right));
    // 부분 문제 3: 두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는다.
    int lo = mid, hi = mid+1;
    int height = min(h[lo], h[hi]);
    // [mid, mid+1]만 포함하는 너비 2인 사각형을 고려한다.
    ret = max(ret, height*2);
    // 사각형이 입력 전체를 덮을 때까지 확장해 나간다.
    while(left < lo || hi < right) {
        // 항상 높이가 더 높은 쪽으로 확장한다.
        if(hi < right && (lo == left || h[lo-1] < h[hi+1])) {
            ++hi;
            height = min(hieght, h[hi]);
        }
        else {
            --lo;
            height = min(height, h[lo]);
        }
        // 확장한 후 사각형의 넓이
        ret = max(ret, height*(hi-lo+1));
    }
    return ret;
}

정당성 증명

이 알고리즘의 정당성을 보이려 할 때 핵심이 되는 부분은 양쪽 부분 문제에 걸쳐 있는 직사각형을 찾을 때, 각 단계마다 더 높은 판자를 택하는 것이 항상 옳음을 보이는 부분이다. 이는 귀류법을 통해 쉽게 증명할 수 있다.

어떤 사각형 R이 우리가 이 과정을 통해 찾은 최대 직사각형보다 더 크다고 가정하자. 너비가 2인 사각형에서 시작해서 한 칸씩 사각형의 너비를 늘려가므로, 우리가 고려한 사각형들 중 R과 너비가 같은 사각형이 반드시 하나 있다. 이 사각형을 R’ 라고 하자. 너비가 같으므로 R이 더 넓기 위해서는 높이가 반드시 R’보다 높아야 한다.

R과 R’은 둘 다 부분 문제 경계에 있는 두 개의 판자를 포함하므로 항상 겹치는 부분이 있다. R이 R’보다 높으므로, R에 포함된 모든 판자들은 당연히 A보다 높아야 한다. 우리의 알고리즘은 현재 사각형의 양쪽 끝에 있는 두 판자 중 항상 더 높은 것을 선택하므로, A보다 낮거나 높이가 같은 판자를 만나야만 A를 선택하게 된다. 그런데 R’을 만드는 과정에서 만나는 반대쪽 판자들은 모두 R에 속해 있으므로 A보다 높다. 따라서 A를 선택하는 경우가 있을 수 없으며, R이 R’보다 높다는 우리의 가정이 모순이라는 사실을 알게 된다. 이렇게 위의 코드에서 고려하는 사각형 중에 반드시 최대 사각형이 있다는 것을 증명할 수 있다.

시간복잡도 분석

위의 예제 코드는 주어진 n 크기의 배열을 $n \over 2$크기의 배열 두 개로 나눈 뒤 이들을 각각 해결한다. 재귀 호출 외에 함수 내에서 하는 일은 두 부분에 걸쳐 있는 사각형을 찾는 작업밖에 없으므로, 이 작업의 시간 복잡도가 전체 시간 복잡도를 결정한다. 이 과정은 너비가 2인 사각형에서 시작해서 너비가 n인 사각형까지를 하나하나 검사하므로 시간복잡도는 O(n)이 된다.

저작자표시