병합 정렬(merge sort) 테크닉을 이용한 counting inversion 문제 해결하는 방법

1. counting inversion problem inversion이란 배열 A에 대하여 자기보다 뒤(index가 큰 쪽)에 있으면서 자기보다 값이 작은 A[j]를 뜻한다. 수학적으로 i A[j]를 만족하는 (i,j)의 개수를 세는 문제이다. 단순하게 세면 $O(N^{2})$이지만 실제 위치보다 전후 관계만 본다는 점을 관찰한다면, 2,X,X,X,X,X,X,X,X,1이더라도 2와 1은 inversion이고, 2,1,X,X,X,X,X,X,X,X,...더라도 2와 1은 inversion이다. 또한 다음 그림과 같이 화살표들의 교점의 개수와 동일하다. 두 수가 서로 inversion이면 교점이 하나 생기기 때문이다. 2. 해법 위 그림에서 볼 수 있는대로, 병합정렬을 하면 자연스럽게..