C++ 분할정복: 병합 정렬, 퀵소트, 이진 탐색, 가장 가까운 점 쌍, 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++ 구현, 자주 하는 실수, 실무에서 쓸 때의 판단 기준까지 차례로 다룹니다.

분할정복이 빨라지는 이유는 “나눴기 때문”이 아니라 합치는 비용이 싸기 때문입니다. 병합정렬에서 크기 n인 문제를 n/2 두 개로 나누면 각 층의 병합 비용은 전부 합쳐 O(n)이고, 층의 수가 log n이므로 전체가 O(n log n)이 됩니다. 이것을 식으로 쓰면 T(n) = 2T(n/2) + O(n)이고, 마스터 정리로 바로 풀립니다. 반대로 합치는 단계가 O(n²)이라면 나눠 봐야 전체도 O(n²)에 머뭅니다. 그래서 새로운 문제에 분할정복을 적용할 때 가장 먼저 따져 볼 질문은 “두 부분의 답을 알 때 전체 답을 선형 시간 안에 만들 수 있는가”입니다. 이 글의 최근접 점 쌍 알고리즘이 까다로운 것도 바로 이 Combine 단계를 선형으로 만드는 기하학적 논증 때문입니다.

요구 환경: 예제에 구조화된 바인딩과 std::optional을 쓰므로 C++17 이상으로 컴파일합니다.

---

분할정복으로 O(n²)를 벗어나는 상황

대용량 배열 정렬

상황: 100만 건의 로그를 타임스탬프 기준으로 정렬해야 합니다. 버블 정렬은 O(n²)라 비교만 약 5천억 번이 필요해, 최적화 빌드에서도 수십 분 단위가 걸립니다. 잘못된 접근:

// ❌ 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) 보장.

---

정렬된 배열에서 빠른 검색

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

---

가장 가까운 두 점 찾기

상황: 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 log n) (아래 단순 구현은 O(n log² n)).

---

행렬 곱셈 최적화

상황: 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에서 유리
최근접 점쌍	Closest Pair	O(n log n)	x축 정렬 후 분할

---

Divide·Conquer·Combine 템플릿

세 단계: Divide, Conquer, Combine

flowchart TD
  A[원본 문제] --> B[Divide: 작은 하위 문제로 분할]
  B --> C[Conquer: 각 하위 문제 해결 - 재귀 또는 기본 케이스]
  C --> D[Combine: 하위 결과를 합쳐 최종 답 생성]
  D --> E[최종 답]

템플릿 코드

// 분할정복 일반 패턴
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);
}

재귀 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);
        }
    }
}

반복(bottom-up) 버전은 크기 1짜리 구간끼리 먼저 병합하고, 그다음 크기 2, 4, 8… 순서로 올라갑니다. 재귀 호출이 없으니 스택 깊이 걱정이 없고, 함수 호출 오버헤드도 사라집니다. 다만 병합정렬은 재귀 깊이가 log₂n(100만 개여도 약 20)에 불과해서, 스택 오버플로우가 실제로 문제가 되는 경우는 드뭅니다. 반복 버전이 진짜로 필요한 쪽은 최악의 경우 깊이가 n까지 갈 수 있는 퀵소트입니다. 제목의 “꼬리 재귀 제거”도 퀵소트에서 의미가 있는 기법인데, 두 부분 중 작은 쪽만 재귀하고 큰 쪽은 반복문으로 처리하면 최악의 입력에서도 스택 깊이가 O(log n)으로 제한됩니다.

---

병합정렬부터 Strassen까지 분할정복 예제

병합정렬 (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);
}

merge에서 a[i] <= a[j]의 =가 안정성을 결정합니다. 값이 같을 때 왼쪽(원래 앞에 있던) 원소를 먼저 가져가야 같은 키를 가진 원소들의 원래 순서가 유지됩니다. <로 바꾸면 정렬 결과는 여전히 맞지만 안정성이 깨지는데, int만 정렬할 때는 차이가 보이지 않다가 “타임스탬프로 정렬했더니 같은 시각 로그의 순서가 뒤섞였다” 같은 형태로 나중에 드러납니다. 표준 라이브러리에서 안정성이 필요하면 std::sort가 아니라 std::stable_sort를 써야 하는 이유도 같습니다.

tmp를 바깥에서 한 번만 할당해 모든 재귀 호출이 공유하는 것도 중요한 설계입니다. 병합할 때마다 std::vector를 새로 만들면 할당이 n번 가까이 일어나 실제 속도가 크게 떨어집니다. 이 구현은 tmp의 [lo, hi] 구간만 쓰므로 서로 다른 구간을 처리하는 호출끼리 충돌하지 않고, 뒤에서 볼 병렬 버전도 이 성질 덕분에 tmp를 공유할 수 있습니다.

---

퀵소트 (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);
}

Hoare 분할은 Lomuto 분할(마지막 원소를 피벗으로 두고 한 방향으로 훑는 방식)보다 교환 횟수가 적고, 중복 값이 많아도 양쪽이 고르게 나뉜다는 장점이 있습니다. 대신 반환값 j가 “피벗의 최종 위치”가 아니라 “왼쪽 구간의 끝”이라서, 재귀를 (lo, p)와 (p + 1, hi)로 나눠야 합니다. Lomuto 방식처럼 (lo, p - 1)과 (p + 1, hi)로 쓰면 원소 하나가 정렬에서 빠지고, 반대로 (lo, p)에 Lomuto를 섞으면 무한 재귀가 됩니다. 인터넷에서 두 방식의 코드 조각을 섞어 붙여 버그가 나는 경우가 가장 흔합니다.

중간 원소 피벗은 정렬된 입력에서의 최악 케이스는 피하지만, 최악의 입력이 사라진 것은 아닙니다. 피벗 선택 규칙이 고정되어 있으면 그 규칙을 역이용한 입력(“median-of-3 killer” 같은)을 만들 수 있고, 외부 입력을 정렬하는 서버라면 이것이 서비스 거부 공격 수단이 됩니다. std::sort가 퀵소트 대신 인트로소트를 쓰는 이유가 여기에 있습니다. 재귀 깊이가 2·log₂n을 넘으면 힙 정렬로 전환해 최악에도 O(n log n)을 보장합니다.

---

이진 탐색 (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);
}

이 구현은 폐구간 [lo, hi]를 불변식으로 씁니다. while (lo <= hi)와 hi = mid - 1이 짝을 이루는 이유가 그것이고, 반열린 구간 [lo, hi)로 바꾸려면 초기값 hi = size, 조건 lo < hi, 갱신 hi = mid를 함께 바꿔야 합니다. 셋 중 하나만 바꾸면 경계 원소를 놓치거나 무한 루프에 빠집니다. 또 hi를 int로 두는 것에도 이유가 있습니다. size_t로 두면 hi = mid - 1에서 mid가 0일 때 언더플로우가 일어나 아주 큰 값이 되고, 빈 배열에서는 size() - 1 자체가 최댓값이 되어 곧바로 범위 밖을 읽습니다.

실무에서는 “값이 있는가”보다 “처음으로 target 이상이 되는 위치”가 필요한 경우가 훨씬 많고, 중복 값이 있을 때 위 코드는 여러 위치 중 아무거나 돌려줍니다. 이럴 때는 직접 구현하기보다 std::lower_bound/std::upper_bound/std::equal_range를 쓰는 편이 안전합니다.

---

최근접 점 쌍 (Closest Pair of Points)

핵심: x좌표 기준 정렬 후, 중간으로 분할. 왼쪽 최소거리 dL, 오른쪽 dR. 중앙 밴드(폭 2×min(dL,dR)) 내 점들만 y순으로 검사.

#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(const 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(const std::vector<Point>& pts, 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, lo, mid);
    double dR = closestPairRec(pts, mid + 1, hi);
    double d = std::min(dL, dR);
    // 밴드: 현재 구간 [lo, hi] 안에서 |x - midX| < d 인 점들만
    std::vector<Point> band;
    for (int i = lo; i <= hi; ++i) {
        if (std::abs(pts[i].x - midX) < d) band.push_back(pts[i]);
    }
    std::sort(band.begin(), band.end(), [](const Point& a, const Point& b) {
        return a.y < b.y;
    });
    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(), [](const Point& a, const Point& b) {
        return a.x < b.x;
    });
    return closestPairRec(pts, 0, static_cast<int>(pts.size()) - 1);
}

이 알고리즘의 핵심은 closestInBand의 안쪽 루프가 상수 번만 돈다는 사실입니다. 밴드 안의 점을 y순으로 정렬해 두면, 어떤 점에서 y 차이가 d 미만인 이웃은 d×2d 크기의 직사각형 안에 있어야 합니다. 그런데 왼쪽과 오른쪽 각각에서는 이미 모든 점 쌍의 거리가 d 이상이므로, 그 직사각형 안에 들어갈 수 있는 점의 수는 기하학적으로 상한이 있습니다(교과서에서는 7개 이하로 보입니다). 그래서 이중 루프처럼 보여도 밴드 검사는 선형 시간입니다. (band[j].y - band[i].y) < best 조건이 빠지면 이 논증이 무너져 O(n²)으로 돌아갑니다.

위 구현은 이해하기 쉽도록 재귀 단계마다 밴드를 y로 다시 정렬하므로 전체 복잡도가 O(n log² n)입니다. 교과서의 O(n log n) 버전은 병합정렬처럼 재귀가 돌아오면서 y순 정렬 결과를 병합해 올려 보내 이 정렬 비용을 없앱니다. 흔한 실수는 전체 점을 y로 한 번 정렬한 배열을 모든 재귀 단계에서 통째로 훑는 것인데, 그러면 매 호출이 n개를 보게 되어 O(n²)이 됩니다. 결과는 맞게 나오기 때문에 작은 테스트에서는 이 성능 버그를 발견하기 어렵습니다. 또 거리 비교만 필요하다면 hypot 대신 제곱 거리를 비교하면 제곱근 계산을 피할 수 있습니다.

---

Strassen 행렬 곱셈 (Matrix Multiplication)

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

• M1 = (A11 + A22)(B11 + B22)
• M2 = (A21 + A22)B11
• M3 = A11(B12 - B22)
• M4 = A22(B21 - B11)
• M5 = (A11 + A12)B22
• M6 = (A21 - A11)(B11 + B12)
• M7 = (A12 - A22)(B21 + B22)

결과: C11 = M1+M4-M5+M7, C12 = M3+M5, C21 = M2+M4, C22 = M1-M2+M3+M6

검산 하나만 해 보면 C12 = M3 + M5 = A11·B12 − A11·B22 + A11·B22 + A12·B22 = A11·B12 + A12·B22로, 일반 행렬 곱의 정의와 일치합니다. 곱셈을 8번에서 7번으로 줄인 대가로 덧셈·뺄셈이 18번으로 늘었는데, 재귀에서는 곱셈 한 번이 곧 “크기 n/2 문제 하나”이므로 T(n) = 7T(n/2) + O(n²) = O(n^log₂7) ≈ O(n^2.807)이 됩니다. 공식을 외워 옮기다 부호 하나만 틀려도 컴파일은 되고 결과만 틀리므로, 구현 후에는 반드시 일반 곱셈 결과와 원소별로 비교하는 테스트를 붙여야 합니다.

#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 m1 = strassen(matrixAdd(a11, a22), matrixAdd(b11, b22));
    Matrix m2 = strassen(matrixAdd(a21, a22), b11);
    Matrix m3 = strassen(a11, matrixSub(b12, b22));
    Matrix m4 = strassen(a22, matrixSub(b21, b11));
    Matrix m5 = strassen(matrixAdd(a11, a12), b22);
    Matrix m6 = strassen(matrixSub(a21, a11), matrixAdd(b11, b12));
    Matrix m7 = strassen(matrixSub(a12, a22), matrixAdd(b21, b22));
    Matrix c11 = matrixAdd(matrixSub(matrixAdd(m1, m4), m5), m7);
    Matrix c12 = matrixAdd(m3, m5);
    Matrix c21 = matrixAdd(m2, m4);
    Matrix c22 = matrixAdd(matrixAdd(matrixSub(m1, m2), m3), m6);
    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에서는 덧셈과 임시 행렬 할당 비용이 곱셈 절감분보다 커서 일반 O(n³) 곱셈이 더 빠릅니다. 그래서 위 예제처럼 일정 크기(여기서는 64) 이하에서는 일반 곱셈으로 전환하는데, 적절한 전환점은 하드웨어와 구현에 따라 달라지므로 직접 측정해 정해야 합니다.

솔직히 말하면 이 구현은 알고리즘 구조를 보여 주기 위한 것이고, 실제 성능을 기대할 코드는 아닙니다. std::vector<std::vector<double>>는 행마다 메모리가 흩어져 캐시 효율이 나쁘고, 재귀 한 단계마다 부분행렬 8개와 중간 결과 수십 개를 새로 할당합니다. 캐시 블로킹과 SIMD를 적용한 일반 O(n³) 곱셈(OpenBLAS, Intel MKL, Eigen 등)이 대부분의 실용 크기에서 이런 Strassen 구현보다 훨씬 빠르고, 주요 BLAS 라이브러리도 기본 경로에서는 Strassen을 쓰지 않습니다. Strassen은 뺄셈이 섞여 있어 부동소수점 오차가 일반 곱셈보다 커지는 수치 안정성 문제도 있어서, 정밀도가 중요한 과학 계산에서는 특히 신중하게 씁니다. 행렬 곱이 병목이라면 먼저 BLAS 라이브러리를 쓰고, Strassen은 알고리즘 설계 기법을 이해하는 예제로 보는 것이 현실적입니다.

---

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

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

#include <vector>
#include <algorithm>
#include <limits>
// 중간을 지나는 최대 부분합 (a[mid]와 a[mid+1]을 반드시 포함)
int maxCrossingSum(const std::vector<int>& a, int lo, int mid, int hi) {
    int leftSum = 0, leftMax = std::numeric_limits<int>::min();
    for (int i = mid; i >= lo; --i) {
        leftSum += a[i];
        leftMax = std::max(leftMax, leftSum);
    }
    int rightSum = 0, rightMax = std::numeric_limits<int>::min();
    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);
}

leftMax와 rightMax의 초기값이 이 코드의 함정입니다. 흔히 0으로 초기화하는데, 그러면 “중간을 지나는 부분 배열”이 빈 구간을 허용하게 되어 모든 원소가 음수인 입력(예: {-3, -1})에서 실제 답 -1 대신 0을 돌려줍니다. 중간을 지나는 부분 배열은 a[mid]와 a[mid+1]을 반드시 포함해야 하므로 위처럼 최솟값으로 시작해야 합니다. 루프가 각각 최소 한 번은 돌기 때문에 두 값을 더해도 오버플로우는 생기지 않습니다. 참고로 이 문제는 카데인(Kadane) 알고리즘으로 O(n)에 풀리므로, 분할정복 버전(O(n log n))은 실전용이라기보다 Combine 단계 설계를 연습하는 예제입니다.

---

스택 오버플로우·무한 루프·Combine 누락

재귀 스택 오버플로우

증상: 큰 입력에서 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)

---

이진 탐색 무한 루프

증상: 프로그램이 종료되지 않습니다. 원인: 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로 업데이트해 반드시 범위 축소

---

병합 시 임시 배열 인덱스 오류

증상: 정렬 결과가 잘못되거나 크래시. 원인: 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];
}

---

분할정복 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)

---

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

---

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로 패딩

---

base case·mid 계산·하위 문제 독립성 원칙

Base case 명확히 정의

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

mid 계산 시 오버플로우 방지

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

하위 문제 독립성 확인

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

Combine 로직 검증

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

작은 구간 최적화

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

---

삽입 정렬 컷오프·임시 배열 재사용·3점 중앙값 피벗

작은 구간은 삽입 정렬

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

임시 배열 재사용

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

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

반복 버전으로 스택 절약

#include <stack>
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});
    }
}

명시적 스택으로 바꾸면 호출 스택 오버플로우는 사라지지만, 힙에 쌓이는 구간 수는 여전히 최악의 경우 O(n)이 될 수 있습니다. 두 구간 중 큰 쪽을 먼저 push하고 작은 쪽을 나중에 push해서 작은 쪽을 먼저 처리하게 하면, 스택에 남는 구간 수가 O(log n)으로 제한됩니다.

성능은 직접 측정하기

정렬 알고리즘의 실제 속도는 데이터 분포(무작위, 거의 정렬됨, 중복 많음), 원소 크기, 컴파일러 최적화, 캐시 크기에 따라 크게 달라지므로 다른 사람의 표를 그대로 믿기보다 자기 데이터로 측정하는 것이 맞습니다. 일반적인 경향만 말하면, 잘 다듬어진 std::sort(인트로소트 + 작은 구간 삽입 정렬)가 직접 짠 퀵소트·병합정렬보다 빠른 경우가 대부분이고, 안정성이 필요하면 std::stable_sort를 씁니다. 직접 구현이 의미 있는 경우는 병렬화나 외부 정렬처럼 표준 라이브러리가 제공하지 않는 구조가 필요할 때입니다. 측정할 때는 같은 입력을 매 반복마다 새로 복사해 정렬해야 합니다. 이미 정렬된 배열을 다시 정렬하는 실수를 하면 퀵소트·삽입 정렬의 결과가 비현실적으로 좋게 나옵니다.

---

분할정복 유틸리티와 std::async 병렬화

분할정복 유틸리티 템플릿

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

병렬 분할정복 (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);
}

이 병렬 버전이 a와 tmp를 두 스레드가 공유해도 데이터 경쟁이 없는 이유는, 왼쪽과 오른쪽 작업이 각각 [lo, mid]와 [mid+1, hi]의 서로 겹치지 않는 구간만 읽고 쓰기 때문입니다. merge는 get()으로 왼쪽 작업이 끝난 것을 확인한 뒤에야 두 구간을 모두 읽습니다. 주의할 점은 스레드 수입니다. std::launch::async는 호출마다 새 스레드를 만들 수 있어서, 임계값 10000에 100만 개를 정렬하면 재귀 트리 깊이만큼 분기해 백 개 넘는 스레드가 생깁니다. 코어 수보다 훨씬 많은 스레드는 전환 비용만 늘리므로, 재귀 깊이로 병렬 분기를 제한(예: 깊이 log₂(코어 수)까지만 async)하거나 C++17 병렬 알고리즘 std::sort(std::execution::par, ...)를 쓰는 편이 낫습니다.

에러 처리 및 검증

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

여기서 std::is_sorted 검사는 O(n)이라, 이진 탐색의 O(log n) 이점을 매 호출마다 없애 버립니다. 디버그 빌드에서만 assert(std::is_sorted(...))로 확인하고, 릴리스에서는 “정렬된 입력”을 함수의 사전 조건으로 문서화하는 것이 일반적인 절충입니다.

로깅 및 디버깅

#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;
    // ...
}

단위 테스트용 헬퍼

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

---

분할정복 구현 점검 목록

분할정복 설계 전

• 문제가 독립적인 하위 문제로 나뉘는지 확인
• 하위 문제가 겹치지 않으면 분할정복, 겹치면 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) 행렬 곱셈

핵심 원칙:

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

---

자주 묻는 질문 (FAQ)

Q. 직접 구현한 이진 탐색이 무한 루프에 빠지는 이유는 무엇인가요?

A. 대부분 mid 계산과 경계 갱신 규칙이 맞지 않아서 생깁니다. 예를 들어 lo < hi 조건에서 mid = (lo + hi) / 2로 계산하고 lo = mid로 갱신하면, 두 원소가 남았을 때 mid가 계속 lo와 같아져 범위가 줄지 않습니다. 구간을 반열린 [lo, hi) 같은 하나의 불변식으로 정하고 lo = mid + 1 또는 hi = mid처럼 매번 범위가 반드시 줄어들도록 갱신하며, 오버플로를 피하려면 mid는 lo + (hi - lo) / 2로 계산합니다.

Q. 이미 정렬된 입력에서 퀵소트가 스택 오버플로우를 일으키는 이유는 무엇인가요?

A. 첫 원소를 피벗으로 고르면 정렬된 입력에서 매번 한쪽으로만 분할되어 재귀 깊이가 n까지 늘어납니다. 병합 정렬은 항상 반씩 나누므로 깊이가 log n에 머뭅니다. 퀵소트는 중간값이나 랜덤 피벗을 쓰거나, 재귀가 깊어지면 힙 정렬로 전환하는 인트로소트 방식으로 최악의 경우를 피해야 합니다. 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++ 동적 계획법
• 탐욕 알고리즘이 맞는지 증명하기: 교환 논증과 활동 선택·거스름돈·작업 스케줄링 예제
• C++ 알고리즘 최적화 | 시간복잡도·공간복잡도·트레이드오프 [#54-10]
• C++ STL 알고리즘 기초: sort·find·transform·accumulate 실전 활용
• STL 정렬과 검색 함께 쓰기
• C++ 수학 알고리즘

---