분할 정복 안내서 · 6/6

실무에서의 분할 정복

실무에서 분할 정복을 처음부터 직접 짤 일은 많지 않지만, 매일 쓰는 도구 안에서는 분할 정복이 늘 돌아가고 있습니다. 이 장에서는 분할 정복이 쓰이는 곳, 먼저 찾아 쓸 라이브러리 함수, 직접 구현할 때 자주 하는 실수를 정리합니다.

쓰이는 곳

정렬 라이브러리: Python의 list.sort와 Java의 객체용 Arrays.sort는 병합 기반 정렬인 Timsort를 씁니다. Java는 기본형 배열을 듀얼 피벗 퀵 정렬로 정렬합니다. C++의 std::stable_sort는 보통 병합 정렬, std::sort는 인트로 정렬(힙 정렬로 대체할 수 있는 퀵 정렬)로 구현됩니다.
선택: C++의 std::nth_element와 numpy.partition(기본값 introselect)은 나쁜 피벗에 대비한 퀵셀렉트 변형입니다.
큰 수 계산: CPython은 일정 크기를 넘는 큰 정수를 카라추바로 곱하고, GMP 같은 라이브러리는 더 큰 수에서 Toom-Cook과 FFT 기반 방법으로 넘어갑니다.
신호 처리: 쿨리-튜키 FFT는 크기 n인 변환을 크기 n/2인 변환 두 개로 나누어 O(n^2)을 O(n log n)으로 줄입니다.
암호: RSA와 디피-헬먼은 수천 비트짜리 지수로 모듈러 거듭제곱을 하는데, 빠른 거듭제곱이 없으면 불가능한 계산입니다.
데이터베이스와 대용량 처리: 데이터가 메모리에 들어가지 않으면 외부 병합 정렬이 정렬된 조각을 디스크에 쓰고 병합합니다. 정렬 병합 조인, MapReduce 방식의 작업, Java의 fork/join 프레임워크도 일을 나누고, 조각을 따로 처리하고, 결과를 합칩니다.
디버깅: git bisect는 커밋 기록을 이진 탐색해 버그를 만든 변경을 찾습니다.

라이브러리를 먼저 쓰기

import heapq
import statistics

MOD = 1_000_000_007
print(pow(3, 10**18, MOD))        # 내장 모듈러 빠른 거듭제곱
print(pow(3, -1, MOD))            # 모듈러 역원(Python 3.8 이상)

data = [9, 1, 8, 2, 7, 3]
print(heapq.nsmallest(2, data))   # [1, 2], O(n log k)
print(statistics.median(data))    # 5.0
print(sorted(data))               # Timsort, 안정 정렬, O(n log n)

C++의 std::nth_element는 k번째 원소를 정렬된 자리에 놓고 나머지를 그 기준으로 나누며, 평균 선형 시간에 동작합니다.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{9, 1, 8, 2, 7, 3};
    std::nth_element(v.begin(), v.begin() + 2, v.end());
    std::cout << v[2] << '\n';  // 3, 세 번째로 작은 값
}

자주 하는 실수

재귀 깊이: Python의 기본 한도는 약 1000 프레임입니다. 균형 있게 나누면 깊이가 log n에 그치지만, 원소를 하나씩만 줄이는 분할(나쁜 피벗, 한쪽으로 치우친 트리)은 한도를 넘길 수 있습니다. 감소 정복은 반복문으로, 퀵셀렉트는 무작위 피벗으로 씁니다.
숨은 복사: a[:mid]는 리스트 절반을 복사합니다. 단계마다 슬라이싱해도 전체는 O(n log n)이지만 메모리 할당이 많아집니다. 속도가 중요하면 인덱스 범위를 넘기고 버퍼 하나를 재사용합니다.
너무 작은 부분 문제: 함수 호출은 비교 몇 번보다 비쌉니다. 실제 정렬 라이브러리는 작은 구간에서 삽입 정렬로 바꾸고, 카라추바도 작은 수에서는 일반 곱셈으로 돌아갑니다.
경계 실수: 구간을 반열린 [lo, hi)로 쓸지 닫힌 [lo, hi]로 쓸지 정하고 끝까지 지킵니다. mid = (lo + hi) // 2인 이진 탐색에서 lo = mid로 갱신하면 원소 두 개인 구간에서 lo가 움직이지 않아 무한 반복에 빠집니다.
오버플로: C++, Java, JavaScript에서는 두 나머지의 곱이 64비트나 2^53을 넘을 수 있습니다. 구현 장을 참고합니다.
같은 값: 로무토 분할은 모든 값이 같으면 O(n^2)으로 느려집니다. 연습 문제처럼 세 갈래 분할을 씁니다.

재귀 없이: 상향식 병합 정렬

병합 정렬은 폭 1, 2, 4, ...인 구간을 차례로 병합하면 재귀 없이도 동작합니다.

def merge_sort_bottom_up(a):
    a = list(a)
    n, width = len(a), 1
    while width < n:
        for lo in range(0, n, 2 * width):
            mid, hi = min(lo + width, n), min(lo + 2 * width, n)
            left, right = a[lo:mid], a[mid:hi]
            i = j = 0
            for k in range(lo, hi):
                if j == len(right) or (i < len(left) and left[i] <= right[j]):
                    a[k] = left[i]
                    i += 1
                else:
                    a[k] = right[j]
                    j += 1
        width *= 2
    return a

print(merge_sort_bottom_up([5, 2, 4, 7, 1, 3, 2, 6]))  # [1, 2, 2, 3, 4, 5, 6, 7]

외부 정렬과 병렬 병합도 이와 같은 모양으로 동작합니다.

정리

정렬, 선택, 큰 수 곱셈, FFT, 암호의 모듈러 거듭제곱은 모두 내부에서 분할 정복을 씁니다.
직접 짜기 전에 sorted, pow, heapq, std::nth_element, numpy.partition을 먼저 찾아봅니다.
직접 구현할 때는 재귀 깊이, 복사 비용, 작은 입력 처리, 오버플로, 같은 값을 확인합니다.

더 읽을거리

이 장에 대해 질문이 있나요?