기수 정렬(radix sort)을 수행하여 다음 원소들을 오름차순으로 … | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 17년 1회차
기수 정렬(radix sort)을 수행하여 다음 원소들을 오름차순으로 정렬하고자 한다. 각 단계별 정렬 순서로 나타날 수 없는 것은? (단, 정수 KK는 0≤K≤9990 \le K \le 999 범위에 있고 각 자리수를 나타내는 3개의 서브키(K1K^1, K2K^2, K3K^3)로 구성되어 있다고 생각한다. 여기서 K1K^1는 일의 자리 수, K2K^2는 십의 자리 수, K3K^3는 백의 자리 수를 의미하고, 0≤Ki≤90 \le K^i \le 9이다)
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, … 순서는 처음 입력을 백의 자리만으로 분배한 결과로, 일의 자리부터 처리하는 기수 정렬의 어느 단계에서도 나오지 않는다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 17년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기