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

	import sys
	input=sys.stdin.readline
	def merge(a,b):
	global cnt
	la,lb=len(a),len(b)
	i,j=0,0
	temp=[]
	while i<la and j<lb:
	if a[i]>b[j]:
	temp.append(b[j])
	j+=1
	cnt+=la-i
	else:
	temp.append(a[i])
	i+=1
	if i==la:
	temp.extend(b[j:])
	else:
	temp.extend(a[i:])
	return temp
	def merge_sort(arr):
	if len(arr)<=1:
	return arr
	left=0
	right=len(arr)-1
	mid=(left+right)//2
	return merge(merge_sort(arr[left:mid+1]),merge_sort(arr[mid+1:]))
	n=int(input())
	cnt=0
	arr=list(map(int,input().split()))
	merge_sort(arr)
	print(cnt)

view raw Counting Inversion (merge sort).py hosted with ❤ by GitHub

segment tree

	import sys
	from math import ceil,log2
	input=sys.stdin.readline
	p=1000000
	def find(start,end,left,right,node):
	if start>right or end<left:
	return 0
	if left<=start and end<=right:
	return tree[node]
	mid=(start+end)//2
	return find(start,mid,left,right,node*2)+find(mid+1,end,left,right,node*2+1)
	def update(node):
	temp=size+node-1
	while temp>=1:
	tree[temp]+=1
	temp//=2
	n=int(input())
	data=list(map(int,input().split()))
	size=2**ceil(log2(p))
	tree=[0]*(size*2)
	ans=0
	print(tree[1048576:1048600])
	for i in data:
	print(i,'z')
	print(find(1,size,i+1,size,1))
	ans+=find(1,size,i+1,size,1)
	update(i)
	print(tree[1048576:1048600])
	print(ans)

view raw 10090 Counting Inversions.py hosted with ❤ by GitHub

배운점

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