Wizz군의 블로그에서 신입사원 면접 문제에 대한 포스트를 읽었습니다.
사실 저 문제는, Jon Bently의 유명한 "Programming Pearls" (번역서 제목은 "생각하는 프로그래밍" 입니다.) 의 첫번째 예제로 나오는 정수 파일 정렬하기의 거꾸로 버전입니다.
"1부터 27000 사이의 번호가 1번씩만 존재하는 파일이 있는데, 이 파일을 정렬하라. (단 파일에서 번호는 1번씩만 출현하고, 총 번호의 개수는 27000보다 작을 수 있다. 단, 프로그램이 돌아가는 환경에서 가용한 메모리는 수KB 안쪽으로 매우 작고, 거대 시스템의 하위 시스템으로 작동하는 모듈이라서 속도도 매우 빨라야 한다."
이 정도의 요구사항을 만족하는 코드를 작성하는 문제였죠. 책에는 Pseudo Code로 작성된 알고리즘이 소개되어 있습니다.
처음 저 책을 읽고서는 첫번째 예제가 너무 마음에 들어서 집에 가서 바로 작성해 봤던 기억이 있습니다.
얼마전에 신입사원 입사 문제로 출제하면서 다시 한번 짜봤는데, C++을 사용하면 매우 간단하게 만들 수 있습니다. bitset 컨테이너가 bitmap 자료구조를 손쉽게 구현하게 해주거든요. C로 하려면 약간 귀찮게 비트를 조작하는 매크로나 함수를 작성해야 합니다.
코드 보기..
반대로, Wizz 군의 블로그 내용을 만족하는 코드는 위의 예제를 좀 뒤집으면 되겠죠?
저장 공간을 아끼기 위해서 bitset 컨테이너를 사용했습니다.
코드 보기..
Wizz 군처럼 shuffle로 정해진 반복 회수를 보장하려면, random_shuffle을 사용하면 됩니다.
코드 보기..
Programming Pearls, 1980년대에 출판되었지만, 지금도 정말 읽을만 합니다.
이번 주말에 다시 한번 읽어봐야겠네요.
