2022년 5급 공채 기술 2차 자료구조론

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

제1문 (20점)

다음 방향 그래프에 대한 물음에 답하시오. (총 20점)
[그림]

(1) 정점(vertex) 0에서 시작하여 깊이 우선 탐색(DFS: Depth First Search)과 너비 우선 탐색(BFS: Breath First Search)을 수행할 때 방문하는 정점을 각각 순서대로 나열하시오. (단, 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 가장 작은 것을 방문한다) (8점)
(2) 위 그래프에 대한 위상 정렬(topological sort) 결과를 제시하시오. (단, 위상 정렬 과정에서 선택할 수 있는 정점이 여러 개인 경우 정점 번호가 가장 작은 것을 선택한다) (6점)
(3) 그래프는 인접 리스트(adjacency list)나 인접 행렬(adjacency matrix)로 표현할 수 있다. 정점 수에 비해 간선(edge)의 수가 작은 희소 그래프(sparse graph)에 대해 DFS나 BFS를 수행할 때 어느 표현법이 시간 복잡도 측면에서 더 효율적인지 서술하시오. (6점)

N개의 정수 A₁, A₂, …, A_N이 있다. 다음과 같이 중복을 제거하는 프로그램을 두 가지 방법으로 작성하고자 한다. 물음에 답하시오. (총 20점)

○한 번 나오는 정수는 그대로 둔다.
○두 번 이상 나오는 정수는 한 개를 제외하고 모두 삭제한다.

	<방법 1>

각 정수 A_k를 자신보다 앞에 있는 모든 정수와 비교하여 A_k와 같은 값의 정수를 삭제한다. 이 과정을 A₁부터 A_N까지 수행한다.

	<방법 2>

A₁, A₂, …, A_N에 대해 이진 탐색 트리(binary search tree)를 구성한다. 트리를 구성하는 과정에서 삽입하려는 정수와 같은 값이 이미 트리에 포함되어 있으면 그 정수를 삽입하지 않는다.

(1) 다음 데이터에 대해 <방법 1>과 <방법 2>를 적용한 결과를 제시하시오. (단, <방법 1>의 결과는 프로그램이 수행되는 과정에서 삭제된 정수를 삭제되는 순서대로 나열하고, <방법 2>의 결과는 최종 이진 탐색 트리를 그리시오) (10점)
14, 10, 17, 12, 10, 11, 20, 12, 18, 25, 20, 8, 22, 11, 23
(2) N개의 정수에 대해 <방법 1>의 최악의 경우 시간 복잡도, <방법 2>의 평균적인 경우와 최악의 경우 시간 복잡도를 구하시오. (10점)

다음 그래프에 대해 다익스트라(Dijkstra)의 최단 경로 알고리즘을 이용하여 정점 A로부터 다른 모든 정점들 사이의 최단 경로를 구하고자 한다. 이에 대해 다음 물음에 답하시오. (총 30점)
[그림]

(1) 알고리즘의 수행 과정에서 정점 A로부터의 최단 경로가 결정되는 정점을 순서대로 나열하시오. (8점)
A→( )→( )→( )→( )→( )→( )→( )
(2) 정점 A로부터 각 정점 v까지의 최단 경로 길이 d(A, v)를 구하여 아래 표를 채우시오. (10점)
v A B C D E F G H
d(A, v) 0
(3) 인접 행렬로 표현된 정점이 n 개이고 간선이 m개인 그래프에서 다익스트라의 최단 경로 알고리즘을 구현하고자 한다. 다익스트라 알고리즘의 최악의 경우 시간 복잡도를 구하시오. (단, 간선의 가중치는 모두 양수이다) (12점)

다음은 어떤 완전 이진 트리(complete binary tree)를 배열로 저장한 상태를 나타낸다. 다음 물음에 답하시오. (총 30점)

[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
11	20	1	3	28	10	5	19	15

(1) 위 배열이 나타내는 완전 이진 트리를 그림으로 나타내시오. (4점)
(2) 1)의 결과인 완전 이진 트리로부터 최대 히프(max heap)를 구성하는 과정을 보이고, 완성된 히프를 표현하는 배열을 제시하시오. (단, 이 과정을 시간 복잡도가 가장 작은 방법으로 수행하시오) (10점)
(3) 2)의 결과인 히프에 22를 삽입한 후 히프를 표현하는 배열을 제시하시오. (8점)
(4) 3)의 결과인 히프에서 최댓값을 삭제한 후 히프를 표현하는 배열을 제시하시오. (8점)

v	A	B	C	D	E	F	G	H
d(A, v)	0