ps:inversion_counting
Inversion Counting
- 어떤 리스트 A에서, i<j 인데 A[i]>A[j] 인 (i,j)쌍을 inversion이라고 한다. inversion counting은 이런 inversion의 갯수를 세는 것이다.
풀이법
- 이 문제를 O(nlogn)에 풀 수 있는 방법은, 분할 정복과 Order Statistic Tree를 쓰는 방법의 두가지가 있다.
- 분할 정복으로 푸는 방법은, 머지 소트를 살짝 변형한 것과 동일하다. 방법은 https://www.geeksforgeeks.org/counting-inversions/여기 참고.
- Order Statistic Tree를 쓰는 방법은, 앞에서부터 원소들을 차례대로 set에 추가하면서, set안의 그 원소보다 큰 수의 갯수를 세는 것이다. 이미 set 안에 추가되어있는 원소들은 index가 자신보다 작은 원소들이니까, 이중에서 rank()연산으로 값이 자신보다 큰 원소들의 갯수를 면 된다
- Python을 기준으로, Order Statistic Tree를 FenwickTree로 구현해서 사용했을 때 보통 범위에서는 실행 속도에 큰 차이가 없었다.
- 단순한 inversion counting 문제를 봤을때, 버블 소트 (n<500,000) 에서는 머지소트쪽이 좀 더 빨랐다. 그러나 좌표압축이 필요 없고, n이 더 커진 Counting Inversions (n<1,000,000) 에서는 Order Statistic Tree쪽이 더 빨랐다.
- 문제에서 할 일이 좀더 많아진 경우, 예를들면 달리기 에서는 Order Statistic Tree쪽이 더 빨랐다.
- 응용 문제에 적용할 수 있는 확장성면에서도 Order Statistic Tree를 쓰는 것이 더 유리하다.
- 그래서, inversion counting 관련 문제가 나오면 고민 없이 teflib.fenwicktree.OrderStatisticTree를 사용해서 풀기로 했다.
확장
일반적인 2-tuple에서 풀이
- 배열에서 i<j 인데 A[i]>A[j] 이 되는 것을 inversion이라고 정의했는데, 이것을 (인덱스, 값)이라는 튜플로 바꿔서 생각하면, P[i] = (i, A[i])인 pair의 리스트로 볼 수 있다. 그러면 이 문제는 P[i].first < P[j].first 이고 P[i].second > P[j].second 인 (i,j)를 찾는 것과 동일하다. 따라서 아무 pair형태의 데이터에서도 이것을 똑같이 적용할 수 있다. 2차원 좌표상의 점들이 대표적인 예다. P_i = (x_i,y_i)라는 점들이 주어질때, x_i < x_j 이면서 y_i > y_j 인 (P_i, P_j)쌍의 갯수를 구하는 것, 다시 말하면 위치 관계가 ↖↘ 방향에 놓여 있는 포인트 쌍의 갯수를 구하는 문제를 똑같은 방식으로 풀 수 있다.
- 먼저 점들을 x에 대해서 정렬하고, x가 작은 것부터 대응되는 y값을 set에 추가하며, set 안에서 자기보다 더 큰 수의 갯수를 세면 된다.
- x_i < x_j이고 y_i < y_j 인 쌍을 구하는 것도 동일하다. 이런 쌍을 보통 dominated pair이라고 부른다
3-tuple
- 2-tuple에 적용했던 비슷한 아이디어를 3-tuple로 확장시켜보자.
- P[i]=(x_i,y_i,z_i)일 때, dominated pair의 갯수를 세는 것은 x_i<x_j, y_i<y_j, z_i<z_j 인 (p[i], p[j])쌍의 갯수를 세는 것이 된다. 이것을 하려면 x에 대해 소팅해서, 어떤 데이터 구조 안에 x값이 더 작은 튜플들만 모아놓는 것까지는 똑같지만, 그 데이터 구조 안에서 y<Y이고 z<Z인 튜플을 찾을 수 있어야 한다. 이것을 지원하려면 Order Statistic Tree를 2차원으로 짜야 한다.
- 3-tuple에서 좀더 쉬운 문제는 dominated pair의 갯수가 아닌, 존재 여부만 찾는 것이다. 이것은 구간 최솟값 쿼리를 통해서 풀 수 있다. 일단 x에 대해서 정렬해서 x_i<X인 점들만 저장해놓는다. A[y]가 해당되는 점의 z값중 최솟값을 갖도록 저장하면, 이제 y<Y 이고 z<Z인 점이 존재하는 지 여부는 min(A[0:Y]) 가 Z보다 큰지 아닌지를 비교해서 구할 수 있다. 세그먼트 트리를 쓰면 구간 최솟값과 점 추가를 O(logn)에 할 수 있다. 이 문제에서는 쿼리 범위가 항상 0으로 시작하므로 펜윅트리로도 처리할 수 있다.
세 개의 원소의 inversion
- tuple의 사이즈를 늘리는 대신, 점의 갯수를 늘리는 쪽으로 확장해보자. 즉 x_i < x_j < x_k 이고 y_i < y_j < y_k 인 (i,j,k) 트리플, 또는 3-inversion의 갯수를 찾는 문제로 확장해보자.
- x에 대해서 정렬해서 순서대로 추가한다는 기본은 변함 없다.
- (x_k,y_k)를 추가할 때, 이미 저장된 점들로 만들어진 2-inversion (i,j)들 중에서 y_j<y_k 인 것의 갯수를 세어주면 된다.
- 이를 구현하기 위해서는, y값들을 저장하는 Order Statistic Tree와 2-inversion에서 큰쪽의 y값들을 저장하는 Order Statistic Tree를 따로 만들어서 각각 업데이트해주면 된다.
- 불만 정렬에도 좀더 설명이 있으니 참고.
- 이걸 더 확장해서 n개의 원소의 inversion을 찾을수도 있다.
- i번째 원소로 끝나는 (k-1)-inversion의 갯수를 알고 있으면, 거기에서 i번째 원소로 끝나는 k-inversion의 갯수를 OST를 이용해서 구할수가 있다. 이 결과를 다시 저장해두고 여기에서 (k+1)-inversion의 갯수를 구하는 식으로 반복해나간다
- blobhyperthink 참고.
코드
- 버블 소트 참고.
관련 문제
ps/inversion_counting.txt · 마지막으로 수정됨: 2023/08/04 01:09 저자 teferi
토론