[자료 구조/알고리즘] 분할 정복과 정렬

분할 정복 알고리즘

분할 정복(divide-and-conquer) 알고리즘이란 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 분할 정복 알고리즘은 재귀적(recursive) 알고리즘을 사용한다. 문제를 동일하거나 관련된 유형의 두 개 이상의 하위 문제(subproblem)로 재귀적으로 분할한 다음 하위 문제에 대한 결과를 결합하여 원래 문제에 대한 결과를 얻는다.

분할 정복 알고리즘을 사용하는 예로는 이진 탐색(binary search), 퀵 정렬(quick sort), 병합 정렬(merge sort), 고속 푸리에 변환(fast Fourier transform, FFT) 등이 있다.

분할 정복 알고리즘은 재귀 호출을 사용하므로 함수 호출 시 콜 스택(call stack)의 스택 프레임이 스택 구조에서 처리되는 과정에서 오버헤드가 발생할 수 있다. 또한 재귀 스택에 할당된 메모리가 충분해야 하며 그렇지 않으면 스택 오버플로우(stack overflow)로 인해 실행이 실패할 수 있다. 시간 효율적인 분할 정복 알고리즘은 작은 재귀 깊이(recursion depth)를 가진다.

분할 정복 알고리즘을 통한 문제 해결은 크게 세 과정으로 나눌 수 있다.

1. 분할 (divide): 주어진 문제를 작게 줄여서(decompose) 하위 문제로 만드는 법을 찾는다. 하위 문제는 가능한한 가장 작고 간단한 문제이어야 한다. 재귀 함수를 호출할 때마다 문제를 작게 나누어 하위 문제로 만든다. 하위 문제를 더 이상 나눌 수 없을 때까지 문제를 재귀적으로 분할한다. 하위 문제는 원래 문제의 일부를 나타내야 한다. 재귀는 종료되어야 하므로 기본 단계(base case)는 항상 주어져야 한다. 예를 들어, 재귀 함수 호출을 할 때마다 호출 대상이 되는 배열의 크기가 점점 감소해야 한다. 이때 재귀 함수 호출은 모든 기본 단계를 만나기 전까지 완료되지 않는다. 재귀에서는 부분적으로 실행된 함수 호출의 상태를 모두 저장한다.
2. 정복 (conquer): 하위 문제를 재귀적으로 해결한다. 이때 기본 단계를 지정하여 재귀가 종료될 수 있도록 한다. 하위 문제가 더 이상 재귀할 수 없을 만큼 작아지면 해당 하위 문제는 기본 단계에 해당된다. 하위 문제들의 해결 결과는 재사용될 수 있으므로 메모리에 저장되어야 한다.
3. 결합 (combine): 하위 문제에 대한 해결 결과를 결합하여 원래 문제를 해결한다. 기본 단계의 하위 문제를 해결한 결과는 더 큰 하위 문제를 해결하는데 사용되며, 이후 더 작은 하위 문제가 더 큰 하위 문제를 해결하는데 사용되는 과정이 반복된다. 하위 문제들의 해결 결과가 원래 문제를 해결하는데 사용될 때까지 아래에서 위로 전파된다.

퀵 정렬

퀵 정렬(quick sort)은 정렬 알고리즘 중 하나로, 선택 정렬(selection sort)보다 훨씬 빠르다. 퀵 정렬은 분할 정복 알고리즘을 사용한다. 퀵 정렬은 배열을 재귀적으로 분할할 때 원소를 이동하는 방법을 사용하며 분할된 하위 배열을 결합할 때 정렬을 하지는 않는다.

분할 정복의 재귀 단계에서 문제를 작게 만드는 과정은 다음과 같다. 먼저 배열에서 원소 하나를 선택한다. 이 원소를 기준 원소(pivot)라고 한다. 모든 원소를 기준 원소보다 작은 원소들과 큰 원소들로 분류한다. 이것을 분할(partitioning)이라고 한다. 분할 결과 배열은 다음과 같이 나뉘게 된다.

• 기준 원소보다 작은 숫자들로 이루어진 하위 배열
• 기준 원소
• 기준 원소보다 큰 숫자들로 이루어진 하위 배열

이때 하위 배열(sub-array)이 정렬되어 있으면 전체 배열을 정렬하는 일은 왼쪽 배열 + 기준 원소 + 오른쪽 배열과 같이 배열들을 합치는 것이며 그 결과 전체 원소들이 정렬된 배열이 된다. 하위 배열이 정렬되어 있지 않을 경우 두 개의 하위 배열에 대해서도 퀵 정렬을 수행하고, 그 결과를 합치면 전체 배열이 정렬된다.

분할 정복의 기본 단계인 정렬 시 가장 간단한 배열은 정렬할 필요가 없는 배열이다. 즉, 비어 있는 배열이나 원소가 하나인 배열이 기본 단계가 된다. 이때는 정렬할 것이 없으므로 배열을 있는 그대로 반환하면 된다. 원소가 두 개인 배열을 정렬하기 위해서는 첫 번째 원소가 두 번째 원소보다 작으면 정렬된 상태이므로 그대로 반환하면 된다. 만약 그렇지 않다면 두 원소를 교환한다. 원소가 세 개인 배열부터는 문제를 작게 나누기 위한 과정이 필요하다.

퀵 정렬의 분할 정복 과정을 정리하면 다음과 같다.

1. 분할: 문제를 작게 만든다. 기준 원소를 선택하고 배열을 기준 원소보다 작은 원소의 배열과 기준 원소보다 큰 원소의 배열, 두 개의 하위 배열로 분할한다. 배열을 더 이상 분할할 수 없을 때까지 모든 배열에 대해 재귀적으로 배열 분할 작업을 수행한다.
2. 정복: 분할된 하위 배열을 정렬한다. 기본 단계는 원소가 한 개인 배열 또는 원소가 없는 빈 배열이다.
3. 결합: 분할된 하위 배열의 정렬 결과를 병합하여 정렬된 배열을 얻는다.

빅오 표기법에 따르면 퀵 정렬의 평균 실행 시간은 O(n log n)이지만 최악의 경우에는 O(n2)이 될 수 있으며 이 경우 퀵 정렬은 선택 정렬만큼 느리다. 퀵 정렬의 성능은 선택한 기준 원소에 크게 의존한다. 평균적인 경우와 최악의 경우 실행 시간이 다른 것은 바로 어떤 기준 원소를 선택하는지에 따라 정렬 시간이 달라지기 때문이다. 만약 첫 번째 원소나 마지막 원소를 항상 기준 원소로 선택하고, 이미 정렬되어 있는 배열에 대해 퀵 정렬을 호출하면 퀵 정렬은 입력으로 주어진 배열이 이미 정렬되어 있는지, 아닌지는 확인하지 않기 때문에 그냥 정렬하려고 할 것이다. 이때 두 개의 하위 배열 중 하나는 항상 빈 배열이 된다. 따라서 호출 스택이 아주 길어진다. 이 경우는 최악의 경우이다. 예를 들어 8개의 원소를 가지는 배열에서 호출 스택의 전체 높이(크기)는 8이 된다. 반면 정 가운데 있는 원소를 항상 기준 원소로 선택한다고 가정하면 배열을 절반으로 나누므로 호출 스택은 매우 짧아지게 된다. 이 경우는 최선의 경우이다. 예를 들어 8개의 원소를 가지는 배열에서 호출 스택의 전체 높이는 4이다. 배열을 절반으로 나누기 때문에 재귀적 호출을 많이 할 필요가 없다. 기본 단계에 더 빨리 도달하기 때문에 호출 스택이 짧아진다. 가장 마지막 원소를 기준 원소로 선택하여 배열을 분할하는 것을 로무토 분할(Lomuto partitioning)이라고 한다. 다른 기준 원소 선택 방법을 사용하면 퀵 정렬의 성능을 개선할 수 있다.

최악의 경우와 최선의 경우 호출 스택의 높이와 전체 알고리즘 시간을 살펴보면 다음과 같다. 기준 원소로 원소 하나를 선택하면 나머지 원소들은 두 개의 하위 배열로 나누어진다. 이렇게 나누기 위해서는 나머지 원소들을 모두 기준 원소와 비교해야 한다. 이 작업에는 O(n)의 실행 시간이 걸린다. 호출 스택의 첫 번째 단계 뿐만 아니라 이후의 모든 호출 스택에서도 O(n)개의 원소를 비교해야 한다. 배열을 다르게 분할한다고 해도 여전히 매번 O(n)개의 원소를 모두 비교해야 하는 것은 마찬가지이다. 따라서 모든 호출 스택 작업이 완료되려면 O(n) 시간이 걸린다. 최선의 경우 O(log n)개의 단계가 되므로 호출 스택의 높이가 O(log n)이며 각각의 단계는 O(n) 시간이 걸리므로 전체 알고리즘은 O(n) × O(log n) = O(n log n) 시간이 걸린다. 최악의 경우에는 O(n)개의 단계가 되므로 호출 스택의 높이가 O(n)이며 전체 알고리즘은 O(n) × O(n) = O(n2) 시간이 걸린다. 퀵 정렬에서는 일반적인 경우에도 최선의 경우와 같은 실행 속도를 가진다. 만약 기준 원소를 전체 배열에서 무작위로 선택한다면 퀵 정렬은 평균적으로 O(n log n) 실행 시간을 가지게 된다.

알고리즘에서 제자리(in-place) 알고리즘이란 자료 구조를 추가로 사용하지 않고(아예 사용하지 않는 것은 아니며 무시할 만한 정도의 추가 공간을 사용) 입력을 변환하는 것을 말한다. 정렬 알고리즘에서 제자리 알고리즘을 사용하는 정렬을 제자리 정렬(in-place sort)이라고 한다. 퀵 정렬의 일반적인 구현은 제자리 정렬이므로 입력에 따라 추가적인 메모리를 사용하지 않는다. 기준 원소를 선택한 후 기준 원소 보다 작은 원소를 큰 원소와 단순히 교환(swap)한다. 단, 재귀 호출을 사용하므로 메모리의 스택 영역이 사용되며 알고리즘의 공간 복잡도는 재귀 호출의 호출 스택 높이에 비례한다. 최선의 경우 재귀 트리(recursion tree)의 최대 높이(height)는 1 + log n이며 O(log n)개의 재귀 호출을 수행하므로 공간 복잡도는 O(log n)이다. 최악의 경우에는 O(n)개의 재귀 호출을 수행하며 공간 복잡도는 O(n)이 된다.

정렬 알고리즘에서 동일한 원소에 대해 입력 배열에서의 상대적인 순서가 출력 배열에서의 상대적인 순서와 동일하면 해당 알고리즘은 안정적(stable)이라고 한다. 퀵 정렬은 동일한 두 원소의 위치가 변경될 수 있으므로 불안정한(unstable) 정렬 알고리즘이다.

병합 정렬

병합 정렬(merge sort)은 퀵 정렬과 같이 분할 정복 알고리즘을 사용하는 정렬 알고리즘이다. 퀵 정렬에서는 기준 원소를 선택하고 이를 기준으로 배열을 두 개의 하위 배열로 나누지만 병합 정렬은 배열을 단순히 반으로(기준 원소는 배열의 중간 원소이다) 나누어 두 개의 하위 배열로 나눈다. 병합 정렬은 퀵 정렬과 달리 배열을 재귀적으로 분할할 때 원소를 이동하지는 않으며 분할된 하위 배열을 결합할 때 정렬을 수행한다.

병합 정렬의 분할 정복 과정은 다음과 같다.

1. 분할: 문제를 작게 만든다. 배열을 반으로 나누어 두 개의 하위 배열로 만든다. 배열을 더 이상 분할할 수 없을 때까지 모든 배열에 대해 재귀적으로 배열 분할 작업을 수행한다.
2. 정복: 분할된 하위 배열을 정렬한다. 기본 단계는 원소가 한 개인 배열 또는 원소가 없는 빈 배열이다.
3. 결합: 분할된 하위 배열의 정렬 결과를 병합하여 정렬된 배열을 얻는다.

병합 정렬에서는 정렬되지 않은 배열을 하위 배열의 크기가 1이 될 때까지 재귀적으로 두 개의 하위 배열로 나눈다. 길이가 1인 두 하위 배열을 합칠 때 정렬한다. 나머지 하위 배열에 대해서도 재귀적으로 병합 정렬을 수행하고, 그 결과를 합치면 전체 배열이 정렬된다.

빅오 표기법에 따르면 병합 정렬의 평균 실행 시간은 O(n log n)이며 최악의 경우에도 O(n log n)이다.

병합 정렬의 일반적인 구현은 제자리 정렬이 아니며 따라서 입력에 따라 추가적인 메모리를 사용한다. 하위 배열들을 결합할 때 정렬한 결과를 저장할 임시 배열이 필요하다. 병합 정렬은 재귀 호출을 사용하므로 메모리의 스택 영역이 사용된다. 이때 재귀 트리의 최대 높이는 1 + log n이다. 따라서 재귀 함수 호출에 대한 스택 메모리의 공간 복잡도는 O(log n)이다. 재귀적으로 두 개의 하위 배열을 생성하므로 각 재귀 호출 별로 2 * n/2, 2 * n/4, 2 * n/8, … 크기의 배열을 임시로 생성해야 하며 총 배열의 크기는 2n으로 수렴한다. 재귀 호출이 완료되면 해당 호출에서 생성한 임시 배열이 제거된다. 그러나 재귀 호출을 병렬화하지 않는다면 첫 재귀 호출에서 두 개의 하위 배열 중 하나의 하위 배열에 대해서만 재귀 호출이 수행되며 따라서 n개의 원소를 위한 메모리 공간이 필요하므로 공간 복잡도는 O(n)이다. 병합 정렬을 제자리 정렬로 구현할 수 있으며 이 경우 공간 복잡도는 O(1)로 감소하게 된다.

병합 정렬은 동일한 두 원소의 위치가 변경되지 않으며 따라서 안정적인 정렬 알고리즘이다.

퀵 정렬과 병합 정렬

병합 정렬의 평균 빅오 실행 시간과 최악의 경우 빅오 실행 시간은 모두 O(n log n)이지만 퀵 정렬의 경우 평균 O(n log n), 최악의 경우 O(n2)이다. 하지만 모든 경우에 대해 병합 정렬이 퀵 정렬보다 항상 빠른 것은 아니다. 이는 알고리즘이 소비하는 특정 시간인 상수 시간(constant time)을 고려해야 하는 경우 때문이다.

두 개의 알고리즘이 서로 다른 빅오 실행 시간을 가진다면 상수는 크게 문제가 되지 않기 때문에 이런 상수들은 보통 무시한다. 퀵 정렬은 병합 정렬보다 더 작은 상수를 가지므로 실행 시간이 O(n log n)으로 동일하다면 퀵 정렬이 더 빠르다. 퀵 정렬을 사용할 때 최악의 경우보다는 일반적인 경우가 훨씬 많이 발생하기 때문에 현실에서는 퀵 정렬이 더 빠르다.

병합 정렬은 입력값에 관계 없이 항상 일정한 성능을 보여주는 반면 퀵 정렬은 입력값에 따라 성능의 편차가 존재한다.

참고

• 그림으로 이해하는 알고리즘 - 아디트야 바르가바 저/김도형 역
• https://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html