코딩못하는사람

Inversion counting이란? 배열 A는 1,2,3,...n 의 수가 무작위 순서로 들어 있다고 했을 때 그 순서 대비 크기가 역전되어 있는 수들의 쌍을 구하는 문제이다 예를들어 4 2 7 1 5 6 3순서의 배열은(4–2), (4–1), (4–3), (2–1), (7–1), (7–5), (7–6), (7–3), (5–3), (6–3)인 10개의 역순쌍이 있는 것이다. Inversion counting 해결방법 직관적으로 해결하자면 O(n^2)을 이용해서 모든 수에서 모든수를 돌아보면 되지만 O(NlogN)으로 해결하는 merge sort를 이용한 방법과 segment tree를 이용한 방법이 있다. 1.merge sort 병합정렬을 이용한 방법은 병합정렬을 사용해서 반으로 나눈 뒤 합치는 과정..