분할 정복(Divide and Conquer)

Jeonghwan Yoon·2025년 3월 30일

분할정복이란

큰 문제를 작은 문제로 분할(Divide)
작은 문제를 해결(Conquer)
해결한 결과를 다시 합침(Combine)
대표 알고리즘 설계 기법 중 하나로, 재귀 기반으로 구현됨

주요 특징

항목	설명
재귀 기반	반복되는 구조로 재귀적 해결
성능 향상	대부분의 경우 O(log N) 또는 O(N log N) 성능
조합 가능성	이분 탐색, 정렬, 수학 문제 등 다양한 분야에서 사용 가능
구조적 사고 훈련	문제를 나누고 합치는 사고 방식에 익숙해질 수 있음

적용 알고리즘 예시

알고리즘	시간 복잡도	설명
이분 탐색	O(log N)	범위를 반으로 나눠 탐색
거듭제곱	O(log N)	`a^n` 계산 시 중복 제거
병합 정렬	O(N log N)	정렬 후 병합
퀵 정렬	평균 O(N log N) / 최악 O(N²)	피벗 기준 분할 정렬
최대 구간합	O(N log N)	중간을 기준으로 최대값 계산

코드 예시 1: 거듭제곱

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

O(log N)
중복 계산 없이 효율적 거듭제곱

코드 예시 2: 병합 정렬 (Merge Sort)

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged += left[i:]
    merged += right[j:]
    return merged

O(N log N)
리스트 슬라이싱, append 사용

전제 조건

문제를 작게 쪼갤 수 있어야 함
쪼갠 결과를 합쳐서 원래 문제로 복원 가능해야 함
재귀 종료 조건이 명확해야 함 (base case)

실전 적용 예시

유형	적용
정렬	병합 정렬, 퀵 정렬
탐색	이진 탐색
수학	`aⁿ`, 행렬 거듭제곱
재귀적 구조	색종이 분할, 쿼드트리
구간 문제	최대 구간합 등 분할 계산 가능 문제

장점과 단점

구분	내용
장점	복잡한 문제를 단순화, 성능 향상
단점	재귀 호출에 따른 스택 오버플로우, 메모리 증가 가능성

C언어 전환 시 유의점

항목	C언어에서의 구현 방식
슬라이싱	사용 불가 → 시작/끝 인덱스 수동 처리
append	배열 인덱싱 또는 포인터
동적 배열	malloc, realloc 등 직접 메모리 관리
재귀 깊이	스택 오버플로우 주의