Inversion Counting 알고리즘
Inversion Counting 이란?
Inversion Counting 이란 역순으로 되어 있는 순서쌍의 개수를 세는 유명한 알고리즘 입니다. 쉽게 예를 들면 아래와 같은 숫자가 있습니다.
3 2 5 4 1
이렇게 5개의 숫자가 있습니다. 하나씩 비교해보면 (3, 2)는 3이 더 크기 때문에 역순으로 되어 있습니다. (3, 5)는 역순이 아닙니다. (3, 4) 역시 역순이 아닙니다. (3, 1)은 역순으로 되어 있습니다. 이런식으로 모든 순서쌍을 비교해보면 아래와 같은 순서쌍을 찾을 수 있습니다.
(3, 2), (3, 1), (2, 1), (5, 4), (5, 1), (4, 1)
이렇게 6개의 순서쌍을 찾을 수 있습니다. 이것은 버블 정렬을 진행할 때 몇 번이나 교환을 진행하는지의 숫자와 같습니다. 즉 위의 숫자를 버블 정렬로 정렬할 때 교환이 총 6번 일어나게 됩니다.
(3, 2, 5, 4, 1) → (2, 3, 5, 4, 1) → (2, 3, 4, 5, 1) → (2, 3, 4, 1, 5) → (2, 3, 1, 4, 5) → (2, 1, 3, 4, 5) → (1, 2, 3, 4, 5)
위와 같이 버블정렬이 진행되며 첫 번째 원래 리스트를 제외하고 총 6번의 교환이 일어납니다.
Inversion Counting은 Merge Sort와 Segment Tree 두가지 방법으로 풀 수 있습니다. 여기서는 세그먼트 트리를 이용하여 푸는 방법을 알아보겠습니다.
세그먼트 트리로 구하기
세그먼트 트리로 역순의 쌍을 구하는 방법은 구간 합을 사용합니다. 숫자를 하나씩 업데이트하면서 자신보다 큰 숫자들의 구간 합을 구하는 방식 입니다. 그럼 위의 숫자들을 가지고 구해보겠습니다.
전체 숫자의 범위 1부터 5까지 리스트에 숫자들을 업데이트하면서 자신보다 큰 구간의 합을 구해줍니다. 세그먼트 트리에 첫 번째 숫자 3을 업데이트 합니다. 그리고 3보다 큰 숫자들의 개수를 확인해 봅니다. [4 : 5] 구간의 합은 0입니다. 다음으로 두 번째 숫자인 2를 업데이트 합니다.
2를 업데이트하고 3부터 5까지의 범위의 구간 합을 확인해보면 1입니다. (3, 2) 에서 역순으로 되어 있는 순서쌍이 1개임을 알 수 있습니다. 다음으로 세 번째 숫자인 5를 업데이트 합니다.
5보다 큰 숫자는 없기 때문에 역순의 순서쌍도 없습니다. 추가된 순서쌍이 없기 때문에 지금까지 역순의 순서쌍은 1개 입니다. 다음으로 4를 업데이트 합니다.
4보다 큰 숫자의 구간 [5 : 5]의 구간 합은 1입니다. 지금까지 역순의 순서쌍의 총 합은 2가 됩니다. 마지막으로 1을 업데이트 합니다.
1을 업데이트하면서 구간 [2 : 5]의 합계는 4 입니다. 이렇게 이전까지의 순서쌍 2개에 4개가 추가되어 총 6개의 순서쌍을 가지게 됩니다.