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

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

제1문 (30점)

아래와 같은 C언어 형식의 구조를 이용하여 희소 행렬(sparse matrix)을 표현하고자 한다. 즉, 희소 행렬의 원소를 <행(row), 열(col), 값(value)> 3원소 쌍을 사용하여 표현한다. 단, 배열의 위치 0의 row, col, value는 각각 행의 수, 열의 수, 0이 아닌 항의 총 수를 나타낸다. 배열의 위치 1에서부터는 0이 아닌 항을 나타내는 3원소 쌍을 저장한다. 3원소 쌍은 row값 우선으로 정렬되며, 같은 값을 가지는 row에서는 col값 우선으로 정렬된다. 다음 물음에 답하시오. (총 30점)

#define MAX_TERMS 101 /* 항의 최대 수 + 1 */
typedef struct {
int row; /* 행 */
int col; /* 열 */
int value; /* 값 */
} term;
term a[MAX_TERMS], b[MAX_TERMS];

(1) 아래의 희소 행렬 A를 위의 3원소 쌍으로 표현하여 배열 a에 저장할 때, 배열 a의 내용을 보이시오. (5점)
A = {pmatrix {6 0 0 2 0 5 \\ 0 0 3 0 0 0 \\ 0 0 0 7 0 0 \\ 0 0 0 0 0 0 \\ 9 0 0 0 0 0 \\ 0 0 8 0 0 0}}
(2) 위에서 제시한 자료구조를 사용하여 희소 행렬의 전치 행렬을 구하려고 한다. 시간복잡도 O(columns+elements)인 C언어 형식의 의사 코드(pseudo code)를 작성하시오. (단, columns는 희소 행렬의 열의 수이고 elements는 원소의 수이다) (20점)
(3) 1)에서 보인 배열 a에 대해서, 2)에서 제시한 전치 행렬을 구하는 함수를 이용하여 전치 행렬의 결과를 3원소 쌍으로 표현하여 배열 b에 저장하는 경우, 배열 b의 내용을 작성하시오. (5점)

제2문 (30점)

Union-Find 추상자료형(abstract data type)에서 각 원소는 하나의 집합에 속하며 서로 다른 집합끼리는 공유하는 원소가 없다. 그리고, 각 집합에는 고유한 ID가 부여되어 있다. Union-Find 추상자료형에서 제공되는 연산은 MakeSet, Union, Find이며 인터페이스는 아래와 같다.

○MakeSet(s):새로운 값 s를 유일한 원소로 가지는 새 집합을 생성한다.
○Find(s): 원소 s가 속한 집합의 ID를 반환한다.
○Union(s, t):두 원소 s와 t가 서로 다른 집합에 속해 있을 때, 두 집합을 합집합시킨다. 이때 합쳐진 집합의 ID는 s가 속한 집합의 ID이거나 t가 속한 집합의 ID이다. 두 값 중 임의의 값으로 구현 과정에서 정할 수 있다.

Union-Find 추상자료형은 연결리스트(linked list) 형태를 이용하여 선형구조로 구현할 수 있다. 예를 들어 집합 S_{1} = \left\{ a , \ b \right)일 때, S_{1}을 표현하는 연결리스트의 구조는 아래와 같이 구현될 수 있다. 아래 그림에서 화살표는 주소가 저장되어 연결된 관계를 보인다. 한 집합의 ID는 집합에 속한 원소에 해당하는 노드들에 모두 기록된다. 그림의 count는 집합에 속한 원소의 개수이다.
[그림]
이때 다음 물음에 답하시오. (총 30점)

(1) 두 집합 S_{1} = \left\{ a_{1} , \cdots , a_{n}_{1} \right\}과 S_{2} = \left\{ b_{1} , \cdots , b_{n}_{2} \right\}에 대해,
Find(a_{i})(1 \le i \le n_{1}) 연산과 Union(a_{{i}} \, , \, \, b_{{j}}) (1 \le i \le n_{1} , \ 1 \le j \le n_{2}) 연산의 효율적인 구현 방법 및 시간복잡도에 대해 설명하시오. (단, Find 함수의 인자인 a_{i}와 Union 함수의 인자인 a_{{i}} \, , \, \, b_{{j}}는 연결리스트에서 해당 원소가 저장된 노드로 주어진다) (10점)
(2) 총 n개의 원소를 저장하고 있을 때 최초 n개의 MakeSet 연산을 포함하여 총 m개의 연산이 수행되었다면( m \ge n ), 위에서 구상한 효율적인 구현 방법의 최악수행시간을 분석하시오. (20점)

제3문 (20점)

이진트리에 대한 다음 질문에 답하시오. (총 20점)

(1) 이진트리 T에 대한 중위순회와 후위순회의 결과가 다음과 같을 때, 이진트리 T를 그리시오. (10점)
중위순회:B D F C H I A G E
후위순회:B F C D I G E A H

(2) 다음은 이진트리의 높이를 구하는 C프로그램의 일부이다. height_count 함수 중 ㉠, ㉡, ㉢에 들어갈 C코드를 작성하시오. (10점)

typedef struct tree_node {
char data;
struct tree_node *left, *right;
} tree_node;

int max(int a, int b) {
if (a > b) return a;
else return b;
}

int height_count(tree_node* ptr) {
int htl, htr, ht = 0;
if (ptr != NULL) {
htl =

㉠

;
htr =

㉡

;
ht =

㉢

;
}
return ht;
}

㉠

㉡

㉢

제4문 (20점)

다음 가중 그래프에서 Prim’s algorithm을 사용하여 최소 신장 트리를 구하려고 한다. 최소 힙(min heap)을 이용하여 Prim’s algorithm을 사용하여 매 단계마다 최소 신장 트리에 추가될 노드를 선택하려고 한다. 다음 물음에 답하시오. (총 20점)
[그림]

(1) A에서 Prim’s algorithm을 시작할 때, 시작 노드와 알고리즘이 종료할 때까지 노드들이 트리에 추가되는 순서와 진행과정을 쓰시오. (10점)
(2) 최소 신장 트리에 노드 C를 추가하기 직전에 힙 루트에 있는 그래프의 노드와 힙 루트의 두 자식에 해당하는 그래프의 노드들을 쓰고, 그때까지의 알고리즘 진행 과정을 서술하시오. (10점)