티스토리 뷰
필요한 배경지식
- 세그먼트 트리
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쌍을 구하기 위한 방법으로 완전탐색을 생각해보면
이 문제를 해결하는데 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 → 새로운 Inversion쌍 : (4-2)
3. A = {4, 2, 7} , count = 1
4. A = {4, 2, 7, 1} , count = 4 → 새로운 Inversion쌍 : (4-1) , (2-1) , (7-1)
5. A = {4, 2, 7, 1, 5} , count = 5 → 새로운 Inversion쌍 : (7-5)
6. A = {4, 2, 7, 1, 5, 6} , count = 6 → 새로운 Inversion쌍 : (7-6)
7. A = {4, 2, 7, 1, 5, 6, 3} , count = 10 → 새로운 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개의 수를 가질때 세그먼트 트리를 이용하여 구간합을 구하면
연습문제