분할 정복

본문

본문

선택 정렬은 남은 원소 가운데 가장 작은 것을 찾아 앞으로 보내기를 되풀이한다. 원소 1000개는 금방 정렬하지만, 100만 개를 정렬하려면 1초에 1억 번 비교하는 컴퓨터로도 한 시간 넘게 걸린다. 그런데 리스트를 반으로 나누어 각각 정렬한 뒤 합치는 병합 정렬은 같은 100만 개를 0.2초 만에 정렬한다. 나누고 합치는 일을 더했는데 왜 오히려 수만 배 빨라질까?

원소의 수

그림 1. 선택 정렬과 병합 정렬의 비교 횟수와 1초에 1억 번 비교할 때의 시간(막대는 로그 길이). 원소가 많아질수록 두 방법의 차이가 크게 벌어진다.

먼저 알아야 할 것문제 분해(문제 분해), 재귀 구조(재귀 구조), 로그(수학).

3.4.1나누고, 풀고, 합치기

분할 정복은 문제를 같은 모양의 작은 문제들로 나누고, 각각을 재귀로 푼 뒤, 그 답을 합쳐 전체의 답을 만든다. 병합 정렬은 리스트를 반으로 나누어 왼쪽 절반과 오른쪽 절반을 각각 정렬하고, 정렬된 두 리스트를 합친다. 원소가 하나뿐인 리스트는 이미 정렬되어 있으므로 더 나누지 않는다. 정렬된 두 리스트를 합칠 때는 두 리스트의 맨 앞 원소만 견주어 작은 것을 꺼내면 되므로, 원소 수만큼만 비교한다. 이렇게 합치는 일이 싸기 때문에 분할 정복이 빛난다.

정리 3.4.1 병합 정렬의 비교 횟수

원소 \(n\)개를 반씩 나누기를 되풀이하면 \(\log_2 n\)단계 만에 하나씩 쪼개진다. 각 단계에서 합치는 비교는 모두 합해 \(n\)번 정도이므로 전체 비교 횟수는 약 \(n\log_2 n\)이다. 선택 정렬은 \(\dfrac{n(n-1)}{2}\)번 비교한다.

그림 1에서 원소 수를 바꾸어 보자. 원소 1000개는 선택 정렬이 약 50만 번, 병합 정렬이 약 1만 번 비교한다. 원소 100만 개는 선택 정렬이 약 5000억 번으로 한 시간 넘게 걸리지만, 병합 정렬은 약 2000만 번으로 0.2초면 끝난다. 원소가 1000배 늘 때 선택 정렬의 일은 100만 배 늘지만, 병합 정렬의 일은 2000배만 는다. 반으로 나누는 일을 스무 번만 해도 100만 개가 하나씩으로 쪼개지기 때문이다.¹

3.4.2분할 정복이 통하는 조건

분할 정복이 효율적이려면 두 조건이 맞아야 한다. 첫째, 부분 문제의 크기가 일정한 비율로 줄어야 한다. 반씩 줄면 \(\log n\)단계면 끝나지만, 하나씩만 줄면 \(n\)단계가 걸린다. 둘째, 부분 문제의 답을 합치는 일이 싸야 한다. 정렬된 두 리스트는 \(n\)번이면 합칠 수 있지만, 합치는 일이 \(n^2\)번 걸린다면 나누는 의미가 없다. 정렬된 리스트에서 값을 찾는 이진 탐색은 절반을 버리고 한쪽만 풀면 되므로 합치는 일조차 없어 \(\log n\)번이면 끝난다. 거듭제곱 \(a^n\)도 \(a^{n/2}\)를 한 번 구해 제곱하면 \(\log n\)번의 곱셈으로 구한다.

그림 2. 크기가 일정한 비율로 줄고 합치는 일이 쌀 때 분할 정복이 큰 이득을 준다.

3.4.3예제 풀이

예제 3.4.2

정렬된 두 리스트 [2, 5, 8, 9]와 [1, 3, 7, 10]을 병합 정렬의 방식으로 합쳐라. 몇 번 비교하는가? 원소 8개를 병합 정렬할 때 나누는 단계는 몇 단계이며, 비교 횟수는 대략 몇 번인가?

맨 앞끼리 견준다. 2와 1에서 1, 2와 3에서 2, 5와 3에서 3, 5와 7에서 5, 8과 7에서 7, 8과 10에서 8, 9와 10에서 9를 꺼내고, 남은 10을 붙인다. 결과는 [1, 2, 3, 5, 7, 8, 9, 10]이고, 비교는 7번이다. 원소 8개를 합치는 데 많아야 7번이면 된다.

원소 8개는 8 → 4 → 2 → 1로 \(\log_2 8 = 3\)단계 만에 하나씩 쪼개진다. 단계마다 합치는 비교가 많아야 8번 안쪽이므로 전체 비교는 약 \(8 \times 3 = 24\)번이다. 선택 정렬은 \(8 \times 7 \div 2 = 28\)번으로, 원소가 적을 때는 별 차이가 없다. 그런데 원소가 100만 개가 되면 2000만 번과 5000억 번으로 벌어진다. 즉 분할 정복의 이득은 문제가 클수록 커진다. 그래서 대부분의 프로그래밍 언어의 정렬 함수는 이런 분할 정복 정렬을 쓴다.

아래 탐구 카드에서 병합 정렬과 이진 탐색을 직접 짜 보고, 원소 수를 늘리며 실행 시간을 재어 보자.

병합 정렬은 1945년 폰 노이만이 처음 만든 것으로 알려져 있다. 원소를 견주어 정렬하는 어떤 방법도 최악의 경우 약 \(n\log_2 n\)번보다 적게 비교할 수는 없다는 것이 증명되어 있다.

마무리

분할 정복은 문제를 같은 모양의 작은 문제로 나누어 풀고 그 답을 합치며, 병합 정렬은 반씩 나누기를 \(\log_2 n\)단계 하고 단계마다 \(n\)번쯤 비교해 합쳐 약 \(n\log_2 n\)번이면 정렬을 끝낸다. 부분 문제가 일정한 비율로 줄고 합치는 일이 쌀 때 큰 이득이 있다. 그래서 처음 질문의 100만 개는 선택 정렬로는 5000억 번 비교해 한 시간이 넘게 걸리지만, 병합 정렬로는 2000만 번이면 되어 0.2초로 준다.

탐구 1

반으로 나눠 정렬하면 왜 빨라질까?

분할 정복 · 합병 정렬과 퀵 정렬 · 재귀 트리

아직 정렬 안 됨정렬 끝피벗 (퀵 정렬)

입력

원소 수 n = 8

비교 횟수 (지금 / 전체): —
재귀 깊이: —
선택 정렬이라면 n(n−1)/2: —
참고 n log₂n: —

비교 횟수는 원소 두 개의 크기를 비교한 횟수이다. 합병 정렬은 merge 안의 비교를, 퀵 정렬은 피벗과 비교되는 원소 수(구간 길이 − 1)를 센다. 위 퀵 정렬 코드는 리스트를 두 번 훑으므로 실제 비교는 그 두 배이지만, 자리를 바꾸며 한 번만 훑는 구현도 있어 한 번으로 센다.

질문원소를 하나씩 보며 가장 작은 것을 골라 앞으로 보내는 선택 정렬은 원소 16개에 비교를 120번 한다. 1000개면 약 50만 번이다. 리스트를 반으로 나눠 각각 정렬한 뒤 합치면 비교가 줄어들까?
복원문제 분해는 전체 문제를 같은 모양의 부분 문제로 나누고, 부분 문제의 답으로 전체 답을 만드는 관계를 찾는 것이다. 재귀 함수는 기저 사례에서 멈춘다.
설명분할 정복은 ① 문제를 작은 부분 문제로 나누고(분할), ② 각각을 재귀로 풀고(정복), ③ 그 답을 합쳐 전체 답을 만든다(결합). 합병 정렬은 무조건 반으로 나누고, 정렬된 두 리스트의 맨 앞끼리 비교하며 하나로 합친다. 나누기는 쉽고 합치기에서 일을 한다. 퀵 정렬은 피벗을 하나 골라 그보다 작은 것과 크거나 같은 것으로 나누고, 각각 정렬해 이어 붙인다. 나누기에서 일을 하고 합치기는 이어 붙이기뿐이다.
연결합병 정렬은 한 층마다 합병에서 많아야 n번 비교하고, 반씩 나누므로 층은 약 log₂n개이다. 그래서 비교 횟수는 n log₂n 정도이고, 입력이 어떻게 놓여 있든 같다. 퀵 정렬은 피벗이 구간을 고르게 나누면 합병 정렬과 비슷하지만, 이미 정렬된 리스트에서 첫 원소를 피벗으로 고르면 한쪽이 비어 층이 n개가 되고 비교가 n(n−1)/2번으로 늘어난다.
적용n = 8, 무작위 입력에서 합병 정렬을 한 단계씩 실행하며 재귀 트리가 내려갔다 올라오는 순서를 따라가자. 이어서 n = 16에서 세 가지 입력에 대해 두 방법의 비교 횟수와 재귀 깊이를 표로 적어 보자. 퀵 정렬이 가장 느린 입력은 무엇이고, 그때 재귀 트리는 어떤 모양인가?
판단"나누기만 하면 빨라진다"는 틀린 생각이다. 하노이 탑처럼 크기가 하나만 줄어드는 부분 문제가 둘이면 오히려 일이 두 배씩 늘고, 퀵 정렬도 나뉘는 비율이 나쁘면 느려진다. 분할 정복이 빠른 것은 부분 문제의 크기가 일정한 비율로 줄고, 결합하는 비용이 작기 때문이다. 실제 퀵 정렬은 피벗을 무작위로 고르거나 세 값의 중간값으로 골라 이런 최악을 피하며, 파이썬의 sorted()는 합병 정렬과 삽입 정렬을 섞은 Timsort를 쓴다.

확인조건이 달라지면

원소 1024개를 정렬한다. 합병 정렬의 재귀 트리는 몇 층(나누는 횟수)이고, 한 층의 합병에서 비교는 최대 약 몇 번일까?

탐구 2

3의 1000제곱을 곱셈 몇 번으로 구할 수 있을까?

분할 정복 · 부분 문제의 답 재사용 · 거듭제곱

밑 a = 3

지수 n = 13

반복문으로 a를 곱하기: —
power(n//2)를 두 번 호출: —
half에 저장해 한 번 호출: —
n의 2진수: —

세 칸의 숫자는 곱셈 횟수이다. "두 번 호출"은 half를 쓰지 않고 return power(a, n // 2) * power(a, n // 2)처럼 쓴 경우이다. 파이썬의 정수는 자릿수 제한이 없어 큰 값도 정확히 구하지만, 자릿수가 커지면 곱셈 한 번도 오래 걸린다. 실제로는 pow(a, n) 또는 a ** n을 쓴다.

질문3¹⁰⁰⁰을 구하려고 3을 계속 곱하면 곱셈 999번이 필요하다. 그런데 3¹⁰⁰⁰ = (3⁵⁰⁰)²이므로 3⁵⁰⁰만 알면 곱셈 한 번으로 끝난다. 이렇게 계속 나누면 곱셈이 몇 번으로 줄어들까?
복원분할 정복은 문제를 작은 부분 문제로 나누고, 그 답을 결합해 전체 답을 만든다. 지수 법칙에 따라 a^2m = (a^m)², a^2m+1 = (a^m)² × a이다.
설명power(a, n)은 부분 문제 power(a, n // 2)의 답 half를 구한 뒤, n이 짝수면 half × half, 홀수면 half × half × a를 돌려준다. 지수가 매번 반으로 줄므로 호출은 약 log₂n번만 쌓이고, 한 층에서 곱셈은 1~2번이다. 각 줄의 n을 2진수로 보면 한 줄 내려갈 때마다 맨 오른쪽 자리가 하나씩 떨어진다. 그래서 곱셈을 두 번 하는 홀수 단계(주황)의 수는 n의 2진수에 있는 1의 개수와 같다.
연결합병 정렬은 크기가 반인 부분 문제 두 개를 풀어야 하지만, 거듭제곱은 같은 부분 문제 하나의 답을 두 번 쓰면 된다. 그 답을 변수 half에 저장하지 않고 power(a, n // 2)를 두 번 부르면, 호출 수가 층마다 두 배로 늘어 결국 곱셈 횟수가 반복문과 비슷하거나 오히려 많아진다. 분할 정복의 효율은 부분 문제의 개수, 크기가 줄어드는 비율, 결합 비용이 함께 정한다.
적용a = 3, n = 13에서 한 단계씩 실행하며 호출이 쌓였다가 아래에서부터 값이 돌아오는 순서를 확인해 보자. n을 1000으로 놓고 세 방법의 곱셈 횟수를 비교해 보자. n = 1023과 n = 1024 중 한 번 호출 방법의 곱셈이 더 많은 쪽은 어디이고, 왜 그런지 2진수로 설명해 보자.
판단곱셈 횟수가 줄었다고 실행 시간이 꼭 그만큼 주는 것은 아니다. 3¹⁰⁰⁰은 478자리 수라서 곱셈 한 번도 작은 수의 곱셈보다 훨씬 오래 걸린다. 그래도 같은 수를 반복해서 곱하는 방법보다는 훨씬 빠르며, 암호에서 쓰는 "aⁿ을 m으로 나눈 나머지" 계산은 매 단계 나머지만 남겨 수가 커지지 않게 하면서 이 방법을 그대로 쓴다. 파이썬의 pow(a, n, m)이 바로 이 계산이다.

확인조건이 달라지면

행렬 거듭제곱 Mⁿ도 같은 코드로 구할 수 있다(1 대신 단위 행렬). n = 64일 때, half를 저장하는 방법의 행렬 곱셈 횟수에 가장 가까운 것은?