분할 정복과 병합 정렬 · 알고리즘 노트

개념

분할 정복은 문제를 같은 형태의 더 작은 문제로 나누고, 각각 해결한 결과를 결합하여 원래 문제의 답을 구하는 방법입니다.

분할·해결·결합

분할: 원래 문제를 더 작은 문제들로 나눕니다.
해결: 작은 문제에 같은 방법을 적용합니다. 바로 답을 구할 수 있을 만큼 작아지면 재귀 호출을 끝냅니다.
결합: 작은 문제의 답을 모아 원래 문제의 답을 만듭니다.

재귀 호출은 작은 문제의 답을 구하고 돌아오는 흐름을 표현합니다. 이때 무엇을 기준으로 나눌지, 어디서 호출을 끝낼지, 구한 답을 어떻게 합칠지를 정해야 합니다.

대표 예시: 병합 정렬

병합 정렬은 배열을 두 부분으로 나누고, 각 부분을 정렬한 다음 하나로 합칩니다. 작은 문제도 배열을 정렬하는 문제이므로 같은 절차를 반복할 수 있습니다.

배열 $[4,1,3,2]$ 를 정렬하는 과정은 다음과 같습니다.

단계	배열의 상태	처리
분할	$[4,1,3,2]\rightarrow[4,1], [3,2]$	가운데에서 두 부분으로 나눕니다.
분할	$[4], [1], [3], [2]$	각 부분을 다시 나눕니다.
종료	$[4], [1], [3], [2]$	원소가 하나인 배열은 정렬된 상태입니다.
결합	$[1,4], [2,3]$	작은 두 배열을 정렬된 순서로 합칩니다.
결합	$[1,2,3,4]$	두 정렬 결과를 합쳐 원래 문제를 해결합니다.

정렬된 두 부분의 병합

길이가 $1$ 이하이면 이미 정렬되어 있습니다. 그보다 길면 중간에서 나누어 양쪽을 재귀적으로 정렬합니다. 병합할 때 두 부분의 맨 앞 원소를 비교하여 작은 값을 결과에 넣습니다.

정렬된 $[1,4,7]$ 과 $[2,3,8]$ 을 합칠 때 $1,2,3,4,7,8$ 순서로 원소를 꺼냅니다. 한쪽 원소를 모두 옮겼으면 다른 쪽의 남은 원소를 이어 붙입니다.

값이 같을 때 왼쪽 원소를 먼저 선택하면 기존 순서를 유지하는 안정 정렬이 됩니다.

두 부분이 각각 정렬되어 있으면 전체에서 가장 작은 남은 값은 두 부분의 맨 앞 값 중 하나입니다. 예를 들어 $[1,4,7]$ 과 $[2,3,8]$ 에서 $1$ 을 선택한 다음에는 $4$ 와 $2$ 를 비교하면 됩니다. 뒤쪽의 $7$ 이나 $8$ 은 각 부분의 앞 값보다 크므로 먼저 선택될 수 없습니다. 이 성질 덕분에 두 부분을 한 번씩 읽으며 합칠 수 있습니다.

복잡도

원소 수를 $N$ 이라고 합니다. 각 깊이에서 모든 원소를 한 번씩 병합하고, 분할 깊이는 $O(\log N)$ 입니다.

연산	시간복잡도	공간복잡도
병합 정렬	$O(N\log N)$	임시 배열 $O(N)$ , 재귀 $O(\log N)$

예제

문제

수를 오름차순으로 정렬하여라.

입력

첫째 줄에 원소 수 $N$ 이 주어진다. $1\le N\le100$ 이다.

둘째 줄에 수열의 원소 $a_1,a_2,\ldots,a_N$ 이 공백을 사이에 두고 주어진다. $1\le a_i<10\,000$ 이다.

출력

정렬한 수를 한 줄에 공백으로 구분하여 출력한다.

예제 코드

C++20

#include <iostream>

using namespace std;

int a[101], t[101];

void sortRange(int l, int r) {
    int m, i, j, k;

    // 구간 [l, r)의 원소가 하나 이하이면 정렬 종료
    if (r - l <= 1) return;
    m = (l + r) / 2;
    // 왼쪽 [l, m)과 오른쪽 [m, r)을 각각 정렬
    sortRange(l, m);
    sortRange(m, r);

    i = l;
    j = m;
    k = l;
    // 두 구간의 맨 앞 값 중 작은 값을 임시 배열에 저장
    while (i < m && j < r) {
        // 값이 같으면 왼쪽 원소를 먼저 선택하여 기존 순서 유지
        if (a[i] <= a[j]) {
            t[k] = a[i];
            ++i;
        }
        else {
            t[k] = a[j];
            ++j;
        }
        ++k;
    }
    while (i < m) {
        t[k] = a[i];
        ++k;
        ++i;
    }
    while (j < r) {
        t[k] = a[j];
        ++k;
        ++j;
    }
    // 병합한 결과를 원래 구간에 반영
    for (i = l; i < r; ++i) {
        a[i] = t[i];
    }
}

int main() {
    int n, i;

    cin >> n;
    for (i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sortRange(0, n);

    for (i = 0; i < n; ++i) {
        cout << a[i] << ' ';
    }
    cout << '\n';
}

Java 17

import java.util.*;

public class Main {
    static int[] a = new int[101], t = new int[101];

    static void sortRange(int l, int r) {
        int m, i, j, k;

        // 구간 [l, r)의 원소가 하나 이하이면 정렬 종료
        if (r - l <= 1) return;
        m = (l + r) / 2;
        // 왼쪽 [l, m)과 오른쪽 [m, r)을 각각 정렬
        sortRange(l, m);
        sortRange(m, r);

        i = l;
        j = m;
        k = l;
        // 두 구간의 맨 앞 값 중 작은 값을 임시 배열에 저장
        while (i < m && j < r) {
            // 값이 같으면 왼쪽 원소를 먼저 선택하여 기존 순서 유지
            if (a[i] <= a[j]) {
                t[k] = a[i];
                ++i;
            }
            else {
                t[k] = a[j];
                ++j;
            }
            ++k;
        }
        while (i < m) {
            t[k] = a[i];
            ++k;
            ++i;
        }
        while (j < r) {
            t[k] = a[j];
            ++k;
            ++j;
        }
        // 병합한 결과를 원래 구간에 반영
        for (i = l; i < r; ++i) {
            a[i] = t[i];
        }
    }

    public static void main(String[] args) {
        Scanner in;
        int n, i;

        in = new Scanner(System.in);
        n = in.nextInt();
        for (i = 0; i < n; ++i) {
            a[i] = in.nextInt();
        }
        sortRange(0, n);

        for (i = 0; i < n; ++i) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
}

Python 3

def sort_range(l, r):
    # 구간 [l, r)의 원소가 하나 이하이면 정렬 종료
    if r - l <= 1:
        return
    m = (l + r) // 2
    # 왼쪽 [l, m)과 오른쪽 [m, r)을 각각 정렬
    sort_range(l, m)
    sort_range(m, r)

    i, j, k = l, m, l
    # 두 구간의 맨 앞 값 중 작은 값을 임시 배열에 저장
    while i < m and j < r:
        # 값이 같으면 왼쪽 원소를 먼저 선택하여 기존 순서 유지
        if lst[i] <= lst[j]:
            tmp[k] = lst[i]
            i += 1
        else:
            tmp[k] = lst[j]
            j += 1
        k += 1
    while i < m:
        tmp[k] = lst[i]
        i += 1
        k += 1
    while j < r:
        tmp[k] = lst[j]
        j += 1
        k += 1
    # 병합한 결과를 원래 구간에 반영
    for i in range(l, r):
        lst[i] = tmp[i]


n = int(input())
lst = list(map(int, input().split()))
tmp = [0] * n
sort_range(0, n)
print(*lst)

2.10.1 Concept

개념

분할·해결·결합

대표 예시: 병합 정렬

정렬된 두 부분의 병합

복잡도

예제

문제

입력

출력

예제 입력

예제 출력

예제 코드