[알고리즘] Counting inversions

Counting inversions 예를들어 배열A에 1, 2, 3, ... n 의 수가 무작위 순서로 들어있다고 해보자. 이 수들에서 2개의 무작위 수를 생각했을 때, 그 순서 대비 크기가 역전되어 있는 두 수의 쌍이 몇개가 되는지를 구해보자. 예를 들어 A {2, 3, 6, 4, 1, 7}이 있을때, 크기가 역전된 쌍은 (2, 1), (3, 1), (6, 4), (6, 1), (4, 1) 이 있다. 따라서 Inversion 된 쌍의 수는 5개 이다. 이런 Inversion된 쌍의 수를 어떻게 구해야 할까? 직관적으로 떠오르는 직접다 for문 돌면서 확인하는 방식은 O(n^2)이 걸릴것이 눈에 훤하다... 이럴때 Merge Sort를 활용하면 O(nlogn)에 가능해진다. Merge Sort Merge Sort를 진행하는 과정에서 교차점의 개수..........

원문링크 : [알고리즘] Counting inversions