Sorting 문제에 대해서 CS전공자라면 분명 학부 시절에 배울 것이고, 비 전공자라고 해도 컴퓨터를 만지는 사람이라면 한번즈음은 다루어 보는 문제 일 것입니다. 일반적으로 Sorting 알고리즘의 복잡도는 얼마라고 배웠나요?
O(nLogn)의 복잡도가 Sorting problem의 Minimum complexity라고 증명된 사실입니다. (Foundations of algorithms, Richard Neapolitan)
여기에 전화번호부가 있습니다. 전화번호의 기록 방식은 여러가지가 있습니다만, 여기서 전화번후부는 XXX-XXX-XXXX의 포맷을 가진다고 가정하죠. 이 전화번호부에 나와 있는 전화번호들을 Ascending(오름차순) Sorting방식으로 출력 하는 알고리즘을 구성해보세요. 물론, Ascending으로 출력하는 알고리즘의 복잡도는 O(n)이어야 합니다.
예를 들면 전화번후부에 아래와 같은 번호들이 리스트업 되어 있을때
031-208-0001
051-866-0001
02-208-0010
출력은 아래와 같은 방식으로 이루어집니다.
02-208-0010
031-208-0001
051-208-0001
문제의 편의를 위해서 사용할 수 있는 외부 메모리는 무한정 있다고 가정하며 알고리즘은 아이디어 수준 또는 의사코드 수준으로 제시 하시면 됩니다. 문제를 3분안에 푸시는 분은 알고리즘 수업을 아주 잘 이용하거나 응용하시는 분 이실 것이고 그 이상은 스스로 문제를 해결 하시는 분일 것입니다. 개인적으로 후자의 정답을 기대 해봅니다.
'For craft > Quiz' 카테고리의 다른 글
| O(n), Print problems (8) | 2008/12/02 |
|---|---|
| Answers which are 1 bit counter and TLZ (0) | 2008/09/30 |
| 1 bit counter of O(lnN) in bit string. (8) | 2008/09/05 |
| Operation of Bit string (25) | 2008/08/30 |