티스토리 뷰
필요한 배경지식
- 세그먼트 트리
Inversion Counting
Inversion은 다음과 같이 정의됩니다.
길이가 N인 배열 A[1], A[2], ..., A[N]이 주어질때, $ i < j $ 이고 $ A[i] > A[j] $를 만족할때 $A[i]$와 $A[j]$는 Inversion관계이다.
Inversion Counting은 위에서 설명한 Inversion관계의 총 개수를 찾는 문제 입니다.
배열이 정렬이 되어 있을때는 Inversion Counting이 0이 되지만 역순으로 정렬되어 있다면 최대가 됩니다.
Inversion쌍을 구하기 위한 방법으로 완전탐색을 생각해보면 \( O(N^{2}) \)의 시간복잡도로 모든 쌍을 비교해 볼 수 있지만 대부분의 문제에서 시간안에 해결할 수 없습니다.
이 문제를 해결하는데 2가지 방법이 잘 알려져 있는데 merge sort를 이용하는 방법과 세그먼트 트리를 이용하는 방법입니다.
이 글에서는 둘 중 세그먼트 트리를 이용하는 방법을 알아보겠습니다.
예를 들어 다음과 같은 배열이 있습니다.
$A$ = {4, 2, 7, 1, 5, 6, 3}
먼저 배열$A$의 수들을 오름차순으로 정렬해야 할때, Inversion관계에 있는 쌍을 첫번째 수부터 차례대로 확인해 보기 위해서 배열 $A$에 포함된 수 $K$를 순서대로 새로 추가하면서 그때의 Inversion counting을 $count$에 나타내 보겠습니다.
1. $A$ = {4} , $count$ = 0
2. $A$ = {4, 2} , $count$ = 1 $\rightarrow$ 새로운 Inversion쌍 : (4-2)
3. $A$ = {4, 2, 7} , $count$ = 1
4. $A$ = {4, 2, 7, 1} , $count$ = 4 $\rightarrow$ 새로운 Inversion쌍 : (4-1) , (2-1) , (7-1)
5. $A$ = {4, 2, 7, 1, 5} , $count$ = 5 $\rightarrow$ 새로운 Inversion쌍 : (7-5)
6. $A$ = {4, 2, 7, 1, 5, 6} , $count$ = 6 $\rightarrow$ 새로운 Inversion쌍 : (7-6)
7. $A$ = {4, 2, 7, 1, 5, 6, 3} , $count$ = 10 $\rightarrow$ 새로운 Inversion쌍 : (4-3) , (7-3) , (5-3) , (6-3)
위의 결과에서 알 수 있는 사실은 새로운 수 $K$가 $A$에 추가될 때, 새로운 Inversion쌍의 개수는 $K$앞에 있는 수들 중 $K$보다 큰 수의 개수라는 것을 알 수 있습니다. 여기서 K보다 큰 수의 개수는 세그먼트 트리의 구간합을 이용하여 구해낼 수 있습니다.
배열$A$에 수$K$가 추가되어 있는지 나타낼 배열을 아래와 같이 표로 나타냈습니다.
4가 처음으로 추가된 후 배열의 상태입니다.
이미 추가된 수 중에서 4보다 큰 수는 없으므로 $count$ = 0 임을 알 수 있습니다.
2가 추가되었습니다. 2보다 큰 수의 개수를 알아내기 위해서는 [3,7]의 구간합을 구해야 합니다.
[3,7]의 구간합은 1이므로 $count$ = 1 이 되었습니다.
다음으로 7이 추가되었지만 7보다 큰 수는 없으므로 $count$ = 1 으로 유지됩니다.
1이 추가되었고 [2,7]의 현재 구간합은 3이므로 $count$ = 4가 됩니다.
5가 추가 되었고 [6,7]의 구간합은 1이므로 $count$ = 5가 됩니다.
6이 추가 되었고 [7,7]의 구간합은 1이므로 $count$ = 6이 됩니다.
마지막으로 3이 추가 되었고 [4,7]의 구간합은 4이므로 $count$ = 10이 되고
Inversion쌍의 총 개수를 구해낼 수 있습니다.
배열이 N개의 수를 가질때 세그먼트 트리를 이용하여 구간합을 구하면 \( O(lgN) \)만큼의 시간복잡도가 필요하고 이를 N번 반복해야 하므로 총 \( O(NlgN) \)의 시간복잡도로 문제를 해결할 수 있습니다.
연습문제