Divide and Conquer (분할 정복)

Divide and Conquer (분할 정복): 큰 문제를 작은 하위 문제로 나누어 각각 해결한 뒤, 결과를 결합하여 원래 문제를 해결하는 알고리즘 기법.

• Independent Subproblems (독립적인 하위 문제)에 적합.
• 하위 문제가 반복되는 Overlapping Subproblems (중복 부분 문제)는 Dynamic Programming (동적 계획법)으로 최적화할 수 있음.
• 일반적으로 Recursion (재귀)을 활용하여 구현.

1. How It Works (동작 원리)

1. Divide (분할): 문제를 더 작은 하위 문제로 분할.
2. Conquer (정복): 하위 문제를 재귀적으로 해결. Base Case (기저 조건)에 도달하면 직접 해결.
3. Merge / Combine (병합 / 결합): 하위 문제의 결과를 결합하여 최종 해답 생성.

Merge Sort vs Quick Sort

구분	Merge Sort	Quick Sort
Divide	배열을 절반으로 분할	Pivot 기준 Partition
Conquer	각 부분 배열 재귀 정렬	각 부분 배열 재귀 정렬
Merge	정렬된 배열 병합	별도 병합 불필요

• Merge Sort: Merge 과정이 핵심.
• Quick Sort: Divide(Partition) 과정이 핵심.

2. Complexity Analysis (복잡도 분석)

일반적인 Recurrence Relation (점화식):

[
T(n)=aT(n/b)+f(n)
]

• n: 입력 크기.
• a: 생성되는 하위 문제 개수.
• n/b: 각 하위 문제의 크기.
• f(n): 분할·병합 등 재귀 호출 외부의 작업 비용.

하위 문제가 동일한 크기일 때 Master Theorem (마스터 정리) 등을 이용해 복잡도 계산 가능.

예시: Merge Sort

[
T(n)=2T(n/2)+O(n)=O(n\log n)
]

3. Examples and Applications (대표 알고리즘)

알고리즘	핵심 아이디어	Time
Power Function (거듭제곱)	지수를 절반씩 줄이며 제곱	O(log N)
Binary Search (이진 탐색)	정렬된 탐색 범위를 절반으로 축소	O(log N)
Closest Pair of Points (최근접 점 쌍)	점들을 분할하고 경계의 후보까지 검사	O(N log N)
Strassen's Algorithm (스트라센 행렬 곱셈)	행렬을 분할하여 곱셈 횟수 감소	O(N^2.8074)
FFT (고속 푸리에 변환)	변환을 짝수·홀수 부분 문제로 분할	O(N log N)
Karatsuba Algorithm (카라추바 곱셈)	큰 정수 곱셈을 3개의 작은 곱셈으로 분할	O(N^1.585)
Merge Sort (병합 정렬)	분할 → 정렬 → 병합	O(N log N)
Quick Sort (퀵 정렬)	Pivot으로 분할 후 재귀 정렬	평균 O(N log N)

※ Strassen의 지수는 원문의 2.8974가 아닌 약 2.8074가 정확함. Quick Sort의 최악 시간 복잡도는 O(N²).

4. Advantages (장점)

• Problem Decomposition (문제 분해): 복잡한 문제를 작은 문제로 단순화. 예: Tower of Hanoi (하노이 탑).
• Algorithm Efficiency (알고리즘 효율성): 불필요한 연산을 줄여 효율적인 알고리즘 설계 가능.
• Parallelism (병렬성): 독립적인 하위 문제를 여러 프로세서에서 병렬 처리 가능.
• Cache Locality (캐시 지역성): 작은 하위 문제의 데이터가 캐시에 들어가면 메모리 접근 효율 향상. 일부 분할 정복 알고리즘은 Cache-Oblivious (캐시 크기 독립적 최적화) 특성을 가짐.

5. Disadvantages (단점)

• Overhead (오버헤드): 재귀 호출·분할·병합에 추가 비용 발생.
• Complexity (복잡성): 하위 문제 간 의존성으로 설계가 복잡해질 수 있음.
• Implementation Difficulty (구현 난이도): 효율적인 분할·결합 방법을 찾기 어려울 수 있음.
• Memory Usage (메모리 사용량): 재귀 스택 및 중간 결과 저장에 추가 메모리 필요.

핵심: Divide and Conquer는 Divide → Conquer → Merge를 통해 큰 문제를 작은 문제로 분해하여 해결하는 기법. 하위 문제의 독립성과 효율적인 분할·결합 방법이 성능을 결정함.