주어진 배열을 정렬하는 과정에서 발생하는 반전(inversion)의 총 횟수를 반전 개수(Inversion Count)라고 합니다. 반전 문제는 고전적인 알고리즘 문제로, 병합 정렬(Merge Sort) 알고리즘을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 원소보다 왼쪽에 위치하면서 더 큰 값을 가진 원소의 개수를 모두 세어 결과에 더하는 것이며, 이 로직은 병합 정렬의 merge(병합) 함수 내부에서 처리됩니다.
내용을 더 잘 이해하기 위해 병합 과정에 포함된 두 개의 부분 배열을 예로 들어 살펴보겠습니다.
입력: arr[] = { 1, 9, 6, 4, 5}
출력: Inversion count is 5반전 개수(Inversion Count)란?
배열이 주어졌을 때 해당 배열의 반전 개수를 찾는 것이 목표입니다. 인덱스 i와 j에 대해 (i < j)이면서 동시에 (A[i] > A[j])인 경우, 쌍 (i, j)를 배열 A의 반전이라고 정의합니다. 즉, 배열 안에서 이러한 조건을 만족하는 모든 쌍의 개수를 세면 됩니다.
예를 들어 위 배열에는 다음과 같이 5개의 반전이 존재합니다.
(9,6), (9,4), (9,5), (6,4), (6,5)
알고리즘 접근 방식
- 배열의 원소 값들을 서로 비교합니다.
- 낮은 인덱스에 있는 값이 더 클 경우 카운터를 1씩 증가시킵니다.
- 최종 결과를 출력합니다.
단순 이중 반복문으로 구현하면 시간 복잡도가 O(n²)이 되지만, 병합 정렬을 응용하면 O(n log n)의 시간 복잡도로 문제를 해결할 수 있습니다.
C 언어 구현 예제
#include <stdio.h>
int Merge(int arr[], int aux[], int low, int mid, int high) {
int k = low, i = low, j = mid + 1;
int inversionCount = 0;
while (i <= mid && j <= high) {
if (arr[i] <= arr[j]) {
aux[k++] = arr[i++];
} else {
aux[k++] = arr[j++];
inversionCount += (mid - i + 1); // NOTE
}
}
while (i <= mid)
aux[k++] = arr[i++];
for (int i = low; i <= high; i++)
arr[i] = aux[i];
return inversionCount;
}
int MergeSort(int arr[], int aux[], int low, int high) {
if (high == low) // if run size == 1
return 0;
int mid = (low + ((high - low) >> 1));
int inversionCount = 0;
inversionCount += MergeSort(arr, aux, low, mid);
inversionCount += MergeSort(arr, aux, mid + 1, high);
inversionCount += Merge(arr, aux, low, mid, high);
return inversionCount;
}
int main() {
int arr[] = { 1, 9, 6, 4, 5 };
int N = 5;
int aux[N];
for (int i = 0; i < N; i++)
aux[i] = arr[i];
printf("Inversion count is %d", MergeSort(arr, aux, 0, N - 1));
return 0;
}코드 동작 원리
위 코드에서 Merge 함수는 두 부분 배열을 병합하는 과정에서, 오른쪽 부분 배열의 원소가 왼쪽 부분 배열의 원소보다 작을 때마다 (mid - i + 1)만큼 반전 개수를 더합니다. 이는 왼쪽 부분 배열은 이미 정렬된 상태이므로, 현재 위치 i부터 mid까지의 모든 원소가 해당 오른쪽 원소보다 크다는 것을 의미하기 때문입니다. MergeSort 함수는 배열을 재귀적으로 분할한 뒤 각 단계에서 발생한 반전 개수를 누적하여 최종 결과를 반환합니다.