분할 정복(Divide and Conquer)

분할 정복이란?

 

 

큰 문제를 작은 문제로 나누고, 그 작은 문제들에 대한 결과를 이용하여 큰 문제의 답을 구하는 방법이다.

 

 

재귀적으로 함수를 호출하면서 계산 범위를 조금씩 줄여가는 방식으로 진행된다.

 

 

분할: 주어진 문제를 2개 이상의 여러 부분 문제로 나눈다.(문제가 작아지면 풀기 쉬워지는 성질 이용)

 

 

정복: 여러 해결된 부분 문제들로 조금 더 큰 문제를 해결하여 최종적으로 답을 풀어내는 것

 

 

 

 

 

 

https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

 

$A$의 $B$제곱을 $C$로 나눈 나머지를 구하는 문제로, 분할 정복의 대표적인 예시이다.

 

 

$B$가 너무 크기 때문에 $A$를 $B$번 곱하는 단순한 방법으로는 풀리지 않는다.

 

 

따라서 분할 정복을 이용하는 방식으로 풀 것이다.

 

 

예를 들어 $2^{6}$을 구하려고 할 때, $2^{6}$은 $2^{3}$을 제곱해서 구할 수 있다.

 

$2^{3}$은 $2$·$2^{2}$이다.

 

$2^{2}$은 $2^{1}$을 제곱해서 구할 수 있다.

 

$2^{1} = 2$이므로 $2^{2} = 4$이고 $2^{3} = 8$이고 따라서 우리가 원하는$2^{6}$의 값은 $64$이다.

 

 

정리하자면, $B$가 짝수일 때 $A^{B}$는 $A^{B/2}$의 제곱이고 $B$가 홀수일 때 $A^{B}$는 $A^{(B-1)}·A$이다.

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    long long a, b, c;
    cin >> a >> b>> c;
    cout << DnC(a, b, c) << "\n";
    return 0;
}

 

 

 

 

 

https://www.acmicpc.net/problem/6549

6549번: 히스토그램에서 가장 큰 직사각형

 

 

히스토그램 문제는 분할 정복의 대표적인 문제로, 구간을 쪼개서 문제를 $O(NlogN)$에 해결하는 문제이다.

 

 

히스토그램의 중간 부분을 기준으로 좌우로 나누어 주면서 문제를 해결해준다.

 

 

처음~중간 부분으로 분할, 중간~끝 부분으로 분할하는 두 가지 경우가 존재하고, 중간 부분을 포함하는 경우가 존재하여 총 세가지 경우를 고려해야한다.

 

 

풀이: BOJ 6549 히스토그램에서 가장 큰 직사각형

 

 

 

 

 

 

분할 정복은 관리하는 구간을 매번 반으로 나누는 성질을 가진 세그먼트 트리를 비롯하여 이분 탐색, 병합 정렬, 거듭제곱 연산 등에 사용된다.

 

 

또한 동적계획법이나 히르쉬버그 알고리즘 등 다양하게 응용되므로 충분히 연습해야 하는 테크닉이다.