5급 공채 2차

2017년 5급 공채 기술 2차 자료구조론(선택)

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

제1문 (10점)

범위 최소 질의(Range Minimum Query, RMQ) 문제는 다음과 같이 정의된다. 크기가 n인 배열 A[0..n-1]에 서로 다른 정수들이 저장되어 있고, 0≤a≤b≤n-1인 두 정수 a, b가 질의로 주어졌을 때 A[a], A[a+1], ..., A[b] 중 가장 작은 값을 반환한다. 단순한 순차검색 알고리즘의 시간 복잡도는 최악의 경우 O(n)이다. 물음에 답하시오. (총 10점)
  1. (1) 알고리즘의 성능 개선을 위해 배열 A를 A[0]...A[\sqrt{{n}}-1], A[\sqrt{{n}}]...A[2\sqrt{{n}}-1], ... , A[n-\sqrt{{n}}]...A[n-1]과 같이 길이가 \sqrt{n}인 구간을 \sqrt{n}개 만든 다음, 각 구간의 최소값을 미리 구한다. 이 과정의 시간 복잡도가 O(n)임을 보이시오. (3점)
  2. (2) 1)에서 구한 결과를 이용하여 두 정수 a, b에 대한 RMQ 문제에 답하는데 최악의 경우 O(\sqrt{{n}}) 시간이 걸리는 알고리즘을 설명하고, 시간 복잡도가 위와 같음을 보이시오. (7점)

제2문 (10점)

배열 B는 n개의 상이한 정수들이 오름차순으로 정렬된 배열이다. 배열 A는 배열 B의 원소들을 오른쪽으로 k(0≤k<n)만큼씩 원형으로 이동한 배열이다. 예를 들어서 B＝(15, 25, 37, 39, 45, 52)일 때, A＝(45, 52, 15, 25, 37, 39)는 k＝2만큼 이동한 배열이고, A＝(37, 39, 45, 52, 15, 25)는 k＝4만큼 이동한 배열이다. 다음 물음에 답하시오. (단, 배열의 첨자는 0부터 시작한다고 가정한다) (총 10점)
  1. (1) 배열 A와 정수 k를 입력받아 A에서 가장 큰 원소를 찾는 시간 복잡도가 O(1)인 알고리즘을 설명하시오. (3점)
  2. (2) k는 알려지지 않은 채 배열 A만 주어졌을 때, A에서 가장 큰 원소를 찾는 시간 복잡도가 O(log n)인 알고리즘의 핵심 아이디어를 설명하고, 이를 C 언어와 유사한 의사코드(pseudo code)로 작성하시오. (7점)

제3문 (10점)

어느 지역 내 특정 도시에 병원과 장애인 복지센터를 세우고 전력선을 설치하고자 한다. 그 지역의 도시를 정점(vertex)으로 도시 간의 도로를 간선(edge)으로 표시한 그래프가 다음과 같다. 물음에 답하시오. (단, 간선의 숫자는 도로의 거리를 표시한 것이다) (총 10점)
1
3
5
2
7
3
2
4
2
10
4
11
  1. (1) 병원은 각 도시로부터 병원이 위치할 도시까지의 거리 합이 최소가 되는 도시에 세우려고 한다. 병원이 세워질 도시와 각 도시 간의 거리의 합을 구하시오. (5점)
  2. (2) 장애인 복지센터가 위치하는 도시는 각 도시로부터 장애인 복지센터가 위치할 도시까지의 거리 중 최장인 거리가 가장 짧은 곳에 세우려고 한다. 장애인 복지센터가 세워질 도시를 구하시오. (3점)
  3. (3) 정점 4에 전력회사를 세워 각 도시에 전기가 공급되도록 전력선을 깔려고 한다. 전력선을 가장 짧게 연결할 수 있도록 전력선 망을 설계하는 과정을 보이시오. (2점)

제4문 (10점)

ASCII 문자들로 구성된 길이가 m과 n인(n>m) 문자열(string) s1과 s2가 있다. 다음 물음에 답하시오. (단, ASCII 문자는 총 256개의 서로 다른 값을 갖는다) (총 10점)
  1. (1) s1과 s2를 비교하여, 양쪽에 모두 있는 문자들을 전부 찾아 출력하는 알고리즘을 설계하려고 한다. 시간 복잡도(time complexity)가 O(mn) 걸리는 알고리즘을 설계하라. (2점)
    예) 입력:s1 = "data structure", s2 = "algorithm analysis"
    출력:a, t, s, r (단, 출력 순서는 상관 없음)
  2. (2) 1)의 알고리즘보다 시간 복잡도가 향상된 O(n)의 시간이 걸리는 알고리즘을 설계하라. (3점)
  3. (3) s1이 s2에 포함되는지 즉, s1이 s2의 sub-string인지를 판정하는 시간 복잡도가 O(n)인 알고리즘을 구현할 수 있다면 그러한 알고리즘을 제시하고, 없다면 그 이유를 설명하시오. (5점)

제5문 (10점)

각 노드가 다음과 같은 구조체인 이진 탐색 트리가 그림과 같이 구성되어 있다.
struct node {
char key;
int size;
struct node *left, *right;
};
typedef struct node node_t;

H
7
L
2
N
1
G
4
B
3
E
1
A
1
root

단, 리프(leaf)노드의 size는 1이며 리프(leaf)가 아닌 노드의 size는 아래과 같이 정의된다.
node→size = node→left→size + node→right→size + 1
물음에 답하시오. (총 10점)
  1. (1) 루트 노드 root가 가리키는 이진 탐색 트리에서 size 필드를 이용하여 key 값이 i-번째 순위의 노드를 반환하는 함수를 oSelect(root, i)라고 한다. 예를 들어, 위 그림에서 oSelect(root, 5)를 입력하면 ‘노드 H’의 포인터가 반환된다. 아래의 oSelect() 함수를 완성하시오. (단, 파라미터 i는 항상 범위 안의 값을 가진다고 가정한다) (7점)
    node_t *oSelect(node_t *node, int odr)
    {


    }
  2. (2) 균형이진트리의 경우와 최악의 경우 각각에 대하여, 함수 oSelect()의 시간복잡도를 big-O로 표현하고 그 이유를 설명하시오. (단, 전체 노드의 개수는 N이라고 가정한다) (3점)