[알고리즘] 분할 정복과 정렬
분할 정복 알고리즘
분할 정복(divide-and-conquer) 알고리즘이란 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 분할 정복 알고리즘은 재귀적(recursive) 알고리즘을 사용한다. 문제를 동일하거나 관련된 유형의 두 개 이상의 하위 문제로 재귀적으로 분할한 다음 하위 문제에 대한 결과를 결합하여 원래 문제에 대한 결과를 얻는다. 분할 정복 알고리즘을 사용하는 예로는 퀵 정렬, 병합 정렬, 고속 푸리에 변환 등이 있다.
분할 정복 알고리즘은 재귀 호출을 사용하므로 함수 호출 시 콜 스택(call stack)의 스택 프레임이 스택 구조에서 처리되는 과정에서 오버헤드가 발생할 수 있다. 또한 재귀 스택에 할당된 메모리가 충분해야 하며 그렇지 않으면 스택 오버플로우(stack overflow)로 인해 실행이 실패할 수 있다. 시간 효율적인 분할 정복 알고리즘은 작은 재귀 깊이(recursion depth)를 가진다.
분할 정복 알고리즘을 통한 문제 해결은 크게 두 과정으로 나눌 수 있다.
- 가장 간단한 경우인 기본 단계를 찾는다. 기본 단계는 가능한한 가장 간단한 문제이어야 한다.
- 주어진 문제를 작게 줄여서 기본 단계가 되도록 만드는 법을 찾는다. 재귀 함수를 호출할 때마다 문제를 작게 나누어야 한다. 예를 들어, 재귀 함수 호출을 할 때마다 호출 대상이 되는 배열의 크기가 점점 감소해야 한다. 이때 재귀 함수 호출은 모든 기본 단계를 만나기 전까지 완료되지 않는다. 재귀에서는 부분적으로 실행된 함수 호출의 상태를 모두 저장한다.
퀵 정렬
퀵 정렬(quick sort)은 정렬 알고리즘 중 하나로, 선택 정렬보다 훨씬 빠르다. 퀵 정렬은 분할 정복 알고리즘을 사용한다. 퀵 정렬에서 분할 정복의 기본 단계인 정렬 시 가장 간단한 배열은 정렬할 필요가 없는 배열이다. 즉, 비어 있는 배열이나 원소가 하나인 배열이 기본 단계가 된다. 이때는 정렬할 것이 없으므로 배열을 있는 그대로 반환하면 된다. 원소가 두 개인 배열을 정렬하기 위해서는 첫 번째 원소가 두 번째 원소보다 작으면 정렬된 상태이므로 그대로 반환하면 된다. 만약 그렇지 않다면 두 원소를 교환한다. 원소가 세 개인 배열부터는 문제를 작게 나누기 위한 과정이 필요하다.
퀵 정렬의 분할 정복 과정은 다음과 같다.
- 기본 단계: 원소가 한 개인 배열 또는 원소가 없는 빈 배열 정렬하기
- 재귀 단계: 문제를 작게 만들기
재귀 단계에서 문제를 작게 만드는 만드는 과정은 다음과 같다. 먼저 배열에서 원소 하나를 선택한다. 이 원소를 기준 원소(pivot)라고 한다. 모든 원소를 기준 원소보다 작은 원소들과 큰 원소들로 분류한다. 이것을 분할(partitioning)이라고 한다. 분할 결과 배열은 다음과 같이 나뉘게 된다.
- 기준 원소보다 작은 숫자들로 이루어진 하위 배열
- 기준 원소
- 기준 원소보다 큰 숫자들로 이루어진 하위 배열
이때 하위 배열(sub-array)이 정렬되어 있으면 전체 배열을 정렬하는 일은 왼쪽 배열 + 기준 원소 + 오른쪽 배열과 같이 배열들을 합치는 것이며 그 결과 전체 원소들이 정렬된 배열이 된다. 하위 배열이 정렬되어 있지 않을 경우 두 개의 하위 배열에 대해서도 퀵 정렬을 호출하고, 그 결과를 합치면 전체 배열이 정렬된다. 하위 배열이 원소가 한 개인 배열 또는 원소가 없는 빈 배열이면 기본 단계에 해당된다.
퀵 정렬의 순서를 정리하면 다음과 같다.
- 기준 원소를 선택한다.
- 배열을 기준 원소보다 작은 원소의 배열과 기준 원소보다 큰 원소의 배열, 두 개의 하위 배열로 분할한다.
- 하위 배열에 대해 재귀적으로 퀵 정렬을 수행한다. 어떤 기준 원소를 고르든 두 개의 하위 배열에 재귀적으로 퀵 정렬을 수행하면 된다. 각 하위 배열들이 정렬되고 나서 합치면 전체 배열이 정렬된다.
빅오 표기법에 따르면 퀵 정렬의 평균 실행 시간은 O(n log n)이지만 최악의 경우에는 O(n^2)이 될 수 있으며 이 경우 퀵 정렬은 선택 정렬만큼 느리다. 병합 정렬의 경우 빅오 실행 시간이 O(n log n)이다. 하지만 모든 경우에 대해 병합 정렬이 퀵 정렬보다 항상 빠른 것은 아니다. 이는 알고리즘이 소비하는 특정 시간인 상수 시간(constant time)을 고려해야 하는 경우 때문이다. 두 개의 알고리즘이 서로 다른 빅오 실행 시간을 가진다면 상수는 크게 문제가 되지 않기 때문에 이런 상수들은 보통 무시한다. 퀵 정렬은 병합 정렬보다 더 작은 상수를 가지므로 실행 시간이 O(n log n)으로 동일하다면 퀵 정렬이 더 빠르다. 퀵 정렬을 사용할 때 최악의 경우보다는 일반적인 경우가 훨씬 많이 발생하기 때문에 현실에서는 퀵 정렬이 더 빠르다.
퀵 정렬의 성능은 선택한 기준 원소에 크게 의존한다. 평균적인 경우와 최악의 경우 실행 시간이 다른 것은 바로 어떤 기준 원소를 선택하는지에 따라 정렬 시간이 달라지기 때문이다. 만약 첫 번째 원소를 항상 기준 원소로 선택하고, 이미 정렬되어 있는 배열에 대해 퀵 정렬을 호출하면 퀵 정렬은 입력으로 주어진 배열이 이미 정렬되어 있는지, 아닌지는 확인하지 않기 때문에 그냥 정렬하려고 할 것이다. 두 개의 하위 배열 중 하나는 항상 빈 배열이 된다. 따라서 호출 스택이 아주 길어진다. 이 경우는 최악의 경우이다. 예를 들어 8개의 원소를 가지는 배열에서 호출 스택의 전체 높이(크기)는 8이 된다. 정 가운데 있는 원소를 항상 기준 원소로 선택한다고 가정하면 배열을 절반으로 나누므로 호출 스택은 매우 짧아지게 된다. 이 경우는 최선의 경우이다. 예를 들어 8개의 원소를 가지는 배열에서 호출 스택의 전체 높이는 4이다. 배열을 절반으로 나누기 때문에 재귀적 호출을 많이 할 필요가 없다. 기본 단계에 더 빨리 도달하기 때문에 호출 스택이 짧아진다.
최악의 경우와 최선의 경우 호출 스택의 높이와 전체 알고리즘 시간을 살펴보면 다음과 같다. 기준 원소로 원소 하나를 선택하면 나머지 원소들은 두 개의 하위 배열로 나누어진다. 이렇게 나누기 위해서는 나머지 원소들을 모두 기준 원소와 비교해야 한다. 이 작업에는 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(n^2) 시간이 걸린다. 퀵 정렬에서는 일반적인 경우에도 최선의 경우와 같은 실행 속도를 가진다. 만약 기준 원소를 전체 배열에서 무작위로 선택한다면 퀵 정렬은 평균적으로 O(n log n) 실행 시간을 가지게 된다.
참고
- 그림으로 이해하는 알고리즘 - 아디트야 바르가바 저/김도형 역
Comments