Number of Swap Operations
Problem Solving/Algorithm notes 2008. 7. 24. 22:53
오늘 우연찮게 찾아본 자료.. 이참에 정리해두는게 낫겠다..
어떤 1~n 까지의 수의 permutation을 정렬하기 위해 최소 몇번의 swap operation이 필요할까?
1. 이웃하는 수끼리만 swap이 가능하다면 bubble sort시 swap 이 일어나는 개수와 같다..
2. 임의의 수끼리 swap이 가능하다면 아래의 방법을 사용한다..
UVa 보드에서 퍼온 글인데.. 이와 관련되어 유용한 내용이 많다..
관련문제:
299 - Train Swapping
10570 - Meeting with Aliens
ps)
오늘 아침 10시에 탑코더가 열렸었는데.. 후배 한명이 Div2 500점 문제를 풀다가 # of swap operation에 대해서 마구 물어보길래.. 잽싸게 자료를 찾아서 설명해줬다.. 나중에 문제를 읽어봤는데.. # of swap operation과는 전혀 상관없는 문제잖아.. -_-
어떤 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.
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' 카테고리의 다른 글
| Bell Number (0) | 2009.07.12 |
|---|---|
| Finding Minimum Path Cover in DAG (0) | 2009.06.15 |
| Plane Equation (평면의 방정식) (0) | 2009.04.16 |
| Ellipse (타원) (0) | 2009.04.15 |
| Combination 개수 구하기 (Pascal's Triangle) (2) | 2009.02.07 |
| 소수 구하는 방법 (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 |
| Misère Nim (2) | 2007.12.16 |