분할 정복: 분해 계약과 병합 정확성

분할 정복은 큰 문제를 같은 형태의 작은 문제로 쪼개 해결하는 방식입니다. 초보 단계에서는 재귀 문법에만 집중하다가 병합 규칙을 놓쳐 오답이 자주 납니다. 그래서 분할보다 작은 해답을 어떻게 합칠지를 우선 고정해야 합니다.

여기서는 분해-정복-병합을 코드 트릭이 아니라 설계 계약으로 설명합니다. 하위 문제의 의미를 우선 문장으로 고정하고, 병합 불변식을 확인하는 순서로 진행합니다. 병합 정렬과 최대 부분합 예제로 같은 원리를 반복해 익힙니다.

분할 정복에서 분해 계약과 병합 불변식을 고정하는 설계 흐름도

핵심 원리 맵: 분할·병합 계약

분할 정복은 재귀 문법보다 하위 문제 정의와 병합 계약을 우선 잡으면 구현이 쉬워집니다. 문제를 나누기 전에 하위 문제 한 개가 정확히 무엇을 푸는가를 문장으로 우선 적어 보세요.

분할 정복은 원문제를 같은 형태의 작은 문제로 쪼개고, 각 해를 다시 합쳐 답을 만드는 방식입니다. 핵심은 분해 규칙, 하위 문제 의미, 결합 함수가 서로 모순 없이 연결되는지 확인하는 것입니다. 병합 정렬은 배열을 반으로 나눠 각각 정렬한 뒤 병합하는 전형적인 분할 정복 예시입니다.

기저 조건은 더 이상 나눌 필요가 없는 최소 입력 구간입니다. 재귀 호출을 종료하고 직접 답을 반환하는 경계 조건이므로, 누락되면 무한 재귀가 발생합니다. 예를 들어 배열 길이가 1 이하이면 이미 정렬된 상태이므로 그대로 반환하면 됩니다.

병합 불변식은 결합 과정 전체에서 유지해야 하는 논리 약속입니다. 입력 부분해가 만족하는 성질을 이용해 출력 부분해에서도 같은 성질이 보장되도록 결합해야 합니다. 병합 정렬에서는 left/right는 이미 정렬됨을 전제로 가장 작은 값을 순서대로 뽑아야 최종 정렬성이 유지됩니다.

분할 정복 설계가 운영에 미치는 영향

분할 정복은 정렬뿐 아니라 행렬 곱셈, 최근접 점, 최대 부분합 등 다양한 문제에 반복됩니다. 특히 문제 크기가 커질수록 전체를 한 번에 푸는 방식은 복잡도와 구현 난이도에서 불리해집니다.

잘 설계된 분할 정복은 검증 단위를 줄여 테스트와 디버깅을 체계화하는 데 유리합니다.

분해/병합 디버깅 시나리오

여기서는 오답 -> 디버깅 -> 교정 -> 검증 흐름으로 추적해, 어디서 불변식이 깨지는지 단계별로 확인합니다.

분할 정복의 공통 흐름을 병합 정렬로 추적합니다.

입력: [5, 2, 4, 1]

배열을 [5,2], [4,1]로 분할합니다.
각 하위 문제를 정렬해 [2,5], [1,4]를 만듭니다.
병합 규칙으로 두 배열을 결합해 [1,2,4,5]를 얻습니다.
중요한 기준은 분할보다 병합 불변식(두 입력은 정렬돼 있음)입니다.

분할 정복 적용 관찰 기준

아래 조건이 성립하면 분할 정복을 우선 고려합니다.

문제를 동일 형태의 하위 문제로 나눌 수 있는가?
병합 규칙이 명확하게 정의되는가?
하위 문제가 충분히 독립적인가?
재귀 깊이가 허용 가능한가?

병합 규칙을 증명할 수 없다면 분할 정복보다 DP 또는 그리디가 더 적합할 수 있습니다.

분할 정복: 병합 정렬

문제 의도: 분할-정복-병합 계약을 유지하는 정렬 구현을 확인합니다.
입력 예시: nums=[9,1,5,3,7,2,6,4]
출력 예시: [1,2,3,4,5,6,7,9]

main.cpp

#include <iostream>
#include <vector>
using namespace std;

vector<int> mergeSort(const vector<int>& arr) {
    if (arr.size() <= 1) return arr;

    int mid = static_cast<int>(arr.size()) / 2;
    vector<int> left(arr.begin(), arr.begin() + mid);
    vector<int> right(arr.begin() + mid, arr.end());

    left = mergeSort(left);
    right = mergeSort(right);

    vector<int> merged;
    merged.reserve(arr.size());
    int i = 0, j = 0;

    while (i < static_cast<int>(left.size()) && j < static_cast<int>(right.size())) {
        if (left[i] <= right[j]) merged.push_back(left[i++]);
        else merged.push_back(right[j++]);
    }

    while (i < static_cast<int>(left.size())) merged.push_back(left[i++]);
    while (j < static_cast<int>(right.size())) merged.push_back(right[j++]);
    return merged;
}

int main() {
    vector<int> nums = {9, 1, 5, 3, 7, 2, 6, 4};
    vector<int> sorted = mergeSort(nums);
    for (int x : sorted) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.Arrays;

public class Main {
    static int[] mergeSort(int[] arr) {
        if (arr.length <= 1) return arr;

        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        left = mergeSort(left);
        right = mergeSort(right);

        int[] merged = new int[arr.length];
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) merged[k++] = left[i++];
            else merged[k++] = right[j++];
        }
        while (i < left.length) merged[k++] = left[i++];
        while (j < right.length) merged[k++] = right[j++];
        return merged;
    }

    public static void main(String[] args) {
        int[] nums = {9, 1, 5, 3, 7, 2, 6, 4};
        int[] sorted = mergeSort(nums);
        System.out.println(Arrays.toString(sorted));
    }
}

main.py

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.extend(left[i:])
    merged.extend(right[j:])
    return merged

nums = [9, 1, 5, 3, 7, 2, 6, 4]
print(merge_sort(nums))
# 출력: [1, 2, 3, 4, 5, 6, 7, 9]

main.rs

fn merge_sort(arr: &[i32]) -> Vec<i32> {
    if arr.len() <= 1 {
        return arr.to_vec();
    }

    let mid = arr.len() / 2;
    let left = merge_sort(&arr[..mid]);
    let right = merge_sort(&arr[mid..]);

    let mut merged = Vec::with_capacity(arr.len());
    let (mut i, mut j) = (0usize, 0usize);

    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            merged.push(left[i]);
            i += 1;
        } else {
            merged.push(right[j]);
            j += 1;
        }
    }
    while i < left.len() {
        merged.push(left[i]);
        i += 1;
    }
    while j < right.len() {
        merged.push(right[j]);
        j += 1;
    }

    merged
}

fn main() {
    let nums = vec![9, 1, 5, 3, 7, 2, 6, 4];
    let sorted = merge_sort(&nums);
    println!("{:?}", sorted);
}

병합 단계 안정성 탐색 구간 조건 체크

하위 호출은 정렬된 배열을 반환한다는 계약을 가집니다. 병합 단계는 두 정렬 배열을 선형 시간에 결합해 같은 계약을 상위로 전달합니다.

병합 정렬은 입력 분포와 무관하게 성능이 예측 가능해 최악 성능 보장이 필요한 환경에서 유리합니다.

평균 시간복잡도: O(N log N)
최악 시간복잡도: O(N log N)
공간복잡도: O(N)

분할 정복: 최대 부분합(분할 정복 버전)

문제 의도: 최대 부분합을 왼쪽/오른쪽/교차 구간으로 분해해 계산합니다.
입력 예시: arr=[-2,1,-3,4,-1,2,1,-5,4]
출력 예시: 6

main.cpp

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;

int solve(const vector<int>& nums, int lo, int hi) {
    if (lo == hi) return nums[lo];

    int mid = (lo + hi) / 2;
    int leftBest = solve(nums, lo, mid);
    int rightBest = solve(nums, mid + 1, hi);

    int leftSum = INT_MIN, s = 0;
    for (int i = mid; i >= lo; --i) {
        s += nums[i];
        leftSum = max(leftSum, s);
    }

    int rightSum = INT_MIN;
    s = 0;
    for (int i = mid + 1; i <= hi; ++i) {
        s += nums[i];
        rightSum = max(rightSum, s);
    }

    int cross = leftSum + rightSum;
    return max({leftBest, rightBest, cross});
}

int maxSubarrayDivide(const vector<int>& nums) {
    return solve(nums, 0, static_cast<int>(nums.size()) - 1);
}

int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << maxSubarrayDivide(arr) << "\n";
    return 0;
}

Main.java

public class Main {
    static int solve(int[] nums, int lo, int hi) {
        if (lo == hi) return nums[lo];

        int mid = (lo + hi) / 2;
        int leftBest = solve(nums, lo, mid);
        int rightBest = solve(nums, mid + 1, hi);

        int leftSum = Integer.MIN_VALUE;
        int s = 0;
        for (int i = mid; i >= lo; i--) {
            s += nums[i];
            leftSum = Math.max(leftSum, s);
        }

        int rightSum = Integer.MIN_VALUE;
        s = 0;
        for (int i = mid + 1; i <= hi; i++) {
            s += nums[i];
            rightSum = Math.max(rightSum, s);
        }

        int cross = leftSum + rightSum;
        return Math.max(Math.max(leftBest, rightBest), cross);
    }

    static int maxSubarrayDivide(int[] nums) {
        return solve(nums, 0, nums.length - 1);
    }

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubarrayDivide(arr));
    }
}

main.py

def max_subarray_divide(nums):
    def solve(lo, hi):
        if lo == hi:
            return nums[lo]

        mid = (lo + hi) // 2
        left_best = solve(lo, mid)
        right_best = solve(mid + 1, hi)

        left_sum = cur = float('-inf')
        s = 0
        for i in range(mid, lo - 1, -1):
            s += nums[i]
            cur = max(cur, s)
        left_sum = cur

        right_sum = cur = float('-inf')
        s = 0
        for i in range(mid + 1, hi + 1):
            s += nums[i]
            cur = max(cur, s)
        right_sum = cur

        cross = left_sum + right_sum
        return max(left_best, right_best, cross)

    return solve(0, len(nums) - 1)

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_divide(arr))
# 출력: 6

main.rs

fn solve(nums: &[i32], lo: usize, hi: usize) -> i32 {
    if lo == hi {
        return nums[lo];
    }

    let mid = (lo + hi) / 2;
    let left_best = solve(nums, lo, mid);
    let right_best = solve(nums, mid + 1, hi);

    let mut left_sum = i32::MIN;
    let mut s = 0;
    for i in (lo..=mid).rev() {
        s += nums[i];
        left_sum = left_sum.max(s);
    }

    let mut right_sum = i32::MIN;
    s = 0;
    for i in (mid + 1)..=hi {
        s += nums[i];
        right_sum = right_sum.max(s);
    }

    let cross = left_sum + right_sum;
    left_best.max(right_best).max(cross)
}

fn max_subarray_divide(nums: &[i32]) -> i32 {
    solve(nums, 0, nums.len() - 1)
}

fn main() {
    let arr = vec![-2, 1, -3, 4, -1, 2, 1, -5, 4];
    println!("{}", max_subarray_divide(&arr));
}

교차 구간 결합 포인터 이동 추적

이 문제의 병합 기준은 중앙을 가로지르는 최댓값 계산입니다. 좌측 최댓값, 우측 최댓값, 교차 최댓값 중 최대를 택하면 전체 구간 최댓값 계약이 성립합니다.

분할 정복 구조가 명확하지만, 이 문제는 Kadane 알고리즘(O(N))이 더 빠르므로 적용 관점이 필요합니다.

평균 시간복잡도: O(N log N)
최악 시간복잡도: O(N log N)
공간복잡도: 재귀 스택 O(log N)

분할 정복: 반복형(bottom-up) 병합

문제 의도: 재귀 없이 구간 크기를 늘려가며 병합 정렬을 구현합니다.
입력 예시: arr=[5,2,4,1,3]
출력 예시: [1,2,3,4,5]

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

void mergeRange(vector<int>& arr, vector<int>& temp, int left, int mid, int right) {
    int i = left, j = mid, k = left;
    while (i < mid && j < right) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    while (i < mid) temp[k++] = arr[i++];
    while (j < right) temp[k++] = arr[j++];

    for (int x = left; x < right; ++x) arr[x] = temp[x];
}

vector<int> mergeSortBottomUp(vector<int> arr) {
    int n = static_cast<int>(arr.size());
    vector<int> temp = arr;
    int size = 1;

    while (size < n) {
        for (int left = 0; left < n; left += size * 2) {
            int mid = min(left + size, n);
            int right = min(left + size * 2, n);
            mergeRange(arr, temp, left, mid, right);
        }
        size *= 2;
    }
    return arr;
}

int main() {
    vector<int> sorted = mergeSortBottomUp({5, 2, 4, 1, 3});
    for (int x : sorted) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.Arrays;

public class Main {
    static void merge(int[] arr, int[] temp, int left, int mid, int right) {
        int i = left, j = mid, k = left;
        while (i < mid && j < right) {
            if (arr[i] <= arr[j]) temp[k++] = arr[i++];
            else temp[k++] = arr[j++];
        }
        while (i < mid) temp[k++] = arr[i++];
        while (j < right) temp[k++] = arr[j++];

        for (int x = left; x < right; x++) arr[x] = temp[x];
    }

    static int[] mergeSortBottomUp(int[] arr) {
        int n = arr.length;
        int[] temp = Arrays.copyOf(arr, n);
        int size = 1;

        while (size < n) {
            for (int left = 0; left < n; left += size * 2) {
                int mid = Math.min(left + size, n);
                int right = Math.min(left + size * 2, n);
                merge(arr, temp, left, mid, right);
            }
            size *= 2;
        }

        return arr;
    }

    public static void main(String[] args) {
        int[] sorted = mergeSortBottomUp(new int[]{5, 2, 4, 1, 3});
        System.out.println(Arrays.toString(sorted));
    }
}

main.py

def merge(arr, temp, left, mid, right):
    i, j, k = left, mid, left
    while i < mid and j < right:
        if arr[i] <= arr[j]:
            temp[k] = arr[i]
            i += 1
        else:
            temp[k] = arr[j]
            j += 1
        k += 1

    while i < mid:
        temp[k] = arr[i]
        i += 1
        k += 1

    while j < right:
        temp[k] = arr[j]
        j += 1
        k += 1

    for x in range(left, right):
        arr[x] = temp[x]

def merge_sort_bottom_up(arr):
    n = len(arr)
    temp = arr[:]
    size = 1

    while size < n:
        for left in range(0, n, size * 2):
            mid = min(left + size, n)
            right = min(left + size * 2, n)
            merge(arr, temp, left, mid, right)
        size *= 2

    return arr

print(merge_sort_bottom_up([5, 2, 4, 1, 3]))
# 출력: [1, 2, 3, 4, 5]

main.rs

fn merge(arr: &mut [i32], temp: &mut [i32], left: usize, mid: usize, right: usize) {
    let (mut i, mut j, mut k) = (left, mid, left);
    while i < mid && j < right {
        if arr[i] <= arr[j] {
            temp[k] = arr[i];
            i += 1;
        } else {
            temp[k] = arr[j];
            j += 1;
        }
        k += 1;
    }
    while i < mid {
        temp[k] = arr[i];
        i += 1;
        k += 1;
    }
    while j < right {
        temp[k] = arr[j];
        j += 1;
        k += 1;
    }
    arr[left..right].copy_from_slice(&temp[left..right]);
}

fn merge_sort_bottom_up(arr: &mut [i32]) {
    let n = arr.len();
    let mut temp = arr.to_vec();
    let mut size = 1usize;

    while size < n {
        let mut left = 0usize;
        while left < n {
            let mid = (left + size).min(n);
            let right = (left + size * 2).min(n);
            merge(arr, &mut temp, left, mid, right);
            left += size * 2;
        }
        size *= 2;
    }
}

fn main() {
    let mut nums = vec![5, 2, 4, 1, 3];
    merge_sort_bottom_up(&mut nums);
    println!("{:?}", nums);
}

반복형 병합 운용 수렴값 후속 검토

반복형 구현은 재귀 깊이 제한 이슈를 줄이고, 서비스 코드에서 스택 안정성을 높이는 데 유리합니다. 대신 인덱스 계산이 복잡해져 경계 테스트를 더 촘촘히 작성해야 합니다.

시간복잡도: O(N log N)
공간복잡도: O(N)

재귀/반복 병합 구현 비용 상쇄 지점

분할 정복은 아래 균형점을 갖습니다.

장점: 구조가 명확하고 병렬화 가능성이 높음
단점: 재귀 오버헤드와 병합 메모리 비용 존재
장점: 검증 단위가 분리돼 디버깅 유리
단점: 병합 규칙 설계가 틀리면 전체가 틀림

문제 규모와 운영 환경을 함께 봐야 합니다.

병합 누락 반례와 복구 절차

대표 실패는 다음과 같습니다.

기저 조건 누락으로 무한 재귀 발생
병합 후 잔여 원소 append 누락
중간 인덱스 계산 오류로 요소 손실
큰 입력에서 재귀 한도 초과

반례에는 길이 0, 길이 1, 중복 다량, 이미 정렬, 역정렬 케이스를 포함하세요.

분할 정복 성능 구간 정리

비용 상쇄 지점 판단 시에는 평균 성능뿐 아니라 최악 입력 분포, 메모리 제약, 구현 복잡도를 함께 비교해야 합니다.

알고리즘	평균 시간	최악 시간	공간
병합 정렬	`O(N log N)`	`O(N log N)`	`O(N)`
최대 부분합(분할 정복)	`O(N log N)`	`O(N log N)`	`O(log N)`
반복형 병합 정렬	`O(N log N)`	`O(N log N)`	`O(N)`

분할 구간 끝점 실수 방지 포인트

Python 슬라이싱 기반 구현은 가독성은 좋지만 복사 비용이 큽니다.
성능 민감 구간에서는 인덱스 기반 병합으로 전환을 검토하세요.
재귀 구현을 제출할 때는 입력 상한에 따른 스택 위험을 명시하는 편이 안전합니다.
분할 정복이 가능한 문제라도 항상 최적 해법인 것은 아니므로 대안 알고리즘과 비교가 필요합니다.

분할 정복 품질 체크포인트

기저 조건(len<=1)을 명확히 처리했는가
병합 단계에서 잔여 구간 append 누락이 없는가
재귀 깊이/스택 제약을 입력 상한과 함께 검토했는가
길이 0/1/역정렬/중복 다수 반례를 테스트했는가

분할 정복 점검 정리

분할 정복의 본질은 재귀가 아니라 계약입니다. 분해 규칙과 병합 불변식을 명확히 정의하면 복잡한 문제도 예측 가능한 구조로 안정적으로 해결할 수 있습니다.

분할 정복: 분해 계약과 병합 정확성

목차