오늘 우연찮게 찾아본 자료.. 이참에 정리해두는게 낫겠다..


어떤 1~n 까지의 수의 permutation을 정렬하기 위해 최소 몇번의 swap operation이 필요할까?

1. 이웃하는 수끼리만 swap이 가능하다면 bubble sort시 swap 이 일어나는 개수와 같다..
2. 임의의 수끼리 swap이 가능하다면 아래의 방법을 사용한다..

Let's take for example your data 4 2 3 1. It can be rewriten this way (14)(2)(3). Here we see one cycle of length 2 and two of length 1. The key idea is that: to sort a cycle optimally we need (length-1) operations. So here we need (2-1)+(1-1)+(1-1) swaps.
 
Another example 2 3 1. Its cycle representation is (123) - one cycle of length 3 - so we need 2 swaps to sort it.


UVa 보드에서 퍼온 글인데.. 이와 관련되어 유용한 내용이 많다..


관련문제:
299 - Train Swapping
10570 - Meeting with Aliens


ps)
오늘 아침 10시에 탑코더가 열렸었는데.. 후배 한명이 Div2 500점 문제를 풀다가 # of swap operation에 대해서 마구 물어보길래.. 잽싸게 자료를 찾아서 설명해줬다.. 나중에 문제를 읽어봤는데.. # of swap operation과는 전혀 상관없는 문제잖아.. -_-

'Problem Solving > Algorithm notes' 카테고리의 다른 글

Plane Equation (평면의 방정식)  (0) 2009.04.16
Ellipse (타원)  (0) 2009.04.15
Modular Arithmetic 1탄 - Extended Euclid  (2) 2009.02.22
Combination 개수 구하기 (Pascal's Triangle)  (2) 2009.02.07
Josephus Problem  (2) 2009.01.01
Number of Swap Operations  (0) 2008.07.24
소수 구하는 방법 (Sieve of Eratosthenes)  (2) 2008.07.15
Horner's Rule  (0) 2008.05.04
GCD SUM  (0) 2008.03.18
Erdos & Gallai  (0) 2008.03.04
Game Theory  (0) 2007.12.19

Leave a Comment


to Top