Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ STL Set을 활용한 반전(Inversion) 개수 계산 방법

이 튜토리얼에서는 C++ STL의 set(multiset)을 사용하여 배열의 반전(inversion) 개수를 계산하는 프로그램을 다룹니다.

반전 개수(Inversion Count)란?

반전 개수는 배열이 완전히 정렬된 상태에 얼마나 가까운지를 나타내는 척도입니다. 배열이 이미 정렬되어 있다면 반전 개수는 0이 됩니다. 반대로 반전 개수가 클수록 배열은 정렬 상태에서 멀어진 것입니다.

구체적으로, 인덱스 i < j인 두 원소 arr[i]와 arr[j]에 대해 arr[i] > arr[j]인 경우를 하나의 반전이라고 정의합니다.

C++ STL Set을 이용한 구현

multiset과 upper_bound() 함수를 활용하면 각 원소를 삽입할 때마다, 그동안 삽입된 원소 중 현재 값보다 큰 원소의 개수를 효율적으로 세어 반전 개수를 누적할 수 있습니다.

#include<bits/stdc++.h>
using namespace std;
// 반전 개수 반환
int get_Icount(int arr[], int n){
    multiset<int> set1;
    set1.insert(arr[0]);
    int invcount = 0; // 결과 초기화
    multiset<int>::iterator itset1;
    for (int i=1; i<n; i++){
        set1.insert(arr[i]);
        itset1 = set1.upper_bound(arr[i]);
        invcount += distance(itset1, set1.end());
    }
    return invcount;
}
int main()
{
    int arr[] = {8, 4, 2, 1};
    int n = sizeof(arr)/sizeof(int);
    cout << "Number of inversions count are : "<< get_Icount(arr,n);
    return 0;
}

코드 설명

  1. 첫 번째 원소를 multiset에 삽입합니다.
  2. 이후 각 원소에 대해 upper_bound()를 호출하여 해당 값보다 큰 첫 번째 원소의 위치를 찾습니다.
  3. 그 위치부터 set의 끝까지의 거리(distance)를 더하면, 앞서 등장했으면서 현재 원소보다 큰 값을 가진 원소의 개수, 즉 반전의 수가 됩니다.

실행 결과

Number of inversions count are : 6

예제 배열 {8, 4, 2, 1}은 내림차순으로 정렬되어 있어 모든 원소 쌍(n×(n−1)/2 = 4×3/2 = 6)이 반전에 해당하므로 결과는 6이 됩니다.

시간 복잡도

multiset의 삽입과 upper_bound() 연산은 각각 O(log n)의 시간이 걸리므로, 전체 알고리즘의 시간 복잡도는 O(n log n)입니다. 이는 이중 루프를 사용하는 일반적인 O(n²) 방식보다 훨씬 효율적이며, 특히 원소 수가 많은 배열에서 그 차이가 두드러집니다.