배열 역전(Inversion) 개수 계산 – 병합 정렬로 O(n log n)에 구하기

배열의 역전(inversion)은 배열을 정렬된 상태로 만들 때 필요한 변경(교환) 횟수를 나타내는 지표입니다. 배열이 이미 정렬되어 있다면 역전 개수는 0이며, 반대로 배열이 완전히 역순으로 되어 있을 때 역전 개수는 최대가 됩니다.

이 문제는 단순히 모든 쌍을 비교하는 O(n²) 방식 대신, 병합 정렬(Merge Sort)을 활용한 분할 정복(Divide and Conquer) 기법으로 접근하면 O(n log n)의 시간 복잡도로 훨씬 효율적으로 해결할 수 있습니다.

역전(Inversion)이란?

역전은 배열에서 앞선 위치의 원소가 뒤에 있는 원소보다 큰 쌍(pair)을 의미합니다. 예를 들어 배열 (1, 5, 6, 4, 20)에서는 (5, 4)와 (6, 4)라는 두 쌍이 순서에 어긋나 있으므로 역전 개수는 2입니다. 역전 개수가 많을수록 배열이 정렬 상태에서 멀리 떨어져 있다고 해석할 수 있습니다.

입력과 출력

입력:
수열 (1, 5, 6, 4, 20)

출력:
오름차순으로 정렬하는 데 필요한 역전의 개수
여기서 역전 개수는 2입니다.
첫 번째 역전: (5, 4)
두 번째 역전: (6, 4)

알고리즘

핵심 아이디어는 병합 정렬 과정에서 두 부분 배열을 병합할 때, 오른쪽 부분 배열의 원소가 먼저 선택되면 왼쪽 부분 배열에 남아 있는 모든 원소들과 역전 관계가 된다는 점입니다. 따라서 병합 함수 안에서 count += (mid - i)를 통해 역전 개수를 누적하면 전체 역전 개수를 구할 수 있습니다.

merge(array, tempArray, left, mid, right)

입력: 병합할 두 부분 배열과 left, mid, right 인덱스

출력: 정렬된 순서로 병합된 배열과 해당 병합 단계에서 발생한 역전 개수

Begin
   i := left, j := mid, k := left
   count := 0
   while i <= mid - 1 and j <= right do
      if array[i] <= array[j] then
         tempArray[k] := array[i]
         i := i + 1, k := k + 1
      else
         tempArray[k] := array[j]
         j := j + 1, k := k + 1
         count := count + (mid - i)  // 왼쪽에 남은 원소 수만큼 역전 발생
      end if
   done

   // 왼쪽 부분에 남은 요소 처리
   while i <= mid - 1 do
      tempArray[k] := array[i]
      i := i + 1, k := k + 1
   done

   // 오른쪽 부분에 남은 요소 처리
   while j <= right do
      tempArray[k] := array[j]
      j := j + 1, k := k + 1
   done

   return count
End

mergeSort(array, tempArray, left, right)

입력: 원본 배열과 임시 배열, 그리고 배열의 left, right 인덱스

출력: 정렬 과정에서 누적된 전체 역전 개수

Begin
   count := 0
   if right > left then
      mid := (left + right) / 2  // 중간 인덱스 계산
      count := mergeSort(array, tempArray, left, mid)  // 왼쪽 부분 정렬
      count := count + mergeSort(array, tempArray, mid + 1, right)  // 오른쪽 부분 정렬
      count := count + merge(array, tempArray, left, mid + 1, right)  // 두 부분 병합
   end if
   return count
End

C++ 구현 예제

#include <iostream>
using namespace std;

int merge(int arr[], int temp[], int left, int mid, int right) {
   int i, j, k;
   int count = 0;

   i = left;    // 왼쪽 부분 배열의 위치를 가리키는 인덱스
   j = mid;     // 오른쪽 부분 배열의 위치를 가리키는 인덱스
   k = left;    // 병합 결과를 저장할 위치를 가리키는 인덱스

   while ((i <= mid - 1) && (j <= right)) {
      if (arr[i] <= arr[j]) {   // 왼쪽 요소가 더 작거나 같은 경우
         temp[k++] = arr[i++];
      } else {
         temp[k++] = arr[j++];
         count += (mid - i);   // 발생한 역전 개수를 누적
      }
   }

   while (i <= mid - 1)   // 왼쪽 리스트에 남은 요소 추가
      temp[k++] = arr[i++];

   while (j <= right)     // 오른쪽 리스트에 남은 요소 추가
      temp[k++] = arr[j++];

   for (i = left; i <= right; i++)
      arr[i] = temp[i];   // 임시 배열의 내용을 원본 배열에 복사

   return count;
}

int mergeSort(int arr[], int temp[], int left, int right) {
   int mid, count = 0;

   if (right > left) {
      mid = (right + left) / 2;                  // 배열의 중간 인덱스 계산
      count  = mergeSort(arr, temp, left, mid);      // 왼쪽 부분 배열 병합 정렬
      count += mergeSort(arr, temp, mid + 1, right);  // 오른쪽 부분 배열 병합 정렬

      count += merge(arr, temp, left, mid + 1, right);  // 두 부분 배열을 병합하며 역전 개수 누적
   }
   return count;
}

int arrInversion(int arr[], int n) {
   int temp[n];
   return mergeSort(arr, temp, 0, n - 1);
}

int main() {
   int arr[] = {1, 5, 6, 4, 20};
   int n = 5;
   cout << "Number of inversions are " << arrInversion(arr, n);
}

실행 결과

Number of inversions are 2

시간 복잡도

모든 쌍을 일일이 비교하는 무식한(brute force) 방식은 O(n²)의 시간이 걸리지만, 위와 같이 병합 정렬 기반의 분할 정복 접근법을 사용하면 O(n log n)의 시간 복잡도로 역전 개수를 계산할 수 있습니다. 공간 복잡도는 병합 과정에서 임시 배열을 사용하므로 O(n)입니다. 덕분에 배열의 크기가 클 때도 효율적으로 역전 개수를 구할 수 있습니다.