[BOJ] 1517

less than 1 minute read

버블 소트

1517번 https://www.acmicpc.net/problem/1517

inversion counting을 사용하는 전형적인 문제입니다.
(수열에서 자신보다 앞에 있는 숫자 중 자신보다 큰 수를 inversion이라 하는데 그러한 inversion의 개수를 세는 알고리즘입니다.)
머지 소트를 할 때, 병합 과정에서 생기는 모든 교차점들의 수가
버블 소트를 진행할 때 swap횟수와 같음을 이용하면 됩니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/1517.cpp

Categories:

Updated:

Leave a comment