기수 정렬(radix sort)을 수행하여 다음 원소들을 오름차순으로 … | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 17년 1회차
기수 정렬(radix sort)을 수행하여 다음 원소들을 오름차순으로 정렬하고자 한다. 각 단계별 정렬 순서로 나타날 수 없는 것은? (단, 정수 는 범위에 있고 각 자리수를 나타내는 3개의 서브키(, , )로 구성되어 있다고 생각한다. 여기서 는 일의 자리 수, 는 십의 자리 수, 는 백의 자리 수를 의미하고, 이다)129, 308, 506, 92, 3, 841, 33
1
3, 506, 308, 129, 33, 841, 92
2
92, 3, 33, 129, 308, 506, 841
3
841, 92, 3, 33, 506, 308, 129
4
3, 33, 92, 129, 308, 506, 841
해설
나타날 수 없는 순서는 92, 3, 33, 129, 308, 506, 841이다.
기수 정렬은 일의 자리부터 안정적으로 분배·수집하므로 각 단계의 결과는 다음과 같다.
- 일의 자리 기준: 841, 92, 3, 33, 506, 308, 129로 나타날 수 있다.
- 십의 자리 기준: 3, 506, 308, 129, 33, 841, 92로 나타날 수 있다.
- 백의 자리 기준: 3, 33, 92, 129, 308, 506, 841로 최종 결과이다.
92, 3, 33, … 순서는 처음 입력을 백의 자리만으로 분배한 결과로, 일의 자리부터 처리하는 기수 정렬의 어느 단계에서도 나오지 않는다.
오류나 개정된 내용이 보이면 알려주세요