그 분 질문 : 자, 한 반에 40명의 아이들이 있습니다. 아이들이 달리기 시합을 해서 도착한 순서대로 달리기 기록과 순위를 입력해놓았습니다. 그리고 그 결과를 아래와 같이 표로 나타냈습니다.

---------------------------------------
순위      번호      이름     기록
---------------------------------------
 01       12        .....        ......
 02       04        .....        ......
 03       30        .....        ......
 04       21        .....        ......
 ..
 ..
 ..
 40       03        .....        ......
---------------------------------------
[표1] 기록 순으로 정렬한 학생 명단

그런데 결과를 위와같이 출력하지 말고 아래처럼 학생 번호 순으로 보여줘야 합니다.

---------------------------------------
번호      순위      이름     기록
---------------------------------------
 01       18        .....        ......
 02       09        .....        ......
 03       40        .....        ......
 04       02        .....        ......
 ..
 ..
 ..
 40       11        .....        ......
---------------------------------------
[표2] 학생 번호 순으로 정렬한 학생 명단


[표1]을 [표2]처럼 정렬하는데 가장 빨리 정렬하는 방법을 말해보세요.


나 : 에... 아무래도 퀵소트를 쓰는게... 가장 빠르지 않겠나....

그분 : 퀵소트가 제일 빠른가요?

나 : 에... 예....(자, 잘못 말했나??) 제가 알기로는 nlogn 으로 특별한 경우를 제외하면 가장 성능이 우수한 걸로... -_-;

그분 : 그럼 퀵소트보다 더 빠르게 정렬할 수 있는 방법은 없나요?

나 : 에.. 그게... 이론적으로 nlogn보다 더 빠를 수 없다고 알고 있어서.....(머, 머지소트인가? -_-;;)

그 분 : 정말인지 확인해봤습니까?

나 : 에.. 아니요, 그게... 제가 그걸 확인해 볼 능력이 될지는... 아하하..(적당히 웃음으로 ^^;;)

((다른 이야기 하다가 마지막에))

그 분 : 뭐 더 물어보고 싶은것 있나요?

나 : 아, 예. (문제 가리키면서) 이거 답 좀 알려주시면 안될런지요?

그 분 : 한 번 생각해보세요. O(n)만에 정렬하는 방법이 있습니다.

나 : 아, 예....



대강 이런 식으로 마무리된 대화....

그리고 지하철에서 엄청난 인파에 밀리면서 nlogn보다 더 빠른 방법이 있다니, 논문으로 쓰면 튜링상도 받겠다... 생각하다가... 지하철에서 사람이 많이 빠진 후 자리에 앉아서 종이에 끄적끄적하다가 무심코 "번호에서 순위를 빼보았다가" 힌트를 찾았다.

----------------------
순위      번호      (번호-순위)
----------------------
 01       12              11
 02       04               2
 03       30             27
 04       21             17
 ..
 ..
 ..
 40       03             -37
----------------------

순위와 번호가 정확히 1:1 대응이 되기 때문에 (번호-순위)만큼 위치를 이동시키면 O(n)만에 정렬이 된다.

전체 리스트를 훑는데 n 만큼의 시간이 필요하고 리스트의 각 원소마다 적어도 logn 만큼 비교 시간이 필요하지만 여기서는 1:1 대응이라는 점을 이용해서 logn만큼의 비교횟수를 생략할 수 있어서 O(n)만에 정렬할 수 있다.

(예를 들자면 12번 학생은 현재 위치에서 11만큼 아래로 이동하면 된다.)

'생각한조각' 카테고리의 다른 글

[블로그 리뉴얼] syntax highlighting 업데이트  (0) 2011.02.09
Sun 웹서버 7.0  (0) 2010.05.11
티스토리에서 PRE 태그의 문제점  (1) 2010.04.28
Posted by yeori
,