7급 국가직 알고리즘 기출문제 전 회차를 한 권으로 — PDF 전자책(문제집·정답해설집)

26년 1회차

총 25문항 · 객관식 · A4 약 1장

1 / 1

A4정답 포함← → 키 · 드래그로 넘김

7급 국가직 알고리즘 기출문제모두CBT · moducbt.com

26년 1회차

총 25문항 · 객관식 · 정답·해설 포함

문제 1

다음 중 레드－블랙 트리(red-black tree)의 특성으로 옳은 것만을 모두 고르면?

ㄱ. 모든 노드는 레드 또는 블랙이다.
ㄴ. 루트 노드는 레드이다.
ㄷ. 레드 노드의 자식 노드는 항상 블랙이다.
ㄹ. 모든 리프 노드(NIL)는 레드이다.

1ㄱ, ㄴ

2ㄱ, ㄷ

3ㄴ, ㄷ

4ㄷ, ㄹ

정답 및 해설

레드-블랙 트리의 특성으로 옳은 것은 모든 노드가 레드 또는 블랙이라는 것과 레드 노드의 자식은 항상 블랙이라는 것이다.

레드-블랙 트리는 색 규칙(루트·NIL 리프는 블랙, 레드 노드 연속 금지, 루트에서 각 NIL까지 블랙 노드 수 동일)으로 높이를 $O(\log n)$ 로 유지한다.

루트 노드는 레드가 아니라 블랙이어야 한다.
모든 리프 노드(NIL)도 레드가 아니라 블랙이다.

문제 2

동적 계획법(dynamic programming)에 대한 설명으로 옳지 않은 것은?

1부분 문제들 사이에는 의존적 관계가 없다.

2동일한 부분 문제들을 다시 풀지 않도록 하기 위해 부분 문제들의 해를 저장한다.

3주어진 문제를 작은 문제로 나누어 해결하고 이를 이용하여 원래 문제의 해를 도출한다.

4이 기법을 적용할 수 있으려면 최적성의 원리(principle of optimality)가 성립하여야 한다.

정답 및 해설

동적 계획법에서 부분 문제들 사이에 의존 관계가 없다는 설명은 옳지 않다.

동적 계획법은 큰 문제의 해가 작은 부분 문제의 해에 의존하고, 같은 부분 문제가 반복해서 나타나는(중복 부분 문제) 상황에 쓰인다. 부분 문제들이 서로 독립적인 것은 분할 정복의 특징이다.

부분 문제의 해를 테이블에 저장해 다시 풀지 않는 것은 동적 계획법의 핵심이다.
문제를 작은 문제로 나누어 풀고 그 해로 원래 문제의 해를 구하는 것은 옳은 설명이다.
최적의 해가 부분 문제의 최적해로 구성된다는 최적성의 원리가 성립해야 적용할 수 있다.

문제 3

스택(stack)의 특징에 대한 설명으로 옳지 않은 것은?

1나중에 들어온 데이터가 먼저 나가는 후입 선출 구조(LIFO, Last-In First-Out)로 입출력이 일어난다.

2제일 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조로 되어 있다.

3함수 호출에서 복귀주소를 기억하는 데 스택을 사용하고, 함수는 수행이 끝나면 최근에 자신을 호출한 함수로 돌아간다.

4push 연산은 스택에서 하나의 요소를 제거하는 연산으로 top이 가리키는 요소를 스택에서 꺼내서 외부로 건네주는 연산이다.

정답 및 해설

옳지 않은 것은 push를 요소를 제거하는 연산으로 설명한 것이다.

스택에서 top의 요소를 꺼내 외부로 건네주는 연산은 pop이고, push는 top 위치에 새 요소를 삽입하는 연산이다.

나중에 들어온 데이터가 먼저 나가는 후입 선출(LIFO) 구조는 스택의 정의이다.
먼저 들어온 데이터가 맨 아래, 최근 데이터가 맨 위에 쌓이는 구조라는 설명은 옳다.
함수 호출 시 복귀 주소를 스택에 저장해 가장 최근 호출한 함수로 돌아가는 것도 옳다.

문제 4

다음 중 안정적 정렬(stable sort) 알고리즘에 해당하는 것만을 모두 고르면?

ㄱ. 버블 정렬(bubble sort)
ㄴ. 힙 정렬(heap sort)
ㄷ. 삽입 정렬(insertion sort)
ㄹ. 계수 정렬(counting sort)

1ㄴ, ㄷ

2ㄴ, ㄹ

3ㄱ, ㄴ, ㄷ

4ㄱ, ㄷ, ㄹ

정답 및 해설

안정적 정렬에 해당하는 것은 버블 정렬, 삽입 정렬, 계수 정렬이다.

안정적 정렬은 키가 같은 원소들의 입력 순서가 정렬 후에도 유지되는 정렬이다. 인접 원소만 교환하거나 뒤에서부터 같은 키를 차례로 배치하면 순서가 유지된다.

버블 정렬은 인접한 두 원소가 더 클 때만 교환하므로 같은 키의 순서가 바뀌지 않는다.
삽입 정렬은 key보다 큰 원소만 뒤로 밀기 때문에 안정적이다.
계수 정렬은 누적 개수 배열을 이용해 입력을 뒤에서부터 배치하면 안정적이다.
힙 정렬은 루트와 마지막 원소를 맞바꾸는 과정에서 같은 키의 순서가 뒤바뀔 수 있어 불안정하다.

문제 5

다음 이진 트리(binary tree)의 단말 노드(leaf node) 개수와 간선(edge) 개수는?

단말 노드 개수　　간선 개수

13　　7

23　　8

34　　7

44　　8

정답 및 해설

이 트리의 단말 노드는 4개, 간선은 7개이다.

자식이 없는 노드는 D, G, H, F의 4개이다. 트리는 노드가 n개이면 간선이 n − 1개이므로, 노드 A~H의 8개에서 간선은 7개가 된다.

단말 노드 3개: E는 자식 G, H를 가진 내부 노드이므로 단말이 아니고, 단말 노드는 4개이다.
간선 8개: 간선 수를 노드 수와 같게 센 것이며, 트리에는 사이클이 없으므로 간선은 노드 수보다 하나 적다.

문제 6

다음 설명에 해당하는 알고리즘 기법은?

○ 깊이 우선 탐색(DFS, Depth First Search)이 기본 골격이다.
○ 해를 찾는 도중에 해가 아니면 되돌아가서 다시 해를 탐색한다.
○ 최적화(optimization) 문제와 결정(decision) 문제를 해결할 수 있다.

1백 트래킹(back tracking)

2k-NN(k-Nearest Neighbors)

3그리디(greedy) 알고리즘

4분할 정복(divide-and-conquer) 알고리즘

정답 및 해설

설명에 해당하는 기법은 백트래킹이다.

백트래킹은 상태 공간 트리를 깊이 우선 탐색하다가 해가 될 가능성이 없는 노드를 만나면 부모로 되돌아가 다른 경로를 탐색하며, 결정 문제와 최적화 문제 모두에 쓰인다.

k-NN은 가장 가까운 k개의 이웃으로 분류·회귀를 하는 기계학습 기법으로 되돌아가는 탐색과 무관하다.
그리디 알고리즘은 매 순간 최선의 선택을 하고 되돌아가지 않는다.
분할 정복은 문제를 독립적인 부분 문제로 나누어 풀고 결합하는 기법이다.

문제 7

다음 중 문자열 매칭 알고리즘에 해당하는 것만을 모두 고르면?

ㄱ. 벨만 포드(Bellman Ford)
ㄴ. 보이어－무어(Boyer-Moore)
ㄷ. 다익스트라(Dijkstra)
ㄹ. KMP(Knuth, Morris, Pratt)

1ㄱ, ㄴ

2ㄱ, ㄷ

3ㄴ, ㄷ

4ㄴ, ㄹ

정답 및 해설

문자열 매칭 알고리즘은 보이어-무어와 KMP이다.

두 알고리즘 모두 텍스트에서 패턴을 찾을 때 미리 계산한 정보를 이용해 비교 위치를 건너뛰어 단순 비교보다 빠르게 매칭한다.

보이어-무어는 패턴을 오른쪽부터 비교하며 불일치 문자·접미부 정보로 크게 이동한다.
KMP는 실패 함수(접두부와 접미부 일치 정보)로 텍스트 포인터를 되돌리지 않는다.
벨만-포드는 음수 간선을 허용하는 단일 출발점 최단 경로 알고리즘이다.
다익스트라는 음이 아닌 가중치 그래프의 단일 출발점 최단 경로 알고리즘이다.

문제 8

다음 그래프에서 정점 A부터 깊이 우선 탐색을 수행할 때 가능한 정점들의 방문 순서로 옳은 것은?

1A → B → E → F → D → C

2A → B → D → C → E → F

3A → D → B → E → F → C

4A → D → F → E → B → C

정답 및 해설

가능한 깊이 우선 탐색 순서는 A → D → B → E → F → C이다.

그래프의 간선은 A-B, A-C, A-D, B-D, B-E, D-F, C-F이다. A에서 D, D에서 B, B에서 E로 내려가면 E는 더 갈 곳이 없어 B로, B도 미방문 이웃이 없어 D로 되돌아간다. D의 미방문 이웃 F로 간 뒤 F에서 C를 방문하면 탐색이 끝난다.

A → B → E → F → D → C: E에서 되돌아간 B에 미방문 이웃 D가 남아 있으므로 D를 방문해야 하며, F는 E·B 어느 쪽과도 인접하지 않다.
A → B → D → C → E → F: D에는 미방문 이웃 F가 있는데 D와 인접하지 않은 C로 넘어갈 수 없다.
A → D → F → E → B → C: F의 이웃은 D와 C뿐이므로 F 다음에 E를 방문할 수 없다.

문제 9

다음 그래프에 대해 정점 A를 시작으로 프림(Prim) 알고리즘을 수행했을 때, 생성된 최소 신장 트리의 간선 개수는?

14개

25개

36개

47개

정답 및 해설

생성된 최소 신장 트리의 간선은 5개이다.

신장 트리는 모든 정점을 사이클 없이 연결하므로 정점이 n개이면 간선은 n − 1개이다. 그래프의 정점은 A~F의 6개이므로 간선은 5개가 된다.

실제로 A에서 프림 알고리즘을 수행하면 A-B(2), B-F(1), B-E(3), E-D(2), B-C(4)를 차례로 선택해 총 가중치 12의 트리가 만들어진다.

4개: 간선이 4개이면 정점 6개를 모두 연결할 수 없다.
6개: 정점 6개에 간선을 5개보다 많이 두면 반드시 사이클이 생겨 트리가 아니다.
7개: 간선 수를 정점 수보다 크게 센 것으로, 정점 6개의 신장 트리는 간선이 항상 5개로 고정된다.

문제 10

다음 설명에 해당하는 정렬 알고리즘은?

○ 배열을 정렬된 앞부분과 정렬되지 않은 뒷부분으로 나누어 처리한다.
○ 최선의 경우 시간 복잡도는

O(n)

이며 최악의 경우 시간 복잡도는

O(n^2)

이다.

1삽입 정렬

2버블 정렬

3병합(merge) 정렬

4선택(selection) 정렬

정답 및 해설

설명에 해당하는 정렬은 삽입 정렬이다.

삽입 정렬은 앞부분을 정렬된 상태로 유지하며 뒷부분의 원소를 하나씩 알맞은 위치에 끼워 넣는다. 이미 정렬된 입력이면 원소마다 비교 한 번으로 끝나 최선 $O(n)$ , 역순이면 최악 $O(n^2)$ 이다.

버블 정렬은 인접 원소 교환으로 큰 값을 뒤로 보내며, 정렬된 뒷부분을 만드는 방식이다.
병합 정렬은 분할 정복으로 최선·최악 모두 $O(n\log n)$ 이다.
선택 정렬은 입력 상태와 관계없이 최솟값을 찾으므로 최선의 경우에도 $O(n^2)$ 이다.

문제 11

다음 B－트리에 “50”을 삽입할 때의 설명으로 옳지 않은 것은? (단, 각 노드는 최대 4개의 키를 가질 수 있다)

150이 루트 노드가 된다.

2모든 리프 노드의 레벨은 동일하다.

350을 삽입하면 오버플로우가 발생한다.

450을 삽입할 때 분할(split) 연산이 필요하다.

정답 및 해설

50을 삽입한 뒤 새 루트가 되는 키는 20이므로 50이 루트 노드가 된다는 설명이 옳지 않다.

50은 루트의 20과 60 사이 자식인 리프 [21, 25, 30, 45]에 들어가 키가 5개가 되므로 오버플로가 발생한다. 이 리프를 분할하면 중간 키 30이 루트로 올라가고, 루트는 [3, 7, 20, 30, 60]이 되어 다시 오버플로가 난다.

루트를 분할하면 중간 키 20이 새 루트가 되고, 50은 리프 [45, 50]에 남는다.

모든 리프 노드의 레벨은 동일하다: B-트리는 루트 분할로만 높이가 늘어나므로 모든 리프가 같은 레벨을 유지한다.
50을 삽입하면 오버플로우가 발생한다: 대상 리프에 키가 이미 4개 있어서 5개째가 들어가면 최대 키 수를 넘는다.
50을 삽입할 때 분할 연산이 필요하다: 오버플로를 해소하려면 리프와 루트에서 차례로 분할해야 한다.

문제 12

다음 C언어 함수를 이용하여 rec(5)를 수행한 결괏값은?

int rec(int n) {
    if (n <= 0)
        return 0;
    else if (n <= 3)
        return n;
    else
        return rec(n-4) + rec(n-3) + rec(n-2) + rec(n-1);
}

210

312

415

정답 및 해설

rec(5)의 결괏값은 12이다.

n이 1~3이면 n을, 0 이하이면 0을 반환하므로 rec(4)부터 구한다.
rec(4) = rec(0) + rec(1) + rec(2) + rec(3) = 0 + 1 + 2 + 3 = 6

rec(5) = rec(1) + rec(2) + rec(3) + rec(4) = 1 + 2 + 3 + 6 = 12

문제 13

배열 A = [5, 2, 4, 6, 1, 3]를 삽입 정렬로 오름차순 정렬할 때, 전체 과정에서 수행되는 key 값의 총 비교 횟수는? (단, 알고리즘은 다음과 같이 동작한다고 가정하며, 배열의 인덱스는 1부터 시작하고, n 값은 배열 A의 원소의 개수이다)

for i ← 2 to n do
    key ← A[i]
    j ← i - 1
    while j ≥ 1 and A[j] > key do
        A[j+1] ← A[j]
        j ← j - 1
    A[j+1] ← key

112

213

314

415

정답 및 해설

key 값의 총 비교 횟수는 12회이다.

비교는 while 조건의 A[j] > key 가 평가될 때마다 1회이며, j가 0이 되면 비교 없이 종료된다.
i=2(key 2): 5와 비교 → 1회, [2,5,4,6,1,3]
i=3(key 4): 5, 2와 비교 → 2회, [2,4,5,6,1,3]
i=4(key 6): 5와 비교 → 1회
i=5(key 1): 6, 5, 4, 2와 비교 후 j=0 → 4회, [1,2,4,5,6,3]
i=6(key 3): 6, 5, 4, 2와 비교 → 4회

합계: 1 + 2 + 1 + 4 + 4 = 12

문제 14

위상 정렬(topological sort)에 대한 설명으로 옳은 것은?

1깊이 우선 탐색 방식을 이용해서는 구현할 수 없다.

2하나의 그래프에 한 개의 위상 정렬만 존재한다.

3사이클이 없는 모든 종류의 그래프에 적용할 수 있다.

4간선 <i, j>를 가질 때 정점 i는 정점 j를 선행한다.

정답 및 해설

옳은 설명은 간선 <i, j>가 있으면 정점 i가 정점 j를 선행한다는 것이다.

위상 정렬은 방향 비순환 그래프(DAG)의 정점을 모든 간선 i→j에 대해 i가 j보다 앞에 오도록 나열하는 것이다.

DFS의 종료 순서를 역순으로 나열하는 방식으로 위상 정렬을 구현할 수 있다.
선후 관계가 없는 정점들의 순서는 바꿀 수 있으므로 위상 정렬 결과는 여러 개 존재할 수 있다.
사이클이 없어도 무방향 그래프에는 선행 관계가 없으므로 적용할 수 없고, 방향 그래프에만 적용된다.

문제 15

다음 파이썬 프로그램의 실행 결과는?

def search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target: return mid
        elif arr[mid] < target: low = mid + 1
        else: high = mid - 1
    return -1

if __name__ == "__main__":
    a = [2, 5, 8, 12, 16, 23, 38, 56, 91]
    print(search(a, 23))

1－1

정답 및 해설

프로그램은 23이 저장된 인덱스인 5를 출력한다.

이진 탐색 추적(배열 인덱스 0~8):
low=0, high=8 → mid=4, a[4]=16 < 23 → low=5
low=5, high=8 → mid=6, a[6]=38 > 23 → high=5
low=5, high=5 → mid=5, a[5]=23 → 반환

23은 배열에 존재하므로 -1이 출력되지 않고, 탐색 결과 인덱스 5가 출력된다.

문제 16

다음은 어떤 문자열에 포함된 문자들의 빈도수를 나타낸 표이다. 허프만(Huffman) 코드를 적용하여 인코딩한 결과의 비트 수는?

문자	a	b	c	d	e	f
빈도수	7	20	10	5	50	6

198

2202

3300

4331

정답 및 해설

허프만 코드로 인코딩한 전체 비트 수는 202이다.

빈도가 가장 작은 두 노드를 반복해서 합친다.
5(d) + 6(f) = 11
7(a) + 10(c) = 17
11 + 17 = 28
20(b) + 28 = 48
48 + 50(e) = 98

총 비트 수는 각 문자 빈도 × 코드 길이의 합이며, 이는 합쳐서 생긴 내부 노드 값의 합과 같다.
11 + 17 + 28 + 48 + 98 = 202
(검산: e 50×1 + b 20×2 + a·c·d·f (7+10+5+6)×4 = 50 + 40 + 112 = 202)

문제 17

기수 정렬(radix sort)에 대한 설명으로 옳은 것만을 모두 고르면?

ㄱ. 비교 기반의 정렬 알고리즘이다.
ㄴ. 저장공간이 추가로 필요하다.
ㄷ. 안정적 정렬(stable sort) 알고리즘이다.
ㄹ. 시간 복잡도는

O(n\log n)

이다.

1ㄱ, ㄷ

2ㄴ, ㄷ

3ㄴ, ㄹ

4ㄷ, ㄹ

정답 및 해설

기수 정렬에 대한 옳은 설명은 추가 저장공간이 필요하다는 것과 안정적 정렬이라는 것이다.

기수 정렬은 키를 자릿수별로 나누어 각 자릿수에 대해 버킷(또는 계수 정렬)으로 분배하는 방식이며, 하위 자릿수 결과를 보존하려면 각 단계의 정렬이 안정적이어야 한다.

원소끼리 크기를 비교하지 않고 자릿수 값으로 분배하므로 비교 기반 정렬이 아니다.
자릿수가 d, 기수가 k이면 시간 복잡도는 $O(d(n+k))$ 로, 비교 정렬의 하한인 $O(n\log n)$ 이 아니라 선형 시간에 가깝다.

문제 18

다음은 0 이상의 모든 정수 n에 대하여

n!

을 구하는 파이썬 코드이다. (가)에 들어갈 코드로 옳지 않은 것은?

def factorial(n):
    if  (가)  :
        return 1
    return n * factorial(n - 1)

1n == 0

2n <= 0

3n == 1

4n <= 1

정답 및 해설

(가)에 들어갈 코드로 옳지 않은 것은 n == 1이다.

0 이상의 모든 n을 처리하려면 n=0일 때 1을 반환하는 종료 조건이 필요하다. n == 1만 종료 조건이면 factorial(0)이 factorial(-1), factorial(-2), …로 끝없이 호출되어 재귀가 종료되지 않는다.

n == 0은 0!=1을 반환하고, 1 이상은 0까지 내려와 종료되므로 옳다.
n <= 0도 n=0에서 1을 반환하므로 옳다.
n <= 1은 0과 1 모두에서 1을 반환하며 0!=1!=1이므로 옳다.

문제 19

다음 파이썬 프로그램의 실행 결과는?

cnt = 0
class Node:
    def __init__(self,key,h,lf = None,rg = None):
        self.key = key
        self.h = h
        self.lf = lf
        self.rg = rg
class TREE:
    def __init__(self):
        self.r = None
    def h(self, n):
        if n == None:
            return 0
        return n.h
    def put(self, key):
        self.r = self.putitem(self.r,key)
    def putitem(self, n, key):
        if n == None:
            return Node(key, 1)
        if n.key > key:
            n.lf = self.putitem(n.lf,key)
        elif n.key < key:
            n.rg = self.putitem(n.rg,key)
        else:
            return n
        n.h = max(self.h(n.lf),self.h(n.rg)) + 1
        return self.bal(n)
    def bal(self, n):
        global cnt
        if self.bf(n) > 1:
            if self.bf(n.lf) < 0:
                n.lf = self.lf(n.lf)
                cnt += 1
            n = self.rg(n)
            cnt += 1
        elif self.bf(n) < -1:
            if self.bf(n.rg) > 0:
                n.rg = self.rg(n.rg)
                cnt += 1
            n = self.lf(n)
            cnt += 1
        return n
    def rg(self, j):
        i = j.lf
        j.lf = i.rg
        i.rg = j
        j.h = max(self.h(j.lf),self.h(j.rg)) + 1
        i.h = max(self.h(i.lf),self.h(i.rg)) + 1
        return i
    def lf(self, j):
        i = j.rg
        j.rg = i.lf
        i.lf = j
        j.h = max(self.h(j.lf),self.h(j.rg)) + 1
        i.h = max(self.h(i.lf),self.h(i.rg)) + 1
        return i
    def bf(self, n):
        return self.h(n.lf) - self.h(n.rg)
if __name__ == '__main__':
    t = TREE()
    value = [5, 22, 3, 14, 2, 19]
    for i in value:
        t.put(i)
    print(cnt)

정답 및 해설

프로그램은 회전 횟수 2를 출력한다.

코드는 AVL 트리이며, 메서드 rg는 오른쪽 회전, lf는 왼쪽 회전이고 회전 1회마다 cnt가 1 증가한다.
5, 22, 3, 14, 2 삽입: 모든 노드의 균형 인수가 -1~1 범위여서 회전 없음 → 5(왼쪽 3[2], 오른쪽 22[왼쪽 14])

19 삽입: 22 → 14의 오른쪽에 들어가 노드 22의 균형 인수가 2, 왼쪽 자식 14의 균형 인수가 -1이 된다.
LR 경우이므로 14에서 왼쪽 회전(cnt=1) 후 22에서 오른쪽 회전(cnt=2) → 5(왼쪽 3[2], 오른쪽 19[14, 22])

따라서 최종 출력은 2이다.

문제 20

그래프의 임의의 한 점에서 출발하여 다른 모든 점을 한 번씩만 방문하고, 다시 시작점으로 돌아오는 경로 중 최단 경로를 찾는 문제는?

1통 채우기(bin packing) 문제

2정점 커버(vertex cover) 문제

3그래프 색칠하기(graph coloring) 문제

4여행자 문제(TSP, Traveling Salesman Problem)

정답 및 해설

모든 정점을 한 번씩 방문하고 출발점으로 돌아오는 최단 경로 문제는 여행자 문제(TSP)이다.

TSP는 최소 비용 해밀턴 순환을 찾는 문제로, 대표적인 NP-하드 최적화 문제이다.

통 채우기 문제는 크기가 다른 물건을 최소 개수의 통에 담는 문제이다.
정점 커버 문제는 모든 간선의 끝점 중 하나 이상을 포함하는 최소 정점 집합을 찾는 문제이다.
그래프 색칠하기 문제는 인접한 정점이 다른 색이 되도록 최소 색 수로 칠하는 문제이다.

문제 21

수행 시간 분석(run time analysis)에 관한 설명으로 옳지 않은 것은?

1최악 경우(worst case) 분석은 상한의 의미가 있다.

2최선 경우(best case) 분석은 수행 시간이 가장 적은 경우를 의미한다.

3평균 경우(average case) 분석은 모든 입력에 대한 수행 시간을 알고 계산하기 때문에 시간 복잡도의 척도로 많이 사용한다.

4상각(amortized) 분석은 일련의 연산을 수행하는 데 걸리는 총 시간을 연산 수로 나누어 계산한다.

정답 및 해설

옳지 않은 것은 평균 경우 분석이 모든 입력의 수행 시간을 알고 계산하므로 많이 사용된다는 설명이다.

평균 경우 분석은 입력의 확률 분포를 가정해야 하고 계산이 어려워 실제로는 덜 쓰이며, 성능을 보장하는 최악 경우 분석이 시간 복잡도의 척도로 가장 많이 사용된다.

최악 경우 분석은 어떤 입력에도 그 이상 걸리지 않는다는 상한의 의미를 가진다.
최선 경우 분석은 수행 시간이 가장 적게 걸리는 입력에 대한 분석이다.
상각 분석은 일련의 연산 전체 시간을 연산 수로 나누어 연산당 평균 비용을 구한다.

문제 22

문제를 해결하기 위한 알고리즘 개발 단계를 순서대로 바르게 나열한 것은?

(가) 알고리즘 구현
(나) 알고리즘 설계
(다) 알고리즘 분석
(라) 알고리즘 정확성 검증

1(나) → (다) → (라) → (가)

2(나) → (라) → (다) → (가)

3(다) → (나) → (라) → (가)

4(다) → (라) → (나) → (가)

정답 및 해설

알고리즘 개발 단계는 설계 → 정확성 검증 → 분석 → 구현 순서이다.

먼저 문제를 해결할 절차를 설계하고, 그 절차가 모든 입력에 대해 올바른 결과를 내는지 정확성을 검증한 뒤, 시간·공간 효율을 분석하고, 마지막으로 프로그래밍 언어로 구현한다.

분석은 정확성이 검증된 알고리즘을 대상으로 하므로 정확성 검증보다 앞설 수 없다.
설계되지 않은 알고리즘은 분석할 대상이 없으므로 분석이 설계보다 먼저 올 수 없다.

문제 23

그리디 알고리즘에 해당하는 것은?

1크루스칼(Kruskal) 알고리즘

20/1 배낭(knapsack) 문제 풀이

3플로이드－워셜(Floyd-Warshall) 알고리즘

4최장 공통 부분 수열(LCS, Longest Common Subsequence) 구하기

정답 및 해설

그리디 알고리즘에 해당하는 것은 크루스칼 알고리즘이다.

크루스칼 알고리즘은 사이클을 만들지 않는 범위에서 가중치가 가장 작은 간선을 매번 선택해 최소 신장 트리를 만드는 탐욕적 선택 방식이다.

0/1 배낭 문제는 물건을 쪼갤 수 없어 그리디로 최적해가 보장되지 않으며 동적 계획법으로 푼다.
플로이드-워셜 알고리즘은 경유 정점을 하나씩 늘려 가는 동적 계획법이다.
최장 공통 부분 수열은 부분 문제 표를 채우는 동적 계획법으로 구한다.

문제 24

정렬 알고리즘에 대한 설명으로 옳은 것은?

1힙 정렬의 시간 복잡도는

O(n^2)

이다.

2퀵 정렬은 정렬할 전체 원소에 대해 정렬을 수행한 후 기준값을 중심으로 왼쪽 부분집합과 오른쪽 부분집합으로 분할한다.

3삽입 정렬은 입력에 민감한 알고리즘으로, 입력이 거의 정렬되어 있을 때 처리시간이 느리고, 입력이 역으로 정렬되어 있을 때는 최선의 경우로 빠르다.

4병합 정렬은 크기가 n인 입력을 n/2 크기로 분할하고, 각각에 대해 같은 방식으로 정렬을 수행한 후, 2개의 각각 정렬된 부분을 합병한다.

정답 및 해설

옳은 설명은 병합 정렬이 입력을 절반으로 분할해 각각 정렬한 뒤 합병한다는 것이다.

병합 정렬은 분할 정복 알고리즘으로, 분할 깊이 $\log n$ 단계마다 $O(n)$ 합병을 하므로 $O(n\log n)$ 이다.

힙 정렬은 최악의 경우에도 $O(n\log n)$ 이다.
퀵 정렬은 정렬을 먼저 하는 것이 아니라, 기준값으로 먼저 분할한 뒤 각 부분집합을 재귀적으로 정렬한다.
삽입 정렬은 거의 정렬된 입력에서 빠르고(최선), 역순 입력에서 가장 느리다(최악).

문제 25

다음 파이썬 프로그램의 실행 결과는?

class NodeBS(object):
    def __init__(self, vl = None):
        self.vl = vl
        self.root = None
        self.lf = None
        self.rg = None
    def _ad(self, vl):
        nd = NodeBS(vl)
        if vl > self.vl:
            self.rg = self.rg and self.rg._ad(vl) or nd
        elif vl < self.vl:
            self.lf = self.lf and self.lf._ad(vl) or nd
        else:
            print("node duplicated")
        return self
class Bst(NodeBS):
    def add_node(self, vl):
        if not self.root:
            self.root = NodeBS(vl)
        else:
            self.root._ad(vl)
    def order(self):
        current = self.root
        nodes, stack = [], []
        while stack or current:
            if current:
                nodes.append(current.vl)
                stack.append(current)
                current = current.lf
            else:
                current = stack.pop()
                current = current.rg
        return nodes
if __name__ == "__main__":
    bt = Bst()
    in_list = [6, 4, 8, 2, 5, 7, 9, 1, 3, 10]
    for i in in_list:
        bt.add_node(i)
    print(bt.order())

1[6, 4, 2, 1, 3, 8, 5, 7, 9, 10]

2[6, 4, 2, 1, 5, 8, 3, 7, 9, 10]

3[6, 4, 2, 1, 3, 5, 8, 7, 9, 10]

4[6, 4, 2, 1, 5, 3, 8, 7, 9, 10]

정답 및 해설

프로그램은 이진 탐색 트리의 전위 순회 결과 [6, 4, 2, 1, 3, 5, 8, 7, 9, 10]을 출력한다.

삽입 결과 트리: 6의 왼쪽 4, 오른쪽 8 / 4의 왼쪽 2, 오른쪽 5 / 2의 왼쪽 1, 오른쪽 3 / 8의 왼쪽 7, 오른쪽 9 / 9의 오른쪽 10

order()는 노드를 방문하자마자 nodes에 추가하고 왼쪽으로 내려가며, 더 갈 곳이 없으면 스택에서 꺼낸 노드의 오른쪽으로 이동한다. 즉 루트 → 왼쪽 → 오른쪽 순서이다.
6 → 4 → 2 → 1 → 3 → 5 → 8 → 7 → 9 → 10

7급 국가직 알고리즘 기출문제모두CBT · moducbt.com

26년 1회차

총 25문항 · 객관식 · 정답·해설 포함

문제 1

다음 중 레드－블랙 트리(red-black tree)의 특성으로 옳은 것만을 모두 고르면?

ㄱ. 모든 노드는 레드 또는 블랙이다.
ㄴ. 루트 노드는 레드이다.
ㄷ. 레드 노드의 자식 노드는 항상 블랙이다.
ㄹ. 모든 리프 노드(NIL)는 레드이다.

1ㄱ, ㄴ

2ㄱ, ㄷ

3ㄴ, ㄷ

4ㄷ, ㄹ

정답 및 해설

레드-블랙 트리의 특성으로 옳은 것은 모든 노드가 레드 또는 블랙이라는 것과 레드 노드의 자식은 항상 블랙이라는 것이다.

레드-블랙 트리는 색 규칙(루트·NIL 리프는 블랙, 레드 노드 연속 금지, 루트에서 각 NIL까지 블랙 노드 수 동일)으로 높이를 $O(\log n)$ 로 유지한다.

루트 노드는 레드가 아니라 블랙이어야 한다.
모든 리프 노드(NIL)도 레드가 아니라 블랙이다.

문제 2

동적 계획법(dynamic programming)에 대한 설명으로 옳지 않은 것은?

1부분 문제들 사이에는 의존적 관계가 없다.

2동일한 부분 문제들을 다시 풀지 않도록 하기 위해 부분 문제들의 해를 저장한다.

3주어진 문제를 작은 문제로 나누어 해결하고 이를 이용하여 원래 문제의 해를 도출한다.

4이 기법을 적용할 수 있으려면 최적성의 원리(principle of optimality)가 성립하여야 한다.

정답 및 해설

동적 계획법에서 부분 문제들 사이에 의존 관계가 없다는 설명은 옳지 않다.

부분 문제의 해를 테이블에 저장해 다시 풀지 않는 것은 동적 계획법의 핵심이다.
문제를 작은 문제로 나누어 풀고 그 해로 원래 문제의 해를 구하는 것은 옳은 설명이다.
최적의 해가 부분 문제의 최적해로 구성된다는 최적성의 원리가 성립해야 적용할 수 있다.

문제 3

스택(stack)의 특징에 대한 설명으로 옳지 않은 것은?

1나중에 들어온 데이터가 먼저 나가는 후입 선출 구조(LIFO, Last-In First-Out)로 입출력이 일어난다.

2제일 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조로 되어 있다.

3함수 호출에서 복귀주소를 기억하는 데 스택을 사용하고, 함수는 수행이 끝나면 최근에 자신을 호출한 함수로 돌아간다.

4push 연산은 스택에서 하나의 요소를 제거하는 연산으로 top이 가리키는 요소를 스택에서 꺼내서 외부로 건네주는 연산이다.

정답 및 해설

옳지 않은 것은 push를 요소를 제거하는 연산으로 설명한 것이다.

스택에서 top의 요소를 꺼내 외부로 건네주는 연산은 pop이고, push는 top 위치에 새 요소를 삽입하는 연산이다.

나중에 들어온 데이터가 먼저 나가는 후입 선출(LIFO) 구조는 스택의 정의이다.
먼저 들어온 데이터가 맨 아래, 최근 데이터가 맨 위에 쌓이는 구조라는 설명은 옳다.
함수 호출 시 복귀 주소를 스택에 저장해 가장 최근 호출한 함수로 돌아가는 것도 옳다.

문제 4

다음 중 안정적 정렬(stable sort) 알고리즘에 해당하는 것만을 모두 고르면?

ㄱ. 버블 정렬(bubble sort)
ㄴ. 힙 정렬(heap sort)
ㄷ. 삽입 정렬(insertion sort)
ㄹ. 계수 정렬(counting sort)

1ㄴ, ㄷ

2ㄴ, ㄹ

3ㄱ, ㄴ, ㄷ

4ㄱ, ㄷ, ㄹ

정답 및 해설

안정적 정렬에 해당하는 것은 버블 정렬, 삽입 정렬, 계수 정렬이다.

버블 정렬은 인접한 두 원소가 더 클 때만 교환하므로 같은 키의 순서가 바뀌지 않는다.
삽입 정렬은 key보다 큰 원소만 뒤로 밀기 때문에 안정적이다.
계수 정렬은 누적 개수 배열을 이용해 입력을 뒤에서부터 배치하면 안정적이다.
힙 정렬은 루트와 마지막 원소를 맞바꾸는 과정에서 같은 키의 순서가 뒤바뀔 수 있어 불안정하다.

문제 5

다음 이진 트리(binary tree)의 단말 노드(leaf node) 개수와 간선(edge) 개수는?

단말 노드 개수　　간선 개수

13　　7

23　　8

34　　7

44　　8

정답 및 해설

이 트리의 단말 노드는 4개, 간선은 7개이다.

자식이 없는 노드는 D, G, H, F의 4개이다. 트리는 노드가 n개이면 간선이 n − 1개이므로, 노드 A~H의 8개에서 간선은 7개가 된다.

단말 노드 3개: E는 자식 G, H를 가진 내부 노드이므로 단말이 아니고, 단말 노드는 4개이다.
간선 8개: 간선 수를 노드 수와 같게 센 것이며, 트리에는 사이클이 없으므로 간선은 노드 수보다 하나 적다.

문제 6

다음 설명에 해당하는 알고리즘 기법은?

1백 트래킹(back tracking)

2k-NN(k-Nearest Neighbors)

3그리디(greedy) 알고리즘

4분할 정복(divide-and-conquer) 알고리즘

정답 및 해설

설명에 해당하는 기법은 백트래킹이다.

k-NN은 가장 가까운 k개의 이웃으로 분류·회귀를 하는 기계학습 기법으로 되돌아가는 탐색과 무관하다.
그리디 알고리즘은 매 순간 최선의 선택을 하고 되돌아가지 않는다.
분할 정복은 문제를 독립적인 부분 문제로 나누어 풀고 결합하는 기법이다.

문제 7

다음 중 문자열 매칭 알고리즘에 해당하는 것만을 모두 고르면?

ㄱ. 벨만 포드(Bellman Ford)
ㄴ. 보이어－무어(Boyer-Moore)
ㄷ. 다익스트라(Dijkstra)
ㄹ. KMP(Knuth, Morris, Pratt)

1ㄱ, ㄴ

2ㄱ, ㄷ

3ㄴ, ㄷ

4ㄴ, ㄹ

정답 및 해설

문자열 매칭 알고리즘은 보이어-무어와 KMP이다.

두 알고리즘 모두 텍스트에서 패턴을 찾을 때 미리 계산한 정보를 이용해 비교 위치를 건너뛰어 단순 비교보다 빠르게 매칭한다.

보이어-무어는 패턴을 오른쪽부터 비교하며 불일치 문자·접미부 정보로 크게 이동한다.
KMP는 실패 함수(접두부와 접미부 일치 정보)로 텍스트 포인터를 되돌리지 않는다.
벨만-포드는 음수 간선을 허용하는 단일 출발점 최단 경로 알고리즘이다.
다익스트라는 음이 아닌 가중치 그래프의 단일 출발점 최단 경로 알고리즘이다.

문제 8

다음 그래프에서 정점 A부터 깊이 우선 탐색을 수행할 때 가능한 정점들의 방문 순서로 옳은 것은?

1A → B → E → F → D → C

2A → B → D → C → E → F

3A → D → B → E → F → C

4A → D → F → E → B → C

정답 및 해설

가능한 깊이 우선 탐색 순서는 A → D → B → E → F → C이다.

A → B → E → F → D → C: E에서 되돌아간 B에 미방문 이웃 D가 남아 있으므로 D를 방문해야 하며, F는 E·B 어느 쪽과도 인접하지 않다.
A → B → D → C → E → F: D에는 미방문 이웃 F가 있는데 D와 인접하지 않은 C로 넘어갈 수 없다.
A → D → F → E → B → C: F의 이웃은 D와 C뿐이므로 F 다음에 E를 방문할 수 없다.

문제 9

다음 그래프에 대해 정점 A를 시작으로 프림(Prim) 알고리즘을 수행했을 때, 생성된 최소 신장 트리의 간선 개수는?

14개

25개

36개

47개

정답 및 해설

생성된 최소 신장 트리의 간선은 5개이다.

신장 트리는 모든 정점을 사이클 없이 연결하므로 정점이 n개이면 간선은 n − 1개이다. 그래프의 정점은 A~F의 6개이므로 간선은 5개가 된다.

실제로 A에서 프림 알고리즘을 수행하면 A-B(2), B-F(1), B-E(3), E-D(2), B-C(4)를 차례로 선택해 총 가중치 12의 트리가 만들어진다.

4개: 간선이 4개이면 정점 6개를 모두 연결할 수 없다.
6개: 정점 6개에 간선을 5개보다 많이 두면 반드시 사이클이 생겨 트리가 아니다.
7개: 간선 수를 정점 수보다 크게 센 것으로, 정점 6개의 신장 트리는 간선이 항상 5개로 고정된다.

문제 10

다음 설명에 해당하는 정렬 알고리즘은?

○ 배열을 정렬된 앞부분과 정렬되지 않은 뒷부분으로 나누어 처리한다.
○ 최선의 경우 시간 복잡도는

O(n)

이며 최악의 경우 시간 복잡도는

O(n^2)

이다.

1삽입 정렬

2버블 정렬

3병합(merge) 정렬

4선택(selection) 정렬

정답 및 해설

설명에 해당하는 정렬은 삽입 정렬이다.

버블 정렬은 인접 원소 교환으로 큰 값을 뒤로 보내며, 정렬된 뒷부분을 만드는 방식이다.
병합 정렬은 분할 정복으로 최선·최악 모두 $O(n\log n)$ 이다.
선택 정렬은 입력 상태와 관계없이 최솟값을 찾으므로 최선의 경우에도 $O(n^2)$ 이다.

문제 11

다음 B－트리에 “50”을 삽입할 때의 설명으로 옳지 않은 것은? (단, 각 노드는 최대 4개의 키를 가질 수 있다)

150이 루트 노드가 된다.

2모든 리프 노드의 레벨은 동일하다.

350을 삽입하면 오버플로우가 발생한다.

450을 삽입할 때 분할(split) 연산이 필요하다.

정답 및 해설

50을 삽입한 뒤 새 루트가 되는 키는 20이므로 50이 루트 노드가 된다는 설명이 옳지 않다.

루트를 분할하면 중간 키 20이 새 루트가 되고, 50은 리프 [45, 50]에 남는다.

모든 리프 노드의 레벨은 동일하다: B-트리는 루트 분할로만 높이가 늘어나므로 모든 리프가 같은 레벨을 유지한다.
50을 삽입하면 오버플로우가 발생한다: 대상 리프에 키가 이미 4개 있어서 5개째가 들어가면 최대 키 수를 넘는다.
50을 삽입할 때 분할 연산이 필요하다: 오버플로를 해소하려면 리프와 루트에서 차례로 분할해야 한다.

문제 12

다음 C언어 함수를 이용하여 rec(5)를 수행한 결괏값은?

int rec(int n) {
    if (n <= 0)
        return 0;
    else if (n <= 3)
        return n;
    else
        return rec(n-4) + rec(n-3) + rec(n-2) + rec(n-1);
}

210

312

415

정답 및 해설

rec(5)의 결괏값은 12이다.

n이 1~3이면 n을, 0 이하이면 0을 반환하므로 rec(4)부터 구한다.
rec(4) = rec(0) + rec(1) + rec(2) + rec(3) = 0 + 1 + 2 + 3 = 6

rec(5) = rec(1) + rec(2) + rec(3) + rec(4) = 1 + 2 + 3 + 6 = 12

문제 13

for i ← 2 to n do
    key ← A[i]
    j ← i - 1
    while j ≥ 1 and A[j] > key do
        A[j+1] ← A[j]
        j ← j - 1
    A[j+1] ← key

112

213

314

415

정답 및 해설

key 값의 총 비교 횟수는 12회이다.

합계: 1 + 2 + 1 + 4 + 4 = 12

문제 14

위상 정렬(topological sort)에 대한 설명으로 옳은 것은?

1깊이 우선 탐색 방식을 이용해서는 구현할 수 없다.

2하나의 그래프에 한 개의 위상 정렬만 존재한다.

3사이클이 없는 모든 종류의 그래프에 적용할 수 있다.

4간선 <i, j>를 가질 때 정점 i는 정점 j를 선행한다.

정답 및 해설

옳은 설명은 간선 <i, j>가 있으면 정점 i가 정점 j를 선행한다는 것이다.

위상 정렬은 방향 비순환 그래프(DAG)의 정점을 모든 간선 i→j에 대해 i가 j보다 앞에 오도록 나열하는 것이다.

DFS의 종료 순서를 역순으로 나열하는 방식으로 위상 정렬을 구현할 수 있다.
선후 관계가 없는 정점들의 순서는 바꿀 수 있으므로 위상 정렬 결과는 여러 개 존재할 수 있다.
사이클이 없어도 무방향 그래프에는 선행 관계가 없으므로 적용할 수 없고, 방향 그래프에만 적용된다.

문제 15

다음 파이썬 프로그램의 실행 결과는?

def search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target: return mid
        elif arr[mid] < target: low = mid + 1
        else: high = mid - 1
    return -1

if __name__ == "__main__":
    a = [2, 5, 8, 12, 16, 23, 38, 56, 91]
    print(search(a, 23))

1－1

정답 및 해설

프로그램은 23이 저장된 인덱스인 5를 출력한다.

이진 탐색 추적(배열 인덱스 0~8):
low=0, high=8 → mid=4, a[4]=16 < 23 → low=5
low=5, high=8 → mid=6, a[6]=38 > 23 → high=5
low=5, high=5 → mid=5, a[5]=23 → 반환

23은 배열에 존재하므로 -1이 출력되지 않고, 탐색 결과 인덱스 5가 출력된다.

문제 16

다음은 어떤 문자열에 포함된 문자들의 빈도수를 나타낸 표이다. 허프만(Huffman) 코드를 적용하여 인코딩한 결과의 비트 수는?

문자	a	b	c	d	e	f
빈도수	7	20	10	5	50	6

198

2202

3300

4331

정답 및 해설

허프만 코드로 인코딩한 전체 비트 수는 202이다.

빈도가 가장 작은 두 노드를 반복해서 합친다.
5(d) + 6(f) = 11
7(a) + 10(c) = 17
11 + 17 = 28
20(b) + 28 = 48
48 + 50(e) = 98

문제 17

기수 정렬(radix sort)에 대한 설명으로 옳은 것만을 모두 고르면?

ㄱ. 비교 기반의 정렬 알고리즘이다.
ㄴ. 저장공간이 추가로 필요하다.
ㄷ. 안정적 정렬(stable sort) 알고리즘이다.
ㄹ. 시간 복잡도는

O(n\log n)

이다.

1ㄱ, ㄷ

2ㄴ, ㄷ

3ㄴ, ㄹ

4ㄷ, ㄹ

정답 및 해설

기수 정렬에 대한 옳은 설명은 추가 저장공간이 필요하다는 것과 안정적 정렬이라는 것이다.

원소끼리 크기를 비교하지 않고 자릿수 값으로 분배하므로 비교 기반 정렬이 아니다.
자릿수가 d, 기수가 k이면 시간 복잡도는 $O(d(n+k))$ 로, 비교 정렬의 하한인 $O(n\log n)$ 이 아니라 선형 시간에 가깝다.

문제 18

다음은 0 이상의 모든 정수 n에 대하여

n!

을 구하는 파이썬 코드이다. (가)에 들어갈 코드로 옳지 않은 것은?

def factorial(n):
    if  (가)  :
        return 1
    return n * factorial(n - 1)

1n == 0

2n <= 0

3n == 1

4n <= 1

정답 및 해설

(가)에 들어갈 코드로 옳지 않은 것은 n == 1이다.

n == 0은 0!=1을 반환하고, 1 이상은 0까지 내려와 종료되므로 옳다.
n <= 0도 n=0에서 1을 반환하므로 옳다.
n <= 1은 0과 1 모두에서 1을 반환하며 0!=1!=1이므로 옳다.

문제 19

다음 파이썬 프로그램의 실행 결과는?

cnt = 0
class Node:
    def __init__(self,key,h,lf = None,rg = None):
        self.key = key
        self.h = h
        self.lf = lf
        self.rg = rg
class TREE:
    def __init__(self):
        self.r = None
    def h(self, n):
        if n == None:
            return 0
        return n.h
    def put(self, key):
        self.r = self.putitem(self.r,key)
    def putitem(self, n, key):
        if n == None:
            return Node(key, 1)
        if n.key > key:
            n.lf = self.putitem(n.lf,key)
        elif n.key < key:
            n.rg = self.putitem(n.rg,key)
        else:
            return n
        n.h = max(self.h(n.lf),self.h(n.rg)) + 1
        return self.bal(n)
    def bal(self, n):
        global cnt
        if self.bf(n) > 1:
            if self.bf(n.lf) < 0:
                n.lf = self.lf(n.lf)
                cnt += 1
            n = self.rg(n)
            cnt += 1
        elif self.bf(n) < -1:
            if self.bf(n.rg) > 0:
                n.rg = self.rg(n.rg)
                cnt += 1
            n = self.lf(n)
            cnt += 1
        return n
    def rg(self, j):
        i = j.lf
        j.lf = i.rg
        i.rg = j
        j.h = max(self.h(j.lf),self.h(j.rg)) + 1
        i.h = max(self.h(i.lf),self.h(i.rg)) + 1
        return i
    def lf(self, j):
        i = j.rg
        j.rg = i.lf
        i.lf = j
        j.h = max(self.h(j.lf),self.h(j.rg)) + 1
        i.h = max(self.h(i.lf),self.h(i.rg)) + 1
        return i
    def bf(self, n):
        return self.h(n.lf) - self.h(n.rg)
if __name__ == '__main__':
    t = TREE()
    value = [5, 22, 3, 14, 2, 19]
    for i in value:
        t.put(i)
    print(cnt)

정답 및 해설

프로그램은 회전 횟수 2를 출력한다.

따라서 최종 출력은 2이다.

문제 20

그래프의 임의의 한 점에서 출발하여 다른 모든 점을 한 번씩만 방문하고, 다시 시작점으로 돌아오는 경로 중 최단 경로를 찾는 문제는?

1통 채우기(bin packing) 문제

2정점 커버(vertex cover) 문제

3그래프 색칠하기(graph coloring) 문제

4여행자 문제(TSP, Traveling Salesman Problem)

정답 및 해설

모든 정점을 한 번씩 방문하고 출발점으로 돌아오는 최단 경로 문제는 여행자 문제(TSP)이다.

TSP는 최소 비용 해밀턴 순환을 찾는 문제로, 대표적인 NP-하드 최적화 문제이다.

통 채우기 문제는 크기가 다른 물건을 최소 개수의 통에 담는 문제이다.
정점 커버 문제는 모든 간선의 끝점 중 하나 이상을 포함하는 최소 정점 집합을 찾는 문제이다.
그래프 색칠하기 문제는 인접한 정점이 다른 색이 되도록 최소 색 수로 칠하는 문제이다.

문제 21

수행 시간 분석(run time analysis)에 관한 설명으로 옳지 않은 것은?

1최악 경우(worst case) 분석은 상한의 의미가 있다.

2최선 경우(best case) 분석은 수행 시간이 가장 적은 경우를 의미한다.

3평균 경우(average case) 분석은 모든 입력에 대한 수행 시간을 알고 계산하기 때문에 시간 복잡도의 척도로 많이 사용한다.

4상각(amortized) 분석은 일련의 연산을 수행하는 데 걸리는 총 시간을 연산 수로 나누어 계산한다.

정답 및 해설

옳지 않은 것은 평균 경우 분석이 모든 입력의 수행 시간을 알고 계산하므로 많이 사용된다는 설명이다.

최악 경우 분석은 어떤 입력에도 그 이상 걸리지 않는다는 상한의 의미를 가진다.
최선 경우 분석은 수행 시간이 가장 적게 걸리는 입력에 대한 분석이다.
상각 분석은 일련의 연산 전체 시간을 연산 수로 나누어 연산당 평균 비용을 구한다.

문제 22

문제를 해결하기 위한 알고리즘 개발 단계를 순서대로 바르게 나열한 것은?

(가) 알고리즘 구현
(나) 알고리즘 설계
(다) 알고리즘 분석
(라) 알고리즘 정확성 검증

1(나) → (다) → (라) → (가)

2(나) → (라) → (다) → (가)

3(다) → (나) → (라) → (가)

4(다) → (라) → (나) → (가)

정답 및 해설

알고리즘 개발 단계는 설계 → 정확성 검증 → 분석 → 구현 순서이다.

분석은 정확성이 검증된 알고리즘을 대상으로 하므로 정확성 검증보다 앞설 수 없다.
설계되지 않은 알고리즘은 분석할 대상이 없으므로 분석이 설계보다 먼저 올 수 없다.

문제 23

그리디 알고리즘에 해당하는 것은?

1크루스칼(Kruskal) 알고리즘

20/1 배낭(knapsack) 문제 풀이

3플로이드－워셜(Floyd-Warshall) 알고리즘

4최장 공통 부분 수열(LCS, Longest Common Subsequence) 구하기

정답 및 해설

그리디 알고리즘에 해당하는 것은 크루스칼 알고리즘이다.

크루스칼 알고리즘은 사이클을 만들지 않는 범위에서 가중치가 가장 작은 간선을 매번 선택해 최소 신장 트리를 만드는 탐욕적 선택 방식이다.

0/1 배낭 문제는 물건을 쪼갤 수 없어 그리디로 최적해가 보장되지 않으며 동적 계획법으로 푼다.
플로이드-워셜 알고리즘은 경유 정점을 하나씩 늘려 가는 동적 계획법이다.
최장 공통 부분 수열은 부분 문제 표를 채우는 동적 계획법으로 구한다.

문제 24

정렬 알고리즘에 대한 설명으로 옳은 것은?

1힙 정렬의 시간 복잡도는

O(n^2)

이다.

2퀵 정렬은 정렬할 전체 원소에 대해 정렬을 수행한 후 기준값을 중심으로 왼쪽 부분집합과 오른쪽 부분집합으로 분할한다.

4병합 정렬은 크기가 n인 입력을 n/2 크기로 분할하고, 각각에 대해 같은 방식으로 정렬을 수행한 후, 2개의 각각 정렬된 부분을 합병한다.

정답 및 해설

옳은 설명은 병합 정렬이 입력을 절반으로 분할해 각각 정렬한 뒤 합병한다는 것이다.

병합 정렬은 분할 정복 알고리즘으로, 분할 깊이 $\log n$ 단계마다 $O(n)$ 합병을 하므로 $O(n\log n)$ 이다.

힙 정렬은 최악의 경우에도 $O(n\log n)$ 이다.
퀵 정렬은 정렬을 먼저 하는 것이 아니라, 기준값으로 먼저 분할한 뒤 각 부분집합을 재귀적으로 정렬한다.
삽입 정렬은 거의 정렬된 입력에서 빠르고(최선), 역순 입력에서 가장 느리다(최악).

문제 25

다음 파이썬 프로그램의 실행 결과는?

class NodeBS(object):
    def __init__(self, vl = None):
        self.vl = vl
        self.root = None
        self.lf = None
        self.rg = None
    def _ad(self, vl):
        nd = NodeBS(vl)
        if vl > self.vl:
            self.rg = self.rg and self.rg._ad(vl) or nd
        elif vl < self.vl:
            self.lf = self.lf and self.lf._ad(vl) or nd
        else:
            print("node duplicated")
        return self
class Bst(NodeBS):
    def add_node(self, vl):
        if not self.root:
            self.root = NodeBS(vl)
        else:
            self.root._ad(vl)
    def order(self):
        current = self.root
        nodes, stack = [], []
        while stack or current:
            if current:
                nodes.append(current.vl)
                stack.append(current)
                current = current.lf
            else:
                current = stack.pop()
                current = current.rg
        return nodes
if __name__ == "__main__":
    bt = Bst()
    in_list = [6, 4, 8, 2, 5, 7, 9, 1, 3, 10]
    for i in in_list:
        bt.add_node(i)
    print(bt.order())

1[6, 4, 2, 1, 3, 8, 5, 7, 9, 10]

2[6, 4, 2, 1, 5, 8, 3, 7, 9, 10]

3[6, 4, 2, 1, 3, 5, 8, 7, 9, 10]

4[6, 4, 2, 1, 5, 3, 8, 7, 9, 10]

정답 및 해설

프로그램은 이진 탐색 트리의 전위 순회 결과 [6, 4, 2, 1, 3, 5, 8, 7, 9, 10]을 출력한다.

삽입 결과 트리: 6의 왼쪽 4, 오른쪽 8 / 4의 왼쪽 2, 오른쪽 5 / 2의 왼쪽 1, 오른쪽 3 / 8의 왼쪽 7, 오른쪽 9 / 9의 오른쪽 10