C++로 배열의 인버전(Inversion) 개수 구하기

인버전(Inversion)이란 배열을 오름차순으로 정렬하기 위해 필요한 원소 간 교환 횟수를 의미합니다. 배열이 이미 정렬되어 있다면 인버전 개수는 0이 되고, 반대로 배열이 역순(내림차순)으로 정렬되어 있다면 인버전 개수는 최댓값을 가지게 됩니다.

예를 들어 배열에서 앞에 있는 원소가 뒤에 있는 원소보다 큰 경우를 하나의 인버전으로 계산하며, 이러한 쌍의 총 개수가 곧 인버전 카운트입니다.

이번 글에서는 C++ 프로그램을 작성하여 배열 내 인버전 개수를 계산하는 방법을 알아보겠습니다.

알고리즘

가장 기본적인 방법은 이중 반복문을 사용하여 모든 원소 쌍을 비교하는 것입니다. 시간 복잡도는 O(n²)입니다.

시작
    함수 CountInversionArray(a[], n = 원소의 개수)
    카운터 c := 0 으로 초기화
    i를 0부터 n-1까지 반복:
        j를 (i + 1)부터 n까지 반복:
            만약 a[i] > a[j]라면
                카운트를 1 증가
    종료

예제 코드

#include<iostream>
using namespace std;
int CountInversionArray(int a[], int n) {
    int i, j, c = 0;
    for(i = 0; i < n; i++) {
        for(j = i+1; j < n; j++)
            if(a[i] > a[j])
                c++;
    }
    return c;
}
int main() {
    int n, i;
    cout<<"\nEnter the number of elements: ";
    cin>>n;
    int a[n];
    for(i = 0; i < n; i++) {
        cout<<"Enter element "<<i+1<<": ";
        cin>>a[i];
    }
    cout<<"\nThe number of inversion in the array: "<<CountInversionArray(a, n);
    return 0;
}

실행 결과

Enter the number of elements: 5
Enter element 1: 3
Enter element 2: 2
Enter element 3: 7
Enter element 4: 6
Enter element 5: 1

The number of inversion in the array: 6

동작 원리 설명

위 예제에서 입력된 배열은 {3, 2, 7, 6, 1}입니다. 인버전 쌍은 다음과 같이 6개가 존재합니다.

• (3, 2)
• (3, 1)
• (2, 1)
• (7, 6)
• (7, 1)
• (6, 1)

각 쌍에서 앞의 원소가 뒤의 원소보다 크므로, 총 인버전 개수는 6이 됩니다.

참고: 더 효율적인 방법

위 방법은 O(n²)의 시간 복잡도를 가지므로 배열의 크기가 클 경우 비효율적일 수 있습니다. 병합 정렬(Merge Sort)을 활용하면 분할 과정에서 인버전을 함께 계산하여 O(n log n)의 시간 복잡도로 문제를 해결할 수 있습니다.