Inversion Counting

Inversion Counting

배열 $A$가 주어졌을때, $i\lt j$이면서 $A[i]\gt A[j]$를 만족할 때를 Inversion이라고 부른다.

Inversion Counting 은 이 Inversion의 개수를 세는 문제이다.

단순하게 생각해보면 이중 반복문을 통해 $O(N^2)$의 시간복잡도로 이 문제를 해결할 수 있을 것이다.

void getInversion {
	for (int i = 0; i < n; i++) {
    	for (int j = i + 1; j < n; j++) {
        	if (A[i] > A[j]) {
            	cout << "Inversion: << A[i] << ' ' << A[j] << "\n";
                inversion_cnt += 1
            }
        }
    }
}

하지만 이보다 빠른 방법이 존재하는데, Merge Sort혹은 Segment Tree를 응용하는 방법이다.

아래 두 사이트에 Inversion 의 개수를 세는 문제가 있다.

• swexpert 15999. Inversion Counting (교육용)
• BOJ 10090번 Counting Inversions

Merge Sort 로 Inversion Counting 구하기

Merge Sort의 구현 방식과 작동 원리에 대한 이해가 필요합니다.

void merge(int s, int mid, int e) {
    int l = s, r = mid + 1;
    int idx = s;
    while (l <= mid || r <= e) {
        if (r > e || (l <= mid && A[l] < A[r])) 
        	tmp[idx++] = A[l++];
        else {
        	inversion_cnt += mid - left + 1;
        	tmp[idx++] = A[r++];
    	}
    }
    for (int i = s; i <= e; i++) A[i] = tmp[i];
}
void mergeSort(int s, int e) {
    if (s < e) {
        int mid = s + e >> 1;
        mergeSort(s, mid);
        mergeSort(mid + 1, e);
        merge(s, mid, e);
    }
}

Merge Sort는 $O(NlogN)$에 돌아가기 때문에 Inversion Counting 또한, 해당 시간복잡도를 따라간다.

작동 원리는 아래와 같다.

Merge Sort는 배열을 절반씩 쪼갠 후 다시 합쳐나가는 과정을 통해 정렬을 진행한다. 다시 합칠 때, 합치는 두 배열을 $L$, $R$ 이라고 하자.

$L$, $R$ 은 정렬되어 있는 상태라는 것을 Merge Sort를 공부한 적이 있다면 알 수 있다.

$L$, $R$을 합치는 과정에서 $L[i]\gt R[j]$라고 가정하자. 그렇다면 $k\ge i$인 $L[k]$에 대해 $L[k]\gt R[j]$이다. 말로 풀어 설명하자면, 왼쪽에서 한 원소와 오른쪽에서 한 원소를 비교 했을 때, 왼쪽의 원소가 더 크다면 왼쪽의 그 뒤의 원소들은 해당 오른쪽의 원소보다 크다는 것이다.

즉, 교환을 진행할 때 뒤의 원소들과 교차점이 생기게 된다. 해당 교차점의 수가 Inversion의 개수가 된다.

위의 inversion_cnt += mid - left + 1; 부분이 생기는 교차점의 수를 의미한다.

Segment Tree 로 Inversion Counting 구하기

나는 Merge Sort보다 Segment Tree가 이해를 돕는데는 더 직관적이라고 본다.

세그먼트 트리에서는 구간합을 이용한다. 세그먼트 트리에 대해 어느 정도 이해가 있는 사람이라면 이 문장을 보고 풀이를 떠올렸을지도 모르겠다.

세그먼트 트리의 노드의 의미는 $X$의 개수이다.

배열이 $A$가 주어졌을때, 앞의 원소부터 차례대로 세그먼트 트리에 집어넣는다. 집어넣으면서 해당 수보다 큰 수들의 개수를 구하면 해당 수가 가지는 Inversion의 개수를 구할 수 있다. 즉, $[x + 1, N]$까지의 구간합을 쿼리로 불러주면서 반환값을 계속해서 더해나가면 될 것이다.

이 방식 또한 $O(NlogN)$에 해결 가능하다.

그러나 들어오는 수의 범위에 따라 좌표 압축을 진행해야 하므로 조금 번거로운 면이 있다. 그래서 대부분 Merge Sort를 응용한 풀이를 소개하는 것 같다.