[ 개념 ] 40. 분할정복(Divide and Conquer) 알고리즘

> 분할 정복(Divide and Conquer) 알고리즘

이번에 소개해 드릴 것은 역시 유명한 기법인 분할 정복(Divide and Conquer)입니다.

탐색, DP, 그리디 등에 비해서는 등장빈도가 좀 낮지만, 이 기법의 성질 자체가 직접 문제푸는데 뿐 아니라 다른 여러 효율적인 자료구조나 알고리즘에 기여할 때가 많습니다.

분할 정복은 말 그대로 문제를 두 단계, ①분할과 ②정복으로 나눠서 해결하는 것을 말합니다.

분할하는 단계에서는 말 그대로 주어진 문제를 여러 개의 부분 문제들로 나누는데,

문제가 작아지면 작아질수록 풀기 쉬워지는 성질을 이용한 겁니다.

또한 문제의 크기가 엄청나게 줄어든다면(N=1 또는 N=2 정도) 그야말로 바로 답을 구할 수 있는 수준이 되고, 이게 재귀호출로 문제를 풀 때의 기저 사례(base case)와 같습니다.

그렇습니다. 대체로 분할 정복은 재귀 호출과 아주 죽이 잘 맞습니다.

그리고 기저 사례들로 각 문제의 답을 풀고, 그 문제들을 불렀던 조금 더 큰 문제는 이 답들을 통해 비교적 간단한 연산처리만 해주면 자신의 답도 구할 수 있습니다.

이런 식으로 첫 문제까지 쌓아올려가며 답을 풀어내는 것이 최종 목적.

이것이 분할 정복 알고리즘의 대략적인 묘사도입니다.

맨 위의 청록색 문제가 우리가 풀어야 할 문제이고, 그걸 각각 2개의 부분 문제들로 나눠갑니다.

그리고 분홍색까지 쪼개졌을 때 그들은 기저 사례가 되어서 바로 풀 수 있고, 푼 뒤 이들을 나눴던 대로 다시 합쳐 나갑니다.

그냥 풀었을 때보다 오히려 할 일이 많아지지 않을까? 하며 생각하실 수도 있습니다.

그러나 이 기법이 먹히는 경우는, 그냥 풀었을 때보다 저렇게 이미 풀린 부분 문제들을 합치는 게 월등히 빠른 경우입니다.

아주 대표적인 예가 병합 정렬(merge sort), 이분 탐색(binary search), 거듭제곱 연산(a^b) 등입니다.

가장 많이 보이는 경우인, 문제를 정확히 양분하여 2개의 절반 크기의 문제로 분할하는 경우를 생각해 봅시다.

이때 이 문제를 푸는 데는 얼마의 시간이 걸릴까요?

주의!! 고등 수학 지식이 다소 필요합니다(로그, 수열의 합).

먼저 문제의 크기(보통 값의 개수를 의미합니다)를 N이라 할 때, 한 단계 분할 후 문제의 크기는 N/2가 될 것입니다. 자명하죠.

그렇다면 기저 사례가 N=1인 문제라고 할 때, 이 문제는 몇 단계까지 분할될까요? log₂N 단계입니다.

N이 2의 거듭제곱꼴일 땐 정확히 log₂N 단계이고, 그것보다는 클 때는 조금 더 많이 분할될 수도 있지만 많아봐야 문제 크기가 N*2일 때를 넘지 못합니다.

즉, 2^(k-1) < N <= 2^k일 때 문제는 k단계까지 분할됩니다. 간단히 그냥 O(logN)단계로 표현할 수 있죠.

그리고 각 단계를 잘 살펴보면, 맨 위 문제부터 0단계, 1단계, ... k단계라고 분류하면 위에서부터 각 단계에 해당하는 부분 문제의 수는 1개, 2개, 4개, 8개, ... 2^k개입니다.

이제 병합 정렬의 경우를 예로 들어서 얼마나 시간이 단축되는지 설명해보겠습니다.

분할 정복 알고리즘의 수행시간은 문제마다 다 다른데, 여기서 필요한 것은 분할할 때 ①나누어지는 문제의 개수, ②**분할 후 문제의 크기, **③각 문제마다 병합(정복) 단계에서 걸리는 시간이 결정하기 때문입니다.

병합 정렬의 경우, 분할할 해당 문제 크기를 N이라 할 때 ①2, ②N/2, ③O(N)입니다. 일단 ①, ②번은 위 그림의 상황과 일치하고, ③ 정보를 통해 최종 시간복잡도를 구할 수 있습니다. (③번이 왜 O(N)인지는 여기서는 설명하지 않겠습니다. 병합 정렬에 대해 찾아보시길.)

분할을 다 했으니 이제 역순으로 저걸 병합해 나갈 차례인데, 아까 살펴본 것처럼 각 단계의 부분문제의 개수가 있습니다.

k-1단계에서는 2^(k-1)번, ... 2단계에서는 2^2=4번, 1단계에서는 2번, 0단계에서는 1번의 병합을 해야 하는데 각 병합에 걸리는 시간이 해당 문제 크기가 N일 때 O(N)이라 했죠.

그러므로 각 단계별로 드는 연산 횟수를 죽 늘어놓았을 때

0단계: 1 * O(N)

1단계: 2 * O(N/2)

2단계: 4 * O(N/4)

...

m단계: 2^m * O(N/(2^m)) = O(N)

...

따라서 단계별 식을 일반화해 보면 각 단계에서 드는 총합 연산량은 O(N)입니다. 이는 매 단계마다 각 문제의 크기 역시 지수적으로 줄어들기 때문이죠!

그리고 아까 봤듯이 단계는 총 O(logN)개 있으므로, 이를 곱해서 O(NlogN)이라는 시간복잡도를 구할 수 있습니다!

버블 정렬, 선택 정렬 등의 기본적인 알고리즘이 O(N^2)이라는 점에서 보면 굉장한 발전이라고 할 수 있으며, 현재 일반적인 알고리즘 중 가장 빠른 퀵 정렬 또한 분할 정복 기법을 사용합니다.

C++의 STL에 속한 sort 함수, C의 qsort 함수 등 여러 언어의 라이브러리에서 이 빠른 분할 정복을 베이스로 한 정렬 함수를 지원합니다.

이제 고등 수학 수준의 수열의 합에 대한 지식이 있다면, 위에서 언급한 ① ② ③이 무엇이냐에 따라 바로 전체 시간복잡도를 구해낼 수 있는, 즉 분할 정복 기법 시간복잡도의 일반화인 마스터 이론(Master Theorem)을 이해하는 것도 가능합니다.

① ② ③ 값이 각각 a, b, d와 대응합니다. 그러나 형태가 조금 바뀌었으므로 알아서 변환해 넣으셔야 합니다.

원리를 찾아보시면 위 과정과 비슷하게 진행되므로 시간을 들여 천천히 보시면 무리없이 이해 가능합니다.

그럼 아까 언급했던 다른 예를 조금만 봅시다.

이분 탐색이 간단한 예인데, N개의 정렬되어 있는 수들 중 어떤 값 K의 위치를 찾아내거나, 없다는 것을 판정하는 탐색입니다.

그냥 차례대로 훑어보면 O(N)이지만, 정말 놀랍게도 이분 탐색은 O(logN)의 시간복잡도를 자랑합니다.

우리는 이 N=10인 배열에서 값 8을 찾으려고 합니다.

먼저 우리가 할 일은 이렇게 가장 가운데 지점을 피벗으로 삼는 겁니다.

보통 시작 인덱스 번호와 끝 인덱스 번호의 평균을 내는데, 이게 홀수일 경우 맘대로 올림하거나 내림하면 됩니다. 그래도 절반에 가까운 건 변하지 않기 때문. 저는 이번 예제에서는 아무렇게나 하겠습니다.

이제 이 중심점의 값보다 8이 큰지 작은지, 아니면 중심점이 8인지 검사합니다. 중심점이 8이라면 5번 인덱스에서 찾은 것이죠.

일단 값이 15이고 우리가 찾을 값이 8이니까, 오름차순 정렬이 되어있다는 배열의 특성상 15 오른쪽에는 절대 8이 없습니다. 따라서 우리는 15보다 왼쪽 값들만 찾으면 됩니다.

자, 그럼 값이 절대 없다고 판명난 곳을 까맣게 칠해버리고 이어서 찾아봅시다.

이제 문제는 배열 [2, 5, 7, 8, 9]에서 값 8을 찾는, 더 작은 문제로 바뀌었음을 알 수 있습니다. 그렇습니다. 문제가 분할된 거죠.

여기서도 마찬가지로 중심점을 찾아 그 값을 보니 7이고, 7보다 8이 크니까 7 왼쪽엔 절대 8이 없다는 걸 알 수 있습니다.

또 줄어들었습니다. 이제 뭐 값도 2개밖에 안 남았지만 말이죠, 일단 9를 중심점으로 뽑았다고 합시다.

8은 9보다 작죠? 그렇습니다. 8은 7 오른쪽, 9 왼쪽에 있을 수밖에 없는 겁니다.

마지막에 남은 게 달랑 값 하나라 중심점 후보도 하나밖에 없는데, 그게 8이라 찾았습니다.

만약 값이 하나도 안 남았는데(구간 왼쪽 끝과 오른쪽 끝이 같아지거나 하는 점으로 판별 가능) 아직도 못 찾았다면, 그 값은 배열 안에 없다고 판정할 수 있습니다.

극단적인 예를 보여드리기 위해 마지막에 값을 찾는 걸 보여드렸지만 만약 여기서 7을 찾았다던가 하면 단 두 단계만에 찾았겠지요.

이 이분 탐색 예제는 굉장히 특이하게도 별도의 병합 과정조차 필요없습니다. 왜냐면 분할을 하긴 하는데 그 중 한 문제만 풀면 되기 때문.

따라서 마스터 이론에 a=1, b=2, d=0을 대입하면 되고 시간복잡도는 가운데 케이스가 되어 O(logN)이 됩니다.

이진 탐색을 해주는 함수 또한 여러 언어가 제공하는데, C++의 경우 존재하는지만 알려주는 binary_search(), 아예 위치를 찾아주는 lower_bound(), upper_bound() 등이 존재합니다.

lower_bound()는 찾을 값 이상의 값이 처음 등장하는 곳을, upper_bound()는 찾을 값보다 큰 값이 처음 등장하는 곳을 찾아줍니다.

또다른 유명한 문제로는 워낙 풀이가 여러가지이기로 소문난 히스토그램 문제입니다.

이렇게 넓이가 일정한 직사각형들이 이어붙여져 있는데, 이 영역들 사이에 숨어있는 가장 큰 면적의 직사각형을 찾으라는 겁니다.

직사각형 개수 N이 최대 100,000이나 되므로 O(N^2)는 무리, 최소한 O(NlogN), O(N) 정도는 되어야 풀 수 있을 겁니다.

로그가 잘 뜨는 분할 정복 특성상 O(NlogN)일 것 같죠? 그리고 놀라운 사실은 스택을 사용하는 O(N) 알고리즘이 있다는 것이지만, 일단 여기서는 분할 정복 방법을 살펴봅시다.

여기서는 방법이 좀 더 복잡합니다. 일단 여태 그래왔듯이 직사각형들을 왼쪽 반, 오른쪽 반으로 쪼개서 양쪽 문제를 풀면 좋을 것입니다.

그렇게 되면 왼쪽 영역에서 찾은 제일 큰 직사각형, 오른쪽 영역에서 찾은 제일 큰 직사각형 중 큰 게 답이겠...지요 는 잠깐.

이 경우, 분할점에 진짜 답이 걸쳐 있을 수가 있습니다. 즉 왼쪽 오른쪽 부분을 나누는 기준점을 직사각형이 포함하고 있는 경우, 단순히 양쪽 부분 문제들은 걔네를 못 찾을 확률이 큽니다.

사실, 매번 문제를 N=1일 때까지 쪼갤 거라서 이 경우를 처리해주지 않으면 기껏해야 넓이 1이고 가장 긴 직사각형밖에 못 찾을 겁니다...

따라서 조금 더 복잡한데, 매번 문제를 병합할 때마다 가장 중간부터 시작하여 영역을 확장해 나가며 양쪽 영역에 걸친 것들 중 가장 넓은 직사각형을 찾는 방법이 있습니다.

처음엔 가장 가운데의 넓이 1~2 정도로 시작한 후 직사각형을 양쪽으로 넓혀가는 것인데, 매 단계마다 넓이를 1씩 확장하되 바로 왼쪽과 오른쪽 중 높은 곳부터 확장해 나가야 합니다.

이 예제를 봅시다. 심히 찌부러지게 그려놨지만 왼쪽부터 높이가 [6, 2, 5, 4, 5, 1, 6]입니다.

예제는 http://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/ 여기 있는 걸 그대로 썼습니다.

일단 제일 가운데의 직사각형부터 시작합니다. 넓이 1, 높이 4인 상태로 시작합니다.

그 다음, 빨간 직사각형 양옆의 높이가 5, 5인데 어느 쪽으로 확장해도 빨간 직사각형의 높이는 줄어들지 않으므로 아무 쪽으로나 확장합시다.

저는 오른쪽을 선택했고 현재 넓이는 2*4=8.

그 다음, 왼쪽 높이는 5고 오른쪽 높이는 1(!!!!)이니까 왼쪽으로 확장합니다. 넓이는 3*4=12.

그 다음, 왼쪽 2 오른쪽 1이니까 왼쪽으로 확장하는데, 이때는 양쪽 높이가 다 현재 높이 4보다 작으니까 높이가 줄어들 수밖에 없습니다. 넓이는 4*2=8이 됩니다.

그 다음 왼쪽으로 확장합니다. 넓이는 5*2=10. 이번엔 높이가 줄지 않죠.

왼쪽으로는 더 확장할 수 없으므로 오른쪽으로. 이때 높이가 또 줄어듭니다.

넓이는 6*1=6......

마지막 확장을 하고 나면 넓이는 7*1=7이고,

지금까지 확장하면서 생겼던 최대 넓이인 12가 중간점에 걸친 직사각형 중 최대 영역입니다.

이걸 구하는 시간은 O(N)이라는 것을 어렵지 않게 알 수 있습니다.

또한 이 병합 과정에서 사용하는 방법도 하나의 그리디 기법이라 할 수 있으며, 이렇게 기초적인 기법들은 다른 좀 더 어려운 알고리즘에서 직/간접적으로 많이 등장합니다.

어쨌든 이렇게 문제를 병합할 때마다 해당 문제의 답은 왼쪽 영역에서 얻어진 최대 영역, 오른쪽 영역에서 얻어진 최대 영역, 양쪽 영역에 걸친 직사각형 중 최대 영역 이 3가지 중 최댓값이 됩니다.

마스터 이론에 대입해보면 a = 2, b = 2, d = 1이므로 시간복잡도는 O(NlogN)입니다.

#include <cstdio>
#include <algorithm>
using namespace std;

int N, H[100000];

// 분할 정복으로 히스토그램 [s, e) 문제를 푸는 함수
int histogram(int s, int e){
    if(s == e) return 0; // base case: 넓이 0
    if(s+1 == e) return H[s]; // base case: 넓이 1

    int mid = (s+e)/2;
    int result = max(histogram(s, mid), histogram(mid, e)); // 각 양쪽 구간의 최댓값

    // 양쪽 구간에 걸쳐 있는 답을 O(e-s)에 찾음
    int w = 1, h = H[mid], l = mid, r = mid;
    while(r-l+1 < e-s){
        int p = l>s ? min(h, H[l-1]) : -1; // 왼쪽으로 확장했을 경우의 높이
        int q = r<e-1 ? min(h, H[r+1]) : -1; // 오른쪽으로 확장했을 경우의 높이
        // 더 높은(같은) 높이를 가진 쪽으로 확장
        if(p >= q){
            h = p;
            l--;
        }
        else{
            h = q;
            r++;
        }
        // 최댓값 갱신
        result = max(result, ++w*h);
    }
    return result;
}

int main(){
    scanf("%d", &N);
    for(int i=0; i<N; i++)
        scanf("%d", H+i);
    printf("%d\n", histogram(0, N));
}

분할정복 추천문제

1629번: 곱셈

A^B를 구하는 문제입니다. 이때 B가 무지막지하게 크기 때문에 2147483647번 곱하다가는 걍 시간초과입니다.

잘 생각해 보면 B가 짝수일 때 A^B는 A^(B/2)의 제곱입니다. B가 홀수일 때는 A^(B/2)*A이고요.

이렇게 연산량을 대폭 줄일 수 있고 시간복잡도는 O(logB)가 됩니다.

중간에 발생할 수 있는 오버플로우를 조심하시고, 가급적이면 long long 자료형을 사용하시며 나머지 연산을 즉각즉각 해주시는 것이 좋습니다.

2104번: 부분배열 고르기

히스토그램 문제와 굉장히 유사한 풀이를 갖고 있습니다.

계속 문제를 양분하며, 왼쪽 구간에 답이 있는 경우, 오른쪽 구간에 답이 있는 경우, 정답을 가진 영역이 양쪽에 걸친 경우 3가지를 고려해 그 중 최댓값을 리턴하면 됩니다.

1725번: 히스토그램

위에서 설명한 그 문제입니다.

저는 스택을 써서 풀었기에 깃헙의 코드는 도움이 안 될지도...

위의 부분배열 구하기 문제와 풀이가 아주 유사하므로 그 코드를 참고하시는 게.

1780번: 종이의 개수

전체 영역이 모두 같은 값이라면 한 장만 사용해도 좋은 기저 사례이고,

그게 아니라면 가로 3, 세로 3 영역으로 9등분하여 각 영역에 대해 재귀호출해 분할하여 문제를 풀고,

마지막에 각 영역의 답을 모두 더하는 합병 과정을 거칩니다.

a = 9, b = 9, d = 1이므로 시간복잡도는 O(NlogN)이고, N이 최대 3^7 = 2187이므로 충분한 수치.

1992번: 쿼드 트리

역시 정말 유명한 분할 정복 응용 문제 중 하나이고, 바로 위 종이의 개수 문제와 풀이가 아주 유사합니다.

이 경우는 값에 따라 출력을 해야 하는데 문제에서 주어진 것처럼 좌상단->우상단->좌하단->우하단 순서로 부분문제를 풀어야만 하는 점만 지켜주면 어렵지 않습니다.

1074번: Z

영역을 정확히 좌상단, 우상단, 좌하단, 우하단으로 4등분할 수 있고 방문하는 순서도 순서대로입니다.

쿼드 트리 문제와 비슷하게 풀 수 있고 이 문제는 분할 후에도 단 하나의 문제만 찾아가 풀면 됩니다.

문제가 줄어들 때마다 해당 영역 안에 있는 좌표로 조정해주는 것이 풀기 쉽습니다. 그리고 지나쳐온 다른 영역의 크기를 다 더해주면 됩니다.

2447번: 별 찍기 10

전역 배열을 하나 만들고 재귀호출을 해가며 각 칸을 채우는 것이 효율적입니다.

역시 주어진 영역을 9등분하여 가운데는 채우지 않고 나머지 8개 영역은 똑같이 재귀적으로 채워 나갑니다. 영역의 크기가 1이 됐다면 *로 채웁니다.

2339번: 석판 자르기 (★)

구현하기 상당히 난감한 문제.

매번 가능한 모든 경우를 다 시도해 보며(즉, 있는 모든 불순물에 대해 한번씩 시도해 보며) 얻은 경우의 수를 다 합칩니다.

이때 불순물을 기준으로 석판을 2조각 낼 텐데 각 조각에 따라 다시 재귀호출로 문제를 풀어서 분할 정복 기법을 사용합니다.

양쪽의 경우의 수가 A, B일 때 이 문제의 최종 답은 경우의 수 성질에 의해 A*B임을 주의하세요.