18. 분할 정복

분할 정복

빠른 설명

분할 정복은 문제를 더 작은 문제로 나누고, 각각을 해결한 뒤 결과를 합치는 방식이다.

언제 쓰는가

• 큰 문제를 절반 정도로 나눌 수 있을 때
• 병합 정렬, 퀵 정렬, 거듭제곱, 이진 검색
• 구간을 나누어 답을 합칠 수 있을 때

시간복잡도 예시

• 빠른 거듭제곱: $O(\log N)$
• 병합 정렬: $O(N\log N)$

참고자료

• Wikipedia - Divide-and-conquer algorithm
• GeeksforGeeks - Divide and Conquer
• CP-Algorithms - Binary Exponentiation

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
long long power(long long a, long long n) {
    if (n == 0) return 1;
    long long half = power(a, n / 2);
    if (n % 2 == 0) return half * half;
    return half * half * a;
}
 
int main() {
    cout << power(2, 10) << '\n';
}

Python 코드

def power(a, n):
    if n == 0:
        return 1
    half = power(a, n // 2)
    if n % 2 == 0:
        return half * half
    return half * half * a
 
print(power(2, 10))