분할과 정복 알고리즘: 재귀 분해와 결합 비용 설계

문제를 나누고 다시 합치는 설계

분할과 정복(Divide and Conquer)은 큰 입력을 더 작은 독립 하위 문제로 나눈 뒤 각각을 해결하고, 결과를 결합해 전체 해를 만드는 알고리즘 설계 방법이다. 정렬부터 수치 계산, 신호 처리, 공간 데이터 구조, 분산 처리까지 적용 범위가 넓으며 재귀 구조 덕분에 병렬화와 캐시 최적화에도 연결된다.

일반적인 흐름은 세 단계다. 먼저 문제를 a개의 하위 문제로 나누며, 각 문제의 크기를 n/b로 가정한다. 하위 문제는 재귀 또는 반복으로 해결하고, 충분히 작아진 베이스 케이스에서는 직접 처리한다. 마지막으로 하위 해를 결합하는데, 이 단계에는 f(n)의 비용이 든다.

전형적인 점화식은 다음과 같다.

T(n) = a·T(n/b) + f(n)

Master Theorem은 f(n)의 성장률에 따라 Θ(n^log_b a), Θ(n^log_b a log n), Θ(f(n)) 등의 형태로 복잡도를 판단하는 데 사용한다. 베이스 케이스도 설계 대상이다. 입력이 임계값 k 이하라면 삽입정렬 같은 단순 알고리즘으로 전환해 상수항을 줄일 수 있다.

분할 품질과 결합 비용을 함께 본다

Merge Sort는 입력을 균등하게 나누는 대표 사례이고, Quick Sort는 피벗에 따라 불균등하게 분할한다. 하위 문제가 서로 겹치지 않으면 전형적인 분할과 정복에 가깝지만, 중복된다면 메모이제이션이나 동적 계획법을 검토해야 한다. 임계값을 조정하면 재귀 깊이와 호출 오버헤드 사이의 균형도 바꿀 수 있다.

재귀 깊이는 보통 O(log_b n)으로 예상되므로 재귀 한도와 스택 사용량을 고려해야 한다. 꼬리 재귀를 제거하거나 명시적 스택으로 전환해 반복 형태로 구성할 수도 있다. 병렬 정복 단계에서는 워크-스틸링 같은 런타임 스케줄러를 활용할 수 있다.

결합 단계는 전체 성능을 좌우하기 쉽다. 연산의 결합법칙을 활용하거나 스트리밍 방식으로 결합하고, 캐시 친화적인 병합을 택해 f(n)을 줄이는 방식이 있다. 부동소수점 합산처럼 결합 순서가 결과에 영향을 주는 경우에는 순서를 고정해야 결과의 일관성을 유지할 수 있다. 외부 메모리 환경에서는 블록 단위 병합으로 순차 접근을 늘리는 편이 유리하다.

Merge Sort는 O(n) 보조공간을 쓰는 반면, Quick Sort는 평균적으로 O(log n) 스택을 사용한다. Quick Sort는 피벗 품질이 나빠지면 O(n^2) 위험이 있으므로 랜덤화나 Median-of-3로 완화할 수 있다. 작은 입력에서 단순 알고리즘으로 바꾸거나 캐시-오블리비어스 기법을 적용하는 것도 상수항과 메모리 접근 비용을 다루는 방법이다.

독립 하위 문제는 포크-조인 모델에 잘 맞는다. 각 작업을 병렬 실행하고 결합 지점의 동기화를 최소화할 수 있다. 분할로 작업 세트를 작게 유지하면 캐시 미스를 줄일 수 있으며, 캐시-오블리비어스 설계는 특정 계층에 묶이지 않은 최적화를 지향한다. 분할 단위 사이의 공유 상태는 false sharing과 동시성 제약을 만들 수 있으므로 제거하거나 최소화해야 한다.

⤢✕

정렬부터 분산 집계까지의 적용 방식

정렬과 검색에서는 Merge Sort, Quick Sort, Binary Search가 대표적이다. Merge Sort는 안정 정렬과 외부 정렬, 병렬 병합에 적합하다. Quick Sort는 평균 O(n log n)이며 인플레이스 특성이 강점이지만 피벗 전략이 중요하다. Binary Search는 분할된 검색 공간을 O(log n)에 탐색한다.

수치 연산과 신호 처리에서도 같은 구조가 쓰인다. Karatsuba 곱셈은 O(n^1.585)로 큰 정수 산술에 유리하다. Strassen 행렬곱은 O(n^2.807)이며 수치 안정성과 임계 크기를 검토해야 한다. FFT는 O(n log n)으로 주파수 분석과 컨볼루션 가속에 활용된다.

공간 데이터에서는 KD-Tree와 Quadtree가 공간을 분할해 최근접 및 범위 질의를 가속한다. 세그먼트 트리는 구간 합이나 최댓값 질의를 O(log n)에 처리한다.

분산 환경에서는 MapReduce 스타일의 입력 샤딩, 맵, 셔플, 리듀스 흐름이 분할과 결합 구조를 따른다. 이때 결합 함수에는 결합법칙이 요구된다. 외부 병합 정렬은 다중 런을 생성한 후 k-way 병합을 수행하며, 디스크 I/O를 순차화해 처리량을 높인다.

성능 기대와 운영상 제약

단순 O(n^2) 정렬을 O(n log n) 정렬로 전환하면 n=10^7에서 연산량이 ~142× 감소한다. 큰 정수 곱셈에 Karatsuba를 도입할 경우 n=10^6에서 이론상 지수 승수는 ~1.585로 축소된다.

병렬화 가능 비율 s=0.9, 코어 P=8을 Amdahl 법칙 근사에 적용하면 기대 가속비는 ≈ 1/(0.1 + 0.9/8) ≈ 4.71배다. 실제 체감 성능은 포크-조인 오버헤드와 임계값 조정에 따라 달라진다.

캐시 미스를 줄이고 I/O를 순차화하면 처리량 개선에 도움이 된다. 베이스 케이스와 결합 순서를 결정적으로 설계하면 결과의 일관성과 재현성도 확보할 수 있다.

알고리즘	성능(시간복잡도)	확장성(병렬화)	일관성(결과/성능)	안정성(최악의 경우)	운영 편의(메모리/구현)
Merge Sort	O(n log n)	높음	높음(안정 정렬)	높음	중(보조공간 O(n))
Quick Sort	평균 O(n log n)	높음	중(피벗 의존)	낮음(O(n^2) 가능)	높음(인플레이스, 구현 간단)
Karatsuba	O(n^1.585)	중	높음	중	중(임계 크기 필요)
Binary Search	O(log n)	낮음(작업량 작음)	높음	높음	높음(간단, 정렬 전제 필요)

임계값을 둔 안정 병합 정렬

다음 구현은 Python 3.10+와 표준 라이브러리만 사용한다. 비교 가능한 원소 시퀀스를 전제로 하며 안정 정렬을 보장한다.

from typing import List, TypeVar, Callable, Optional

T = TypeVar("T")

def insertion_sort(a: List[T], key: Optional[Callable[[T], object]] = None) -> None:
    key = key or (lambda x: x)
    for i in range(1, len(a)):
        cur = a[i]
        j = i - 1
        curk = key(cur)
        while j >= 0 and key(a[j]) > curk:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = cur

def merge(left: List[T], right: List[T], key: Optional[Callable[[T], object]] = None) -> List[T]:
    key = key or (lambda x: x)
    i = j = 0
    out: List[T] = []
    append = out.append
    while i < len(left) and j < len(right):
        if key(left[i]) <= key(right[j]):  # 안정성 보장(<=)
            append(left[i]); i += 1
        else:
            append(right[j]); j += 1
    if i < len(left): out.extend(left[i:])
    if j < len(right): out.extend(right[j:])
    return out

def merge_sort(a: List[T], key: Optional[Callable[[T], object]] = None, threshold: int = 32) -> List[T]:
    """
    안정 병합 정렬. 길이 ≤ threshold 시 삽입 정렬로 전환해 상수항 최적화.
    시간복잡도: O(n log n), 공간: O(n). 재귀 깊이: O(log n).
    """
    n = len(a)
    if n <= 1:
        return a[:]  # 안전 복사
    if n <= threshold:
        b = a[:]
        insertion_sort(b, key)
        return b
    mid = n // 2
    left = merge_sort(a[:mid], key, threshold)
    right = merge_sort(a[mid:], key, threshold)
    return merge(left, right, key)

if __name__ == "__main__":
    data = [5, 2, 9, 1, 5, 6, 7, 3, 8, 4]
    print(merge_sort(data))

임계값은 CPU 캐시와 분기 예측 특성에 맞춰 16~64 범위를 탐색할 수 있다. 큰 입력이나 깊은 재귀에서는 파이썬 재귀한도(sys.setrecursionlimit) 또는 반복화를 고려한다. 좌우 하위 문제는 프로세스 풀로 병렬 처리할 수 있지만, 분할이 과도하면 오버헤드가 커질 수 있다.