Inversion counting(백준 10090,1517 버블소트)

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

병합정렬을 이용한 방법은 병합정렬을 사용해서 반으로 나눈 뒤 합치는 과정에서

오른쪽 배열에서 오는 수가 들어갈 때 왼쪽 배열에 있는 수가 남아있다면

바꿔주어야 하는 쌍의 수일 것이므로 남아있는 요소들의 수만큼 정답에 더해주게 된다.

[1,3,5,6] [2,4,7,8]의 병합 과정을 보자.

http://blog.daum.net/rhaoslikesan/282

2.Segment Tree

세그먼트 트리로 푸는 방법은 인덱스 트리를 활용하는 것이다. 백준 10090문제에 따르면 각 원소들의 크기는 100만까지로 제한되어있으므로 100만의 크기를 가진 리프노드와 트리를 만든 뒤

배열 앞에서 부터 자신보다 큰 값이 몇개나 들어와 있는지 세그먼트 트리를 이용해 logN으로 구해주면 NlogN에 모든 갯수를 구할 수 있다.

 

코드

merge sort

segment tree

배운점

• 세그먼트 트리 start,end값 left,right값에 조건문을 너무 실수한다. 다신 실수말자 left right가 start end를 포괄할때가 답이고 벗어날때 나간다.
• n이 커서 그런지 merge sort가 훨씬 빠르다.
• 세그먼트 트리의 활용되는 곳이 많다