---
title: "분할 정복: 문제를 나누는 것만으로 빨라지지는 않는다"
author: "Lee"
published_at: "2026-10-04T23:17:00.226Z"
updated_at: "2026-09-30T09:26:53.502Z"
tags: ["컴퓨터공학","알고리즘"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%EB%B6%84%ED%95%A0-%EC%A0%95%EB%B3%B5-%EB%AC%B8%EC%A0%9C%EB%A5%BC-%EB%82%98%EB%88%84%EB%8A%94-%EA%B2%83%EB%A7%8C%EC%9C%BC%EB%A1%9C-%EB%B9%A8%EB%9D%BC%EC%A7%80%EC%A7%80%EB%8A%94-%EC%95%8A%EB%8A%94%EB%8B%A4"
ai_assisted: false
---

# 분할 정복: 문제를 나누는 것만으로 빨라지지는 않는다

[원문](https://ariser.io/@writer_a1cd615ab19e/%EB%B6%84%ED%95%A0-%EC%A0%95%EB%B3%B5-%EB%AC%B8%EC%A0%9C%EB%A5%BC-%EB%82%98%EB%88%84%EB%8A%94-%EA%B2%83%EB%A7%8C%EC%9C%BC%EB%A1%9C-%EB%B9%A8%EB%9D%BC%EC%A7%80%EC%A7%80%EB%8A%94-%EC%95%8A%EB%8A%94%EB%8B%A4)

분할 정복은 큰 문제를 작은 부분문제로 나누고, 부분문제를 해결한 뒤 그 결과를 합치는 알고리즘 설계 방식이다. 나누기, 해결하기, 결합하기라는 세 단계의 관계가 핵심이다. 단순히 함수를 여러 개로 나누는 코드 구조와는 다르다.

![4·1·3·2를 작은 배열로 분할한 뒤 1·2·3·4로 병합하는 과정](/api/v1/media/70070812-e75a-43df-ad36-e0cc31d9d9bc)

*작은 문제를 해결하고 그 결과를 결합하는 분할 정복의 흐름이다.*

### 부분문제의 관계를 먼저 본다

대표 사례인 병합 정렬은 배열을 두 구간으로 나눈다. 각 구간을 재귀적으로 정렬한 뒤 두 정렬 결과를 하나의 순서로 병합한다. 왼쪽 구간을 정렬하는 데 오른쪽 구간의 정렬 결과가 필요하지 않으므로 두 부분문제는 독립적으로 해결할 수 있다.

[7,2,5,1]을 나누면 [7,2]와 [5,1]이 되고, 다시 길이 1 구간으로 나뉜다. 두 원소씩 합쳐 [2,7], [1,5]를 만든 뒤 가장 작은 앞 원소를 비교해 [1,2,5,7]을 얻는다. 이 과정을 이해하려면 나누는 그림만큼 합치는 단계도 자세히 봐야 한다.

정확성은 각 작은 구간이 올바르게 정렬되었다는 가정과, 병합 과정이 두 구간의 모든 원소를 순서대로 보존한다는 사실에 달려 있다. 분할 정복의 결합 함수가 잘못되면 부분문제의 답이 모두 맞아도 전체 답은 틀릴 수 있다.

### 점화식으로 비용을 표현하기

부분문제 수가 a, 크기가 원래의 1/b, 분할과 결합 비용이 f(n)이면 흔히 T(n)=aT(n/b)+f(n) 형태가 나온다. 병합 정렬은 T(n)=2T(n/2)+Θ(n)이다. 각 재귀 층에서 처리하는 전체 원소 수가 n이고 층 수가 log n 정도라서 Θ(n log n)이 된다.

반면 이진 탐색은 절반으로 나눈 두 구간 중 하나만 탐색하므로 T(n)=T(n/2)+Θ(1)이다. 같은 절반 분할이라도 재귀 호출 수와 결합 비용이 다르면 최종 복잡도가 달라진다. 모든 점화식에 특정 정리를 기계적으로 적용할 수 있는 것도 아니다.

공간 비용에는 부분 결과, 보조 배열, 호출 스택이 들어간다. 슬라이스를 복사하는 구현은 인덱스 범위만 전달하는 구현보다 추가 비용이 클 수 있다. 이론에서 무료로 취급한 분할이 실제 코드에서는 복사 작업일 수 있다는 점을 확인해야 한다.

독립 부분문제는 병렬 실행에 어울리지만, 실행 준비 비용과 결합 단계가 속도 향상을 제한한다. 부분문제가 반복해서 겹친다면 분할 정복만으로는 같은 일을 여러 번 수행할 수 있다. 그런 경우 결과 저장이나 동적 계획법이 더 적합할 수 있다.

### 분할의 경계를 코드로 표현하기

```text
sort_range(array, first, last):
    if last - first <= 1:
        return
    middle = first + (last - first) // 2
    sort_range(array, first, middle)
    sort_range(array, middle, last)
    merge the sorted ranges [first, middle) and [middle, last)
```

이 표현은 배열을 복사하지 않고 반열린 인덱스 구간으로 문제를 전달한다. middle이 두 구간 사이 경계이므로 빠뜨린 원소나 중복 포함 원소가 없다. 기저 조건은 빈 구간과 원소 하나를 동시에 처리한다. 분할한 크기의 합이 원래 크기와 같고 각 비기저 호출이 더 작아진다는 사실은 종료와 정확성 모두를 점검하는 기준이다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)