25. Divide and Conquer

분할 정복(Divide and Conquer)은 큰 문제를 여러 개의 작은 부분 문제로 분할한 다음 각각의 부분 문제를 해결하고, 그 결과를 바탕으로 큰 문제의 답을 구하는 문제 해결 방법이다. 동적 계획법과 설명이 비슷하지만 동적 계획법에서는 중복되는 부분 문제가 있었다. 분할 정복의 부분 문제들은 서로 중복되지 않는다.

 

분할 정복에도 기저 사례가 존재하며, 기저 사례는 더 작은 부분 문제로 분할하지 않고 바로 해결할 수 있다. 분할 정복 자체가 재귀함수를 이용하여 구현하는 경우가 많기 때문에 코드에 자연스럽게 추가되기도 한다.

 

BOJ 1629. 곱셈 (Silver I)

지수가 큰 경우의 거듭제곱을 구하는 문제가 분할 정복을 사용하는 대표적인 예시이다. 지수가 크기 때문에 $B$번 반복되는 반복문을 쓰면 시간 초과를 피할 수 없다. 하지만 $x^{2n}=x^n\times x^n,x^{a+b}=x^a \times x^b$라는 성질을 이용하면 $\Theta(\text{lg }B)$번의 곱셈만으로 $A$의 $B$제곱을 구할 수 있다. 원리는 $B$를 $2$의 거듭제곱의 합으로 나타낸 다음 $A$의 $2^n$제곱을 적절히 곱하는 것이다. 예를 들어 $B=11$인 경우, 이 값을 $2$의 거듭제곱의 합으로 나타내면 $8+2+1$이 되고, $A^{11}=A^8\times A^2\times A$로 구할 수 있다. 이 방법이 바텀업을 이용한 것이고, 탑다운 방식의 좀더 직관적인 풀이가 있는데, $B$가 짝수일 경우 $A^B=A^{B/2}\times A^{B/2}$이므로 $A^{B/2}$를 계산한 후 제곱을 하면 되고, $B$가 홀수일 경우 $A^B=A^{B-1}\times A$이므로 $A^{B-1}$을 계산하고 $A$를 곱하면 된다. $B$가 홀수이므로 $B-1$은 짝수가 될 것이다. 이는 재귀호출로 간단하게 구현할 수 있다. 재귀함수를 작성할 때 주의해야 할 점은 $B$가 짝수일 때의 처리를 다음과 같이 하면 안 된다는 것이다.

int pow(int a, int b, int c)
{
    if(b == 0)return 1;
    else if(b % 2)return pow(a, b-1, c) * a % c;
    else return pow(a, b/2, c) * pow(a, b/2, c) % c;
}

$B$가 짝수일 때 함수 호출이 두 번 되기 때문에 분할 정복의 의미가 없어지게 된다. 이 코드를 다음과 같이 수정하면 분할 정복의 의미를 살릴 수 있다.

int pow(int a, int b, int c)
{
    if(b == 0)return 1;
    else if(b % 2)return pow(a, b-1, c) * a % c;
    else
    {
        int k = pow(a, b/2, c);
        return k * k % c;
    }
}

$B$가 짝수일 때 함수 호출을 한 번만 하고 같은 결과를 얻게 된다. 위의 문제의 경우 입력값이 크므로 $8$바이트 정수 자료형을 써야 한다.

 

이외에도 다양한 종류의 분할 정복 기법이 존재한다. 또한 단독으로 쓰이지 않고 다른 알고리즘의 일부로 사용되는 경우도 자주 찾아볼 수 있다.

 

[연습문제]

 

BOJ 1780. 종이의 개수 (Silver II)

이 글에 나온 연습문제인 2630번과 거의 같은데 이 문제는 종이를 $3 \times 3$으로 분할한다. 나머지는 2630번과 같은 방법으로 풀 수 있다.

 

BOJ 2447. 별 찍기 - 10 (Silver I)

재귀함수로 패턴을 만드는 문제이다. 중간중간에 생기는 패턴을 저장한 다음 한꺼번에 출력해야 한다.

 

→ solved.ac tag: divide_and_conquer