C++ 분할정복 완벽 가이드 | 병합정렬·퀵소트·이진탐색·클로스페어·Strassen [실전]

Q: 이 내용을 실무에서 언제 쓰나요?

대용량 정렬, 빠른 검색, 행렬 연산, 기하 알고리즘, 병렬 처리 설계 등에 활용합니다.

Q: 선행으로 읽으면 좋은 글은?

재귀 기초, 정렬·검색 알고리즘, 동적 계획법을 먼저 익히면 분할정복과의 차이를 이해하기 쉽습니다.

2026년 4월 7일 · 40분 읽기 · 수정 2026년 4월 7일 고급 실습

이 글의 핵심

C++ 분할정복(Divide and Conquer) 패턴: 병합정렬, 퀵소트, 이진탐색, 클로스페어, Strassen 행렬 곱셈. 문제 시나리오, 완전한 예제, 흔한 실수, 베스트 프랙티스, 프로덕션 패턴.

들어가며: “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

이 글에서는 실제로 겪는 문제 시나리오부터 시작해, 병합정렬·퀵소트·이진탐색·클로스페어·Strassen 행렬 곱셈의 완전한 C++ 구현, 자주 하는 실수, 베스트 프랙티스, 프로덕션 패턴까지 단계별로 다룹니다.

이 글을 읽으면:

분할정복이 적합한 문제를 식별할 수 있습니다.
병합정렬, 퀵소트, 이진탐색, 클로스페어, Strassen을 직접 구현할 수 있습니다.
재귀 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: 가장 가까운 두 점 찾기

상황: 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).

시나리오 4: 행렬 곱셈 최적화

상황: 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)	정렬된 배열 전제
행렬 곱셈	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 클로스페어 (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.5 Strassen 행렬 곱셈 (Matrix Multiplication)

핵심: 2×2 행렬 곱셈은 8번의 곱셈이 필요하지만, Strassen은 7번의 곱셈으로 동일한 결과를 얻습니다. 4×4 이상 행렬을 2×2 블록으로 분할해 재귀 적용.

수식: A, B를 4개의 부분행렬로 나누면:

P1 = (A11 - A22)(B11 + B22)
P2 = (A11 + A22)(B11 + B22)
P3 = (A11 - A21)(B11 + B12)
P4 = (A11 + A12)B22
P5 = A11(B12 - B22)
P6 = A22(B21 - B11)
P7 = (A21 + A22)B11

결과: C11 = P1+P2-P4+P6, C12 = P4+P5, C21 = P6+P7, C22 = P2-P3+P5-P7

#include <vector>
#include <algorithm>
#include <stdexcept>

using Matrix = std::vector<std::vector<double>>;

// 행렬 덧셈
Matrix matrixAdd(const Matrix& a, const Matrix& b) {
    size_t n = a.size();
    Matrix c(n, std::vector<double>(n));
    for (size_t i = 0; i < n; ++i)
        for (size_t j = 0; j < n; ++j)
            c[i][j] = a[i][j] + b[i][j];
    return c;
}

// 행렬 뺄셈
Matrix matrixSub(const Matrix& a, const Matrix& b) {
    size_t n = a.size();
    Matrix c(n, std::vector<double>(n));
    for (size_t i = 0; i < n; ++i)
        for (size_t j = 0; j < n; ++j)
            c[i][j] = a[i][j] - b[i][j];
    return c;
}

// 일반 O(n³) 행렬 곱셈 (기본 케이스)
Matrix matrixMulNaive(const Matrix& a, const Matrix& b) {
    size_t n = a.size();
    Matrix c(n, std::vector<double>(n, 0));
    for (size_t i = 0; i < n; ++i)
        for (size_t j = 0; j < n; ++j)
            for (size_t k = 0; k < n; ++k)
                c[i][j] += a[i][k] * b[k][j];
    return c;
}

// 부분행렬 추출: A에서 [r1:r2)[c1:c2) 구간
Matrix submatrix(const Matrix& a, size_t r1, size_t r2, size_t c1, size_t c2) {
    Matrix sub(r2 - r1, std::vector<double>(c2 - c1));
    for (size_t i = r1; i < r2; ++i)
        for (size_t j = c1; j < c2; ++j)
            sub[i - r1][j - c1] = a[i][j];
    return sub;
}

// 4개 부분행렬을 하나로 합침
Matrix combineQuarters(const Matrix& c11, const Matrix& c12,
                       const Matrix& c21, const Matrix& c22) {
    size_t n = c11.size() * 2;
    Matrix c(n, std::vector<double>(n));
    size_t m = n / 2;
    for (size_t i = 0; i < m; ++i) {
        for (size_t j = 0; j < m; ++j) {
            c[i][j] = c11[i][j];
            c[i][j + m] = c12[i][j];
            c[i + m][j] = c21[i][j];
            c[i + m][j + m] = c22[i][j];
        }
    }
    return c;
}

// Strassen: 7번의 곱셈으로 n×n 행렬 곱셈 (n은 2의 거듭제곱)
Matrix strassen(const Matrix& a, const Matrix& b) {
    size_t n = a.size();
    if (n != b.size() || (n & (n - 1)) != 0)
        throw std::invalid_argument("Strassen: 정방행렬, 2의 거듭제곱 크기 필요");

    if (n <= 64)  // 작은 행렬은 일반 곱셈이 더 빠름
        return matrixMulNaive(a, b);

    size_t m = n / 2;
    Matrix a11 = submatrix(a, 0, m, 0, m);
    Matrix a12 = submatrix(a, 0, m, m, n);
    Matrix a21 = submatrix(a, m, n, 0, m);
    Matrix a22 = submatrix(a, m, n, m, n);
    Matrix b11 = submatrix(b, 0, m, 0, m);
    Matrix b12 = submatrix(b, 0, m, m, n);
    Matrix b21 = submatrix(b, m, n, 0, m);
    Matrix b22 = submatrix(b, m, n, m, n);

    Matrix p1 = strassen(matrixSub(a11, a22), matrixAdd(b11, b22));
    Matrix p2 = strassen(matrixAdd(a11, a22), matrixAdd(b11, b22));
    Matrix p3 = strassen(matrixSub(a11, a21), matrixAdd(b11, b12));
    Matrix p4 = strassen(matrixAdd(a11, a12), b22);
    Matrix p5 = strassen(a11, matrixSub(b12, b22));
    Matrix p6 = strassen(a22, matrixSub(b21, b11));
    Matrix p7 = strassen(matrixAdd(a21, a22), b11);

    Matrix c11 = matrixAdd(matrixSub(matrixAdd(p1, p2), p4), p6);
    Matrix c12 = matrixAdd(p4, p5);
    Matrix c21 = matrixAdd(p6, p7);
    Matrix c22 = matrixSub(matrixAdd(matrixSub(p2, p3), p5), p7);

    return combineQuarters(c11, c12, c21, c22);
}

// 비2의 거듭제곱 행렬용: 패딩 후 Strassen 적용
Matrix strassenPadded(Matrix a, Matrix b) {
    size_t n = std::max({a.size(), a[0].size(), b.size(), b[0].size()});
    size_t N = 1;
    while (N < n) N *= 2;

    Matrix A(N, std::vector<double>(N, 0));
    Matrix B(N, std::vector<double>(N, 0));
    for (size_t i = 0; i < a.size(); ++i)
        for (size_t j = 0; j < a[0].size(); ++j)
            A[i][j] = a[i][j];
    for (size_t i = 0; i < b.size(); ++i)
        for (size_t j = 0; j < b[0].size(); ++j)
            B[i][j] = b[i][j];

    Matrix C = strassen(A, B);
    Matrix result(a.size(), std::vector<double>(b[0].size()));
    for (size_t i = 0; i < result.size(); ++i)
        for (size_t j = 0; j < result[0].size(); ++j)
            result[i][j] = C[i][j];
    return result;
}

실무 참고: Strassen은 n이 수백~수천 이상일 때 유리합니다. 작은 n에서는 일반 O(n³) 곱셈이 캐시 효율로 더 빠를 수 있어, 위 예제처럼 n≤64에서 전환합니다.

3.6 최대 부분 배열 합 (Maximum Subarray - 분할정복)

분할정복 접근: 중간을 기준으로 왼쪽 최대, 오른쪽 최대, 중간을 지나는 최대를 각각 구하고 합칩니다.

#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: Strassen 행렬 크기 제약

증상: n이 2의 거듭제곱이 아닐 때 크래시 또는 잘못된 결과.

원인: Strassen은 2×2 블록 분할을 전제로 합니다.

// ❌ 3×3 행렬 직접 Strassen 호출 - 잘못된 분할
Matrix C = strassen(A, B);  // n=3

// ✅ 패딩으로 2의 거듭제곱으로 맞춤
Matrix C = strassenPadded(A, B);  // 3×3 → 4×4로 패딩

5. 베스트 프랙티스

1. Base case 명확히 정의

// ✅ 항상 lo >= hi 또는 유사 조건 먼저 검사
void quicksort(std::vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    // ...
}

2. mid 계산 시 오버플로우 방지

// ✅ lo + (hi - lo) / 2
int mid = lo + (hi - lo) / 2;

3. 하위 문제 독립성 확인

분할정복: 하위 문제가 겹치지 않음 (병합정렬, 퀵소트)
DP: 하위 문제가 겹침 (피보나치, LCS)

4. Combine 로직 검증

Divide·Conquer 결과를 반드시 합치는 단계가 있는지 확인

5. 작은 구간 최적화

const int INSERTION_THRESHOLD = 16;
if (hi - lo < INSERTION_THRESHOLD) {
    insertionSort(a, lo, hi);
    return;
}

6. 성능 최적화 팁

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. 임시 배열 재사용

// ✅ 한 번만 할당
void mergesort(std::vector<int>& a) {
    std::vector<int> tmp(a.size());
    mergesortImpl(a, 0, a.size() - 1, tmp);
}

3. 퀵소트 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;
}

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
Strassen 1024×1024	Naive 대비 ~1.5배 빠름	n 클수록 차이 증가

7. 프로덕션 패턴

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;
}

8. 구현 체크리스트

분할정복 설계 전

문제가 독립적인 하위 문제로 나뉘는지 확인
하위 문제가 겹치지 않으면 분할정복, 겹치면 DP 검토
Base case가 명확한지 확인

구현 시

Divide: 균등 분할 (보통 mid = lo + (hi - lo) / 2)
Conquer: 재귀 또는 기본 케이스
Combine: 하위 결과 병합 로직 필수
lo >= hi 등 Base case 처리

퀵소트

피벗 선택 (중간값 또는 랜덤)
재귀 깊이 제한 또는 IntroSort
작은 구간은 삽입 정렬

이진 탐색

mid = lo + (hi - lo) / 2 (오버플로우 방지)
종료 조건 및 경계 업데이트 (무한 루프 방지)

Strassen

행렬 크기가 2의 거듭제곱인지 확인 (또는 패딩)
작은 n에서 일반 곱셈으로 전환 (예: n≤64)

프로덕션

빈 배열·단일 원소 검증
스택 오버플로우 대비 (반복 버전 또는 깊이 제한)
필요 시 병렬화

정리

항목	설명
Divide	문제를 작은 하위 문제로 분할
Conquer	각 하위 문제 해결 (재귀 또는 기본)
Combine	하위 결과를 합쳐 최종 답 생성
병합정렬	O(n log n), 안정, O(n) 추가 공간
퀵소트	O(n log n) 평균, 제자리, 피벗 중요
이진 탐색	O(log n), 정렬된 배열 전제
클로스페어	O(n log n) 최근접 점쌍
Strassen	O(n^2.807) 행렬 곱셈

핵심 원칙:

Divide-Conquer-Combine 세 단계 명확히 구분
Base case와 Combine 누락 주의
재귀 깊이·스택 오버플로우 고려
하위 문제 겹침 시 DP로 전환 검토

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. 대용량 정렬, 빠른 검색, 행렬 연산, 기하 알고리즘(최근접 점쌍, 볼록 껍질), 병렬 처리 설계(맵리듀스), FFT 등에 활용합니다.

Q. 선행으로 읽으면 좋은 글은?

A. 재귀 기초, 정렬·검색, 동적 계획법을 먼저 익히면 분할정복과의 차이를 이해하기 쉽습니다.

Q. 더 깊이 공부하려면?

A. 《알고리즘 설계》 분할정복 챕터, LeetCode Divide and Conquer 유형, cppreference를 참고하세요.

한 줄 요약: Divide-Conquer-Combine 패턴으로 병합정렬·퀵소트·이진탐색·클로스페어·Strassen을 구현하고, 흔한 실수를 피해 실무에 적용할 수 있습니다.

부록: 분할정복 복잡도 요약

알고리즘	시간	공간	비고
병합정렬	O(n log n)	O(n)	안정
퀵소트	O(n log n) 평균, O(n²) 최악	O(log n)	제자리
이진 탐색	O(log n)	O(1)	정렬 전제
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++ 동적 계획법 완벽 가이드 | 메모이제이션·타뷸레이션·최적화 [#54-4]
C++ 탐욕 알고리즘 완벽 가이드 | 활동 선택·분수 배낭·허프만 코딩·구간 스케줄링 [실전]
C++ 알고리즘 최적화 | 시간복잡도·공간복잡도·트레이드오프 [#54-10]
C++ 알고리즘 |

이 글의 핵심

들어가며: “O(n²)에서 벗어나고 싶어요”

실제 겪는 문제 시나리오

목차

1. 문제 시나리오

시나리오 1: 대용량 배열 정렬

시나리오 2: 정렬된 배열에서 빠른 검색

시나리오 3: 가장 가까운 두 점 찾기

시나리오 4: 행렬 곱셈 최적화

알고리즘 선택 가이드

2. 분할정복 기본 패턴

2.1 세 단계: Divide, Conquer, Combine

2.2 템플릿 코드

2.3 재귀 vs 반복 (꼬리 재귀 제거)

3. 완전한 분할정복 예제

3.1 병합정렬 (Merge Sort)

3.2 퀵소트 (Quick Sort)

3.3 이진 탐색 (Binary Search)

3.4 클로스페어 (Closest Pair of Points)

3.5 Strassen 행렬 곱셈 (Matrix Multiplication)

3.6 최대 부분 배열 합 (Maximum Subarray - 분할정복)

4. 자주 발생하는 에러와 해결법

문제 1: 재귀 스택 오버플로우

문제 2: 이진 탐색 무한 루프

문제 3: 병합 시 임시 배열 인덱스 오류

문제 4: 분할정복 vs 동적 계획법 혼동

문제 5: Combine 단계 누락

문제 6: Strassen 행렬 크기 제약

5. 베스트 프랙티스

1. Base case 명확히 정의

2. mid 계산 시 오버플로우 방지

3. 하위 문제 독립성 확인

4. Combine 로직 검증

5. 작은 구간 최적화

6. 성능 최적화 팁

1. 작은 구간은 삽입 정렬

2. 임시 배열 재사용

3. 퀵소트 3점 중앙값 피벗

4. 반복 버전으로 스택 절약

5. 벤치마크 참고 (100만 int, 릴리스)

7. 프로덕션 패턴

1. 분할정복 유틸리티 템플릿

2. 병렬 분할정복 (std::async)

3. 에러 처리 및 검증

4. 로깅 및 디버깅

5. 단위 테스트용 헬퍼

8. 구현 체크리스트

분할정복 설계 전

구현 시

퀵소트

이진 탐색

Strassen

프로덕션

정리

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

Q. 선행으로 읽으면 좋은 글은?

Q. 더 깊이 공부하려면?

부록: 분할정복 복잡도 요약

참고 자료

관련 글