C++ 분할정복 완벽 가이드 | 병합정렬·퀵소트·이진탐색·클로스페어 [실전]
![C++ 분할정복 완벽 가이드 | 병합정렬·퀵소트·이진탐색·클로스페어 [실전]](/og/s/cpp-series-54-10-divide-conquer.webp)
이 글의 핵심
C++ 분할정복(Divide and Conquer) 패턴: 병합정렬, 퀵소트, 이진탐색, Karatsuba 곱셈, 클로스페어. 문제 시나리오, 완전한 예제, 흔한 실수, 성능 팁, 프로덕션 패턴.
들어가며: “O(n²)에서 벗어나고 싶어요”
분할정복의 핵심
분할정복(Divide and Conquer)은 문제를 작은 하위 문제로 나누고, 각각 해결한 뒤 결과를 합치는 패턴입니다. 비유하면 “1000명을 한 번에 정렬하는 것”이 아니라 “1000명을 500명씩 나눠 정렬하고, 두 그룹을 합치는 것”입니다.
flowchart TD
subgraph wrong["❌ 단순 반복 O(n²)"]
W1[전체 문제 한 번에] --> W2[버블/선택 정렬]
W2 --> W3[n=100만 → 수십 초]
W3 --> W4[시간 초과]
end
subgraph right["✅ 분할정복 O(n log n)"]
R1[Divide: 반으로 분할] --> R2[Conquer: 각각 해결]
R2 --> R3[Combine: 결과 병합]
R3 --> R4[100만 → 0.1초]
end
이 글에서는 실제로 겪는 문제 시나리오부터 시작해, 분할정복의 완전한 C++ 구현, 자주 하는 실수, 성능 최적화 팁, 프로덕션 패턴까지 단계별로 다룹니다.
이 글을 읽으면:
- 분할정복이 적합한 문제를 식별할 수 있습니다.
- 병합정렬, 퀵소트, 이진탐색, Karatsuba, 클로스페어를 직접 구현할 수 있습니다.
- 재귀 vs 반복, 메모리·캐시 최적화를 적용할 수 있습니다.
요구 환경: C++17 이상
실무 적용 경험: 이 글은 대규모 C++ 프로젝트에서 실제로 겪은 문제와 해결 과정을 바탕으로 작성되었습니다. 책이나 문서에서 다루지 않는 실전 함정과 디버깅 팁을 포함합니다.
목차
1. 문제 시나리오
시나리오 1: 대용량 배열 정렬
상황: 100만 건의 로그를 타임스탬프 기준으로 정렬해야 합니다. 버블 정렬은 O(n²)로 수십 초가 걸립니다.
잘못된 접근:
// ❌ O(n²) - 전체를 한 번에 처리
void bubbleSort(std::vector<int>& a) {
for (size_t i = 0; i < a.size(); ++i)
for (size_t j = 0; j < a.size() - 1 - i; ++j)
if (a[j] > a[j + 1]) std::swap(a[j], a[j + 1]);
}
// 100만 × 100만 → 시간 초과해결: 병합정렬 — 반으로 나누고 각각 정렬한 뒤 병합. O(n log n) 보장.
시나리오 2: 정렬된 배열에서 빠른 검색
상황: 100만 개의 ID가 정렬된 배열에서 특정 ID 존재 여부를 확인해야 합니다.
잘못된 접근:
// ❌ O(n) 순차 탐색
bool exists(const std::vector<int>& a, int target) {
for (int x : a) if (x == target) return true;
return false;
}해결: 이진 탐색 — 중간값과 비교해 범위를 절반씩 좁힘. O(log n).
시나리오 3: 큰 수 곱셈
상황: 1000자리 × 1000자리 정수 곱셈. 학교에서 배운 O(n²) 방식은 100만 번의 곱셈이 필요합니다.
잘못된 접근:
// ❌ O(n²) - 각 자릿수마다 곱셈
std::string multiplyNaive(const std::string& a, const std::string& b) {
// a의 각 자리 × b의 각 자리 → O(n²)
}해결: Karatsuba 알고리즘 — 분할정복으로 O(n^1.585)에 곱셈.
시나리오 4: 가장 가까운 두 점 찾기
상황: 2D 평면에 10만 개의 점이 있을 때, 가장 가까운 두 점의 거리를 구해야 합니다.
잘못된 접근:
// ❌ O(n²) - 모든 쌍 비교
double closestPairNaive(const std::vector<Point>& pts) {
double best = INF;
for (size_t i = 0; i < pts.size(); ++i)
for (size_t j = i + 1; j < pts.size(); ++j)
best = std::min(best, dist(pts[i], pts[j]));
return best;
}
// 10만 × 10만 → 시간 초과해결: 클로스페어(Closest Pair) — x축 기준 분할, 중앙 밴드만 O(n) 검사. O(n log n).
시나리오 5: 행렬 곱셈 최적화
상황: 1024×1024 행렬 곱셈. 단순 O(n³)은 10억 번 이상의 연산이 필요합니다.
해결: Strassen 알고리즘 — 2×2 블록으로 분할, 7번의 곱셈으로 8번 대체. O(n^2.807).
알고리즘 선택 가이드
| 문제 유형 | 분할정복 알고리즘 | 시간 복잡도 | 비고 |
|---|---|---|---|
| 정렬 | 병합정렬 | O(n log n) | 안정, 추가 공간 O(n) |
| 정렬 | 퀵소트 | O(n log n) 평균 | 제자리, 피벗 선택 중요 |
| 검색 | 이진 탐색 | O(log n) | 정렬된 배열 전제 |
| 큰 수 곱셈 | Karatsuba | O(n^1.585) | n=자릿수 |
| 행렬 곱셈 | Strassen | O(n^2.807) | 큰 n에서 유리 |
| 최근접 점쌍 | 클로스페어 | O(n log n) | x축 정렬 후 분할 |
2. 분할정복 기본 패턴
2.1 세 단계: Divide, Conquer, Combine
flowchart TD A[원본 문제] --> B[Divide: 작은 하위 문제로 분할] B --> C[Conquer: 각 하위 문제 해결 - 재귀 또는 기본 케이스] C --> D[Combine: 하위 결과를 합쳐 최종 답 생성] D --> E[최종 답]
2.2 템플릿 코드
// 분할정복 일반 패턴
template<typename T>
T divideConquer(const std::vector<T>& data, int lo, int hi) {
// 1. Base case: 더 이상 분할 불가
if (lo >= hi) {
return baseCase(data, lo);
}
// 2. Divide: 중간 지점으로 분할
int mid = lo + (hi - lo) / 2;
// 3. Conquer: 각 부분 해결
T leftResult = divideConquer(data, lo, mid);
T rightResult = divideConquer(data, mid + 1, hi);
// 4. Combine: 결과 병합
return combine(leftResult, rightResult);
}2.3 재귀 vs 반복 (꼬리 재귀 제거)
// 재귀 버전 - 직관적이지만 스택 오버플로우 위험
void mergesortRecursive(std::vector<int>& a, int lo, int hi);
// 반복 버전 - 스택 안전, 큰 n에서 안정
void mergesortIterative(std::vector<int>& a) {
int n = static_cast<int>(a.size());
std::vector<int> tmp(n);
for (int sz = 1; sz < n; sz *= 2) {
for (int lo = 0; lo < n - sz; lo += 2 * sz) {
int mid = lo + sz - 1;
int hi = std::min(lo + 2 * sz - 1, n - 1);
merge(a, lo, mid, hi, tmp);
}
}
}3. 완전한 분할정복 예제
3.1 병합정렬 (Merge Sort)
핵심: 반으로 나누고, 각각 정렬한 뒤 두 정렬된 배열을 병합합니다. 안정 정렬이며 최악에도 O(n log n)을 보장합니다.
flowchart TD A[5,2,8,1,9] --> B[5,2,8 | 1,9] B --> C[5,2 | 8 | 1 | 9] C --> D[2,5,8 | 1,9] D --> E[1,2,5,8,9]
#include <vector>
#include <algorithm>
// 병합: a[lo..mid]와 a[mid+1..hi]는 이미 정렬됨
void merge(std::vector<int>& a, int lo, int mid, int hi,
std::vector<int>& tmp) {
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi) {
if (a[i] <= a[j]) tmp[k++] = a[i++]; // <= 로 안정성 유지
else tmp[k++] = a[j++];
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
for (int idx = lo; idx <= hi; ++idx)
a[idx] = tmp[idx];
}
void mergesort(std::vector<int>& a, int lo, int hi, std::vector<int>& tmp) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
mergesort(a, lo, mid, tmp);
mergesort(a, mid + 1, hi, tmp);
merge(a, lo, mid, hi, tmp);
}
void mergesort(std::vector<int>& a) {
if (a.empty()) return;
std::vector<int> tmp(a.size());
mergesort(a, 0, static_cast<int>(a.size()) - 1, tmp);
}3.2 퀵소트 (Quick Sort)
핵심: 피벗을 선택해 분할하고, 왼쪽은 피벗보다 작게, 오른쪽은 크게 배치한 뒤 재귀적으로 정렬합니다. 제자리 정렬이며 평균 O(n log n).
#include <vector>
#include <algorithm>
// Hoare 분할: 중간값 피벗으로 최악 케이스 완화
int partitionHoare(std::vector<int>& a, int lo, int hi) {
int pivot = a[lo + (hi - lo) / 2];
int i = lo - 1, j = hi + 1;
while (true) {
do ++i; while (a[i] < pivot);
do --j; while (a[j] > pivot);
if (i >= j) return j;
std::swap(a[i], a[j]);
}
}
void quicksort(std::vector<int>& a, int lo, int hi) {
if (lo >= hi) return;
int p = partitionHoare(a, lo, hi);
quicksort(a, lo, p);
quicksort(a, p + 1, hi);
}
void quicksort(std::vector<int>& a) {
if (a.size() <= 1) return;
quicksort(a, 0, static_cast<int>(a.size()) - 1);
}3.3 이진 탐색 (Binary Search)
핵심: 정렬된 배열에서 중간값과 비교해 범위를 절반씩 좁혀갑니다.
#include <vector>
// 반복 버전 - 스택 안전
int binarySearch(const std::vector<int>& a, int target) {
int lo = 0, hi = static_cast<int>(a.size()) - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // 오버플로우 방지
if (a[mid] == target) return mid;
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// 재귀 버전
int binarySearchRecursive(const std::vector<int>& a, int target, int lo, int hi) {
if (lo > hi) return -1;
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return mid;
if (a[mid] < target) return binarySearchRecursive(a, target, mid + 1, hi);
return binarySearchRecursive(a, target, lo, mid - 1);
}3.4 Karatsuba 곱셈 (큰 수 곱셈)
핵심: x = a×10^(n/2) + b, y = c×10^(n/2) + d 로 분할하면, xy = ac×10^n + (ad+bc)×10^(n/2) + bd. (ad+bc) = (a+b)(c+d) - ac - bd 로 3번의 곱셈만으로 계산 가능.
#include <string>
#include <algorithm>
// 자릿수 맞춤 (2의 거듭제곱으로)
std::string padZeros(const std::string& s, size_t len) {
if (s.size() >= len) return s;
return std::string(len - s.size(), '0') + s;
}
// 큰 수 덧셈
std::string addBigInt(std::string a, std::string b) {
if (a.size() < b.size()) std::swap(a, b);
b = std::string(a.size() - b.size(), '0') + b;
std::string result;
int carry = 0;
for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {
int sum = (a[i] - '0') + (b[i] - '0') + carry;
result.push_back('0' + sum % 10);
carry = sum / 10;
}
if (carry) result.push_back('0' + carry);
std::reverse(result.begin(), result.end());
return result;
}
// 큰 수 뺄셈 (a >= b 가정)
std::string subBigInt(std::string a, std::string b) {
b = std::string(a.size() - b.size(), '0') + b;
std::string result;
int borrow = 0;
for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {
int diff = (a[i] - '0') - (b[i] - '0') - borrow;
if (diff < 0) { diff += 10; borrow = 1; } else borrow = 0;
result.push_back('0' + diff);
}
std::reverse(result.begin(), result.end());
size_t start = result.find_first_not_of('0');
return start == std::string::npos ? "0" : result.substr(start);
}
// Karatsuba: x * y (x, y는 숫자 문자열)
// xy = ac·10^(2m) + (ad+bc)·10^m + bd, (ad+bc) = (a+b)(c+d) - ac - bd
std::string karatsuba(const std::string& x, const std::string& y) {
size_t n = std::max(x.size(), y.size());
if (n <= 1) {
int v = (x.empty() ? 0 : x[0] - '0') * (y.empty() ? 0 : y[0] - '0');
return std::to_string(v);
}
n = (n + 1) / 2;
std::string xp = padZeros(x, 2 * n), yp = padZeros(y, 2 * n);
std::string a = xp.substr(0, n), b = xp.substr(n);
std::string c = yp.substr(0, n), d = yp.substr(n);
std::string ac = karatsuba(a, c);
std::string bd = karatsuba(b, d);
std::string abcd = karatsuba(addBigInt(a, b), addBigInt(c, d));
std::string adbc = subBigInt(subBigInt(abcd, ac), bd);
return addBigInt(addBigInt(ac + std::string(2 * n, '0'),
adbc + std::string(n, '0')), bd);
}실용적 구현: 위는 개념 설명용. 실제로는 std::string 대신 std::vector<int> 또는 GMP 라이브러리를 사용하는 것이 좋습니다.
3.5 클로스페어 (Closest Pair of Points)
핵심: x좌표 기준 정렬 후, 중간으로 분할. 왼쪽 최소거리 dL, 오른쪽 dR. 중앙 밴드(폭 2×min(dL,dR)) 내 점들만 O(n) 검사.
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits>
struct Point {
double x, y;
};
double dist(const Point& a, const Point& b) {
return std::hypot(a.x - b.x, a.y - b.y);
}
// 밴드 내 점들만 검사 - y좌표 정렬된 상태
double closestInBand(std::vector<Point>& band, double d) {
double best = d;
for (size_t i = 0; i < band.size(); ++i) {
for (size_t j = i + 1; j < band.size() && (band[j].y - band[i].y) < best; ++j) {
best = std::min(best, dist(band[i], band[j]));
}
}
return best;
}
double closestPairRec(std::vector<Point>& pts, std::vector<Point>& byY,
int lo, int hi) {
if (hi - lo <= 2) {
double best = std::numeric_limits<double>::max();
for (int i = lo; i <= hi; ++i)
for (int j = i + 1; j <= hi; ++j)
best = std::min(best, dist(pts[i], pts[j]));
return best;
}
int mid = lo + (hi - lo) / 2;
double midX = pts[mid].x;
double dL = closestPairRec(pts, byY, lo, mid);
double dR = closestPairRec(pts, byY, mid + 1, hi);
double d = std::min(dL, dR);
// 밴드: |x - midX| < d 인 점들
std::vector<Point> band;
for (const auto& p : byY) {
if (std::abs(p.x - midX) < d) band.push_back(p);
}
return std::min(d, closestInBand(band, d));
}
double closestPair(std::vector<Point> pts) {
if (pts.size() < 2) return std::numeric_limits<double>::max();
std::sort(pts.begin(), pts.end(), {
return a.x < b.x;
});
std::vector<Point> byY = pts;
std::sort(byY.begin(), byY.end(), {
return a.y < b.y;
});
return closestPairRec(pts, byY, 0, static_cast<int>(pts.size()) - 1);
}3.7 최대 부분 배열 합 (Maximum Subarray - Kadane vs 분할정복)
분할정복 접근: 중간을 기준으로 왼쪽 최대, 오른쪽 최대, 중간을 지나는 최대를 각각 구하고 합칩니다.
#include <vector>
#include <algorithm>
// 중간을 지나는 최대 부분합
int maxCrossingSum(const std::vector<int>& a, int lo, int mid, int hi) {
int leftSum = 0, leftMax = 0;
for (int i = mid; i >= lo; --i) {
leftSum += a[i];
leftMax = std::max(leftMax, leftSum);
}
int rightSum = 0, rightMax = 0;
for (int i = mid + 1; i <= hi; ++i) {
rightSum += a[i];
rightMax = std::max(rightMax, rightSum);
}
return leftMax + rightMax;
}
int maxSubarrayDC(const std::vector<int>& a, int lo, int hi) {
if (lo == hi) return a[lo];
int mid = lo + (hi - lo) / 2;
int leftMax = maxSubarrayDC(a, lo, mid);
int rightMax = maxSubarrayDC(a, mid + 1, hi);
int crossMax = maxCrossingSum(a, lo, mid, hi);
return std::max({leftMax, rightMax, crossMax});
}
int maxSubarray(const std::vector<int>& a) {
if (a.empty()) return 0;
return maxSubarrayDC(a, 0, static_cast<int>(a.size()) - 1);
}4. 자주 발생하는 에러와 해결법
문제 1: 재귀 스택 오버플로우
증상: 큰 입력에서 Segmentation fault 또는 스택 오버플로우.
원인: 재귀 깊이가 너무 깊어집니다. 예: n=100만일 때 병합정렬은 log2(100만) ≈ 20단계이므로 보통 괜찮지만, 퀵소트는 최악에 n단계까지 갈 수 있습니다.
// ❌ 퀵소트 최악 - 이미 정렬된 데이터 + 첫 원소 피벗
int partitionBad(std::vector<int>& a, int lo, int hi) {
int pivot = a[lo]; // 최악: 한쪽으로만 분할
// ...
}
// ✅ 해결 1: 중간값 또는 랜덤 피벗
int pivot = a[lo + (hi - lo) / 2];
// ✅ 해결 2: 재귀 깊이 제한 후 힙정렬로 전환 (IntroSort)문제 2: 이진 탐색 무한 루프
증상: 프로그램이 종료되지 않습니다.
원인: mid 계산 오버플로우 또는 경계 업데이트 오류.
// ❌ 오버플로우 (lo + hi가 int 범위 초과)
int mid = (lo + hi) / 2;
// ✅ 올바른 계산
int mid = lo + (hi - lo) / 2;
// ❌ 무한 루프 (lo=3, hi=4, mid=3, lo=3 유지)
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (condition) lo = mid; // hi로 수렴 안 함
else hi = mid - 1;
}
// ✅ lo 또는 hi를 mid±1로 업데이트해 반드시 범위 축소문제 3: 병합 시 임시 배열 인덱스 오류
증상: 정렬 결과가 잘못되거나 크래시.
원인: tmp와 a의 인덱스 매핑을 잘못 사용.
// ❌ tmp를 0부터 채움 - lo가 0이 아닐 때 잘못됨
void mergeBad(std::vector<int>& a, int lo, int mid, int hi, std::vector<int>& tmp) {
int k = 0; // 잘못됨
// ...
for (int idx = lo; idx <= hi; ++idx)
a[idx] = tmp[idx]; // tmp[idx]는 비어있을 수 있음
}
// ✅ tmp도 [lo..hi] 구간 사용
void merge(std::vector<int>& a, int lo, int mid, int hi, std::vector<int>& tmp) {
int i = lo, j = mid + 1, k = lo;
// ...
for (int idx = lo; idx <= hi; ++idx)
a[idx] = tmp[idx];
}문제 4: 분할정복 vs 동적 계획법 혼동
증상: “같은 하위 문제를 여러 번 푸는” 경우에 분할정복을 쓰면 지수 시간이 됩니다.
원인: 분할정복은 하위 문제가 겹치지 않을 때 적합. 겹치면 DP 또는 메모이제이션.
// 피보나치: fib(n) = fib(n-1) + fib(n-2)
// ❌ 순수 분할정복 - O(2^n), 같은 fib(k)를 여러 번 계산
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
// ✅ DP 또는 메모이제이션 - O(n)문제 5: Combine 단계 누락
증상: 분할하고 각각 풀었는데 최종 답이 틀립니다.
원인: Conquer 결과를 Combine하는 로직을 빠뜨림.
// ❌ Combine 없음 - 왼쪽 결과만 반환
int wrongDC(std::vector<int>& a, int lo, int hi) {
if (lo >= hi) return a[lo];
int mid = lo + (hi - lo) / 2;
int left = wrongDC(a, lo, mid);
int right = wrongDC(a, mid + 1, hi);
return left; // right 무시!
}
// ✅ Combine: left와 right를 적절히 합침
return combine(left, right);문제 6: Base case 처리 오류
증상: 빈 배열 또는 단일 원소에서 크래시 또는 잘못된 결과.
원인: lo > hi 또는 lo == hi 처리를 빠뜨림.
// ❌ hi - lo == 1일 때 mid = lo, [lo, lo]와 [lo+1, hi]로 분할
// [lo+1, hi]가 빈 구간이 될 수 있음
void quicksortBad(std::vector<int>& a, int lo, int hi) {
int mid = (lo + hi) / 2;
// lo >= hi 체크 없음
}
// ✅ Base case 명시
void quicksort(std::vector<int>& a, int lo, int hi) {
if (lo >= hi) return;
// ...
}5. 성능 최적화 팁
1. 작은 구간은 삽입 정렬
분할이 너무 작아지면 재귀 오버헤드가 커집니다. 일정 크기 이하는 삽입 정렬로 전환합니다.
const int INSERTION_THRESHOLD = 16;
void mergesort(std::vector<int>& a, int lo, int hi, std::vector<int>& tmp) {
if (hi - lo < INSERTION_THRESHOLD) {
insertionSort(a, lo, hi);
return;
}
// ...
}2. 임시 배열 재사용
병합정렬에서 tmp 벡터를 매번 할당하지 말고, 최상위에서 한 번만 할당해 재귀 전체에서 재사용합니다.
// ❌ 매번 할당
void merge(std::vector<int>& a, int lo, int mid, int hi) {
std::vector<int> tmp(hi - lo + 1); // 비효율
// ...
}
// ✅ 한 번만 할당
void mergesort(std::vector<int>& a) {
std::vector<int> tmp(a.size());
mergesortImpl(a, 0, a.size() - 1, tmp);
}3. 퀵소트 피벗 선택
- 첫/끝 원소: 이미 정렬된 데이터에서 O(n²)
- 중간값: 실전에서 안정적
- 랜덤: 최악 확률 감소
- 3점 중앙값: median-of-three로 더 안정적
// 3점 중앙값
int medianOfThree(std::vector<int>& a, int lo, int hi) {
int mid = lo + (hi - lo) / 2;
if (a[lo] > a[mid]) std::swap(a[lo], a[mid]);
if (a[lo] > a[hi]) std::swap(a[lo], a[hi]);
if (a[mid] > a[hi]) std::swap(a[mid], a[hi]);
return mid; // a[mid]가 중앙값
}4. 반복 버전으로 스택 절약
재귀 대신 반복(스택 또는 큐로 구간 관리)을 사용하면 스택 오버플로우를 피할 수 있습니다.
void quicksortIterative(std::vector<int>& a) {
std::stack<std::pair<int,int>> st;
st.push({0, static_cast<int>(a.size()) - 1});
while (!st.empty()) {
auto [lo, hi] = st.top();
st.pop();
if (lo >= hi) continue;
int p = partitionHoare(a, lo, hi);
st.push({lo, p});
st.push({p + 1, hi});
}
}5. 벤치마크 참고 (100만 int, 릴리스)
| 알고리즘 | 시간 (대략) | 비고 |
|---|---|---|
| 병합정렬 | ~100ms | 안정, O(n) 추가 공간 |
| 퀵소트 (중간 피벗) | ~90ms | 제자리 |
| 이진 탐색 100만 번 | ~20ms | O(log n) per query |
| std::sort | ~80ms | IntroSort |
6. 프로덕션 패턴
1. 분할정복 유틸리티 템플릿
#include <functional>
#include <vector>
template<typename T, typename Combine>
T divideConquerTemplate(
const std::vector<T>& data,
int lo, int hi,
std::function<T(const std::vector<T>&, int)> baseCase,
Combine&& combine)
{
if (lo >= hi) return baseCase(data, lo);
int mid = lo + (hi - lo) / 2;
T left = divideConquerTemplate(data, lo, mid, baseCase, combine);
T right = divideConquerTemplate(data, mid + 1, hi, baseCase, combine);
return combine(left, right);
}2. 병렬 분할정복 (std::async)
#include <future>
#include <algorithm>
void mergesortParallel(std::vector<int>& a, int lo, int hi, std::vector<int>& tmp) {
if (hi - lo < 10000) {
mergesort(a, lo, hi, tmp);
return;
}
int mid = lo + (hi - lo) / 2;
auto leftFuture = std::async(std::launch::async, [&]() {
mergesortParallel(a, lo, mid, tmp);
});
mergesortParallel(a, mid + 1, hi, tmp);
leftFuture.get();
merge(a, lo, mid, hi, tmp);
}3. 에러 처리 및 검증
#include <optional>
#include <cassert>
std::optional<int> safeBinarySearch(const std::vector<int>& a, int target) {
if (a.empty()) return std::nullopt;
if (!std::is_sorted(a.begin(), a.end())) {
// 정렬되지 않았으면 이진 탐색 결과 신뢰 불가
return std::nullopt;
}
auto it = std::lower_bound(a.begin(), a.end(), target);
if (it == a.end() || *it != target) return std::nullopt;
return static_cast<int>(std::distance(a.begin(), it));
}4. 로깅 및 디버깅
#ifdef DEBUG_DC
#define LOG_DC(msg) std::cerr << "[DC] " << msg << "\n"
#else
#define LOG_DC(msg) ((void)0)
#endif
void mergesortWithLog(std::vector<int>& a, int lo, int hi, std::vector<int>& tmp) {
LOG_DC("mergesort [" << lo << ", " << hi << "]");
if (lo >= hi) return;
// ...
}5. 단위 테스트용 헬퍼
#include <vector>
#include <random>
std::vector<int> randomVector(size_t n, int minVal = 0, int maxVal = 1000) {
std::mt19937 gen(std::random_device{}());
std::uniform_int_distribution<> dist(minVal, maxVal);
std::vector<int> v(n);
for (auto& x : v) x = dist(gen);
return v;
}
bool isSorted(const std::vector<int>& a) {
for (size_t i = 1; i < a.size(); ++i)
if (a[i] < a[i-1]) return false;
return true;
}7. 구현 체크리스트
분할정복 설계 전
- 문제가 독립적인 하위 문제로 나뉘는지 확인
- 하위 문제가 겹치지 않으면 분할정복, 겹치면 DP 검토
- Base case가 명확한지 확인
구현 시
- Divide: 균등 분할 (보통 mid = lo + (hi - lo) / 2)
- Conquer: 재귀 또는 기본 케이스
- Combine: 하위 결과 병합 로직 필수
-
lo >= hi등 Base case 처리
퀵소트
- 피벗 선택 (중간값 또는 랜덤)
- 재귀 깊이 제한 또는 IntroSort
- 작은 구간은 삽입 정렬
이진 탐색
-
mid = lo + (hi - lo) / 2(오버플로우 방지) - 종료 조건 및 경계 업데이트 (무한 루프 방지)
프로덕션
- 빈 배열·단일 원소 검증
- 스택 오버플로우 대비 (반복 버전 또는 깊이 제한)
- 필요 시 병렬화
정리
| 항목 | 설명 |
|---|---|
| Divide | 문제를 작은 하위 문제로 분할 |
| Conquer | 각 하위 문제 해결 (재귀 또는 기본) |
| Combine | 하위 결과를 합쳐 최종 답 생성 |
| 병합정렬 | O(n log n), 안정, O(n) 추가 공간 |
| 퀵소트 | O(n log n) 평균, 제자리, 피벗 중요 |
| 이진 탐색 | O(log n), 정렬된 배열 전제 |
| Karatsuba | O(n^1.585) 큰 수 곱셈 |
| 클로스페어 | O(n log n) 최근접 점쌍 |
핵심 원칙:
- Divide-Conquer-Combine 세 단계 명확히 구분
- Base case와 Combine 누락 주의
- 재귀 깊이·스택 오버플로우 고려
- 하위 문제 겹침 시 DP로 전환 검토
자주 묻는 질문 (FAQ)
Q. 이 내용을 실무에서 언제 쓰나요?
A. 대용량 정렬, 빠른 검색, 행렬 연산, 기하 알고리즘(최근접 점쌍, 볼록 껍질), 병렬 처리 설계(맵리듀스), FFT 등에 활용합니다.
Q. 선행으로 읽으면 좋은 글은?
A. 재귀 기초, 정렬·검색, 동적 계획법을 먼저 익히면 분할정복과의 차이를 이해하기 쉽습니다.
Q. 더 깊이 공부하려면?
A. 《알고리즘 설계》 분할정복 챕터, LeetCode Divide and Conquer 유형, cppreference를 참고하세요.
한 줄 요약: Divide-Conquer-Combine 패턴으로 병합정렬·퀵소트·이진탐색·Karatsuba·클로스페어를 구현하고, 흔한 실수를 피해 실무에 적용할 수 있습니다.
부록: 분할정복 복잡도 요약
| 알고리즘 | 시간 | 공간 | 비고 |
|---|---|---|---|
| 병합정렬 | O(n log n) | O(n) | 안정 |
| 퀵소트 | O(n log n) 평균, O(n²) 최악 | O(log n) | 제자리 |
| 이진 탐색 | O(log n) | O(1) | 정렬 전제 |
| Karatsuba | O(n^1.585) | O(n) | n=자릿수 |
| Strassen | O(n^2.807) | O(n²) | 행렬 |
| 클로스페어 | O(n log n) | O(n) | 2D 점 |
참고 자료
- cppreference: std::sort
- cppreference: std::lower_bound
- LeetCode: Divide and Conquer
- 《Introduction to Algorithms》 (CLRS) - 분할정복 챕터
관련 글
- C++ 분할정복 완벽 가이드 | 병합정렬·퀵소트·이진탐색·클로스페어·Strassen [실전]
- C++ 동적 계획법 완벽 가이드 | 메모이제이션·타뷸레이션·최적화 [#54-4]
- C++ 알고리즘 |