2023년 5급 공채 기술 2차 알고리즘

문제 3개 · 50점. 참고 답안·채점 기준은 앱에서 볼 수 있습니다.

제1문 (12점)

다음과 같은 이진트리가 있을 때 각각의 노드를 모두 방문하는 순회(Traverse)를 하려 한다. 루트 노드가 F일 때 물음에 답하시오. (총 12점)
[그림]

다음과 같은 순서대로 원소들이 배열되어 있고 오름차순으로 정렬하고자 한다. 물음에 답하시오. (총 18점)

15 30 60 5 35 18

(1) 선택 정렬 방법을 이용하여 정렬하는 과정을 보이고, 정렬이 완료된 시점에서 원소 간의 총비교 횟수를 구하시오. (5점)
(2) 퀵 정렬 방법이 수행되는 과정을 보이고 정렬이 완료된 시점에서 원소 간의 총비교 횟수를 구하시오. (단, 퀵 정렬에서 기준원소(피벗)는 항상 마지막 원소를 사용하는 것으로 가정한다) (6점)
(3) 1)과 2)의 방법들에 대해 배열에 포함된 원소의 개수를 n개라고 가정하였을 경우 각각의 방법에 대한 복잡도를 원소 간 비교 횟수만을 기준으로 하여 점근적 표기법을 이용하여 비교하고 설명하시오. (7점)

어떤 문서 M이 a, b, c, d, e, f의 여섯 가지 문자만으로 구성되어 있고, 해당 문서에서 각 문자의 빈도수가 다음 표와 같다. 물음에 답하시오. (총 20점)

(1) 각 문자를 다음과 같은 이진 코드로 표현할 때, 문서 M을 저장하기 위하여 필요한 저장 공간은 몇 bits인지 구하시오. (5점)
문자 이진 코드
a 000
b 001
c 010
d 011
e 100
f 101
(2) 각 문자의 이진 코드를 어떻게 정하느냐에 따라 문서 M의 저장 공간은 1)의 결과보다 커질 수도 있고 작아질 수도 있다. 문서 M의 저장 공간을 최소화하도록 하는 각 문자의 이진 코드를 구하고, 그때 필요한 저장 공간이 몇 bits인지 구하시오. (단, 문서 M은 각 문자의 이진 코드 그대로 저장되며, 저장된 내용으로부터 문서 M이 유일하게 구해져야 한다) (15점)