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

25년 1회차

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

1 / 1

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

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

25년 1회차

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

문제 1

알고리즘의 조건에 대한 설명으로 옳지 않은 것은?

1입력: 외부에서 제공되는 자료가 0개 이상이어야 한다.

2출력: 적어도 1개 이상의 결과를 만들어야 한다.

3명확성: 명령어들은 현재 실행 가능한 연산이어야 한다.

4유한성: 한정된 수의 단계 후에는 반드시 종료되어야 한다.

정답 및 해설

알고리즘 조건의 정의를 바꿔 쓴 것은 명확성에 대한 설명이다.

명확성은 각 명령어의 의미가 모호하지 않고 분명해야 한다는 조건이며, 명령어가 실제로 실행 가능한 연산이어야 한다는 것은 유효성(효과성)에 해당한다.

입력 조건은 외부에서 주어지는 자료가 0개 이상이면 된다는 뜻으로 옳다.
출력 조건은 적어도 하나 이상의 결과를 만들어야 한다는 뜻으로 옳다.
유한성 조건은 한정된 단계를 거친 뒤 반드시 종료해야 한다는 뜻으로 옳다.

문제 2

점근 표기법에 대한 설명으로 옳은 것은?

1알고리즘의 수행 시간을 대략적으로 나타내는 방법이다.

2O(Big-oh) 표기는 최소한의 알고리즘 수행 시간을 나타내기 위해 사용한다.

3n개 정수 배열에 대한 순차 탐색 알고리즘은 O(1) 시간 복잡도를 가진다.

4증가 함수

10n^2+3n+2

는

\mathrm{O}(n)

으로 표기할 수 있다.

정답 및 해설

점근 표기법은 입력 크기가 커질 때 수행 시간의 증가 추세를 대략적으로 나타내는 방법이다.

상수 계수와 낮은 차수 항을 무시하고 가장 빠르게 증가하는 항만으로 복잡도를 표현한다.

O 표기는 수행 시간의 점근적 상한을 나타내며, 하한을 나타내는 것은 Ω 표기이다.
순차 탐색은 최악의 경우 n개 원소를 모두 비교하므로 $\mathrm{O}(n)$ 이다.
$10n^2+3n+2$ 는 최고차항이 $n^2$ 이므로 $\mathrm{O}(n^2)$ 이며, $\mathrm{O}(n)$ 으로 표기할 수 없다.

문제 3

다음 그림과 같은 최대 힙(max heap)을 이용하여 힙 정렬을 수행할 때, 최댓값 9가 배열의 마지막 요소인 4와 교환된 다음, 힙 구조 유지를 위한 연산이 완료된 상태에서의 배열 내용으로 옳은 것은?

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
-	9	6	8	5	3	7	1	2	4

정답 및 해설

교환 후 힙 재구성을 마치면 배열은 -, 8, 6, 7, 5, 3, 4, 1, 2, 9가 된다.

9와 4를 교환하면 9는 정렬 완료 위치인 마지막 칸에 고정되고, 힙 크기는 8로 줄어든다. 루트의 4는 두 자식 6과 8 중 큰 8과 교환되어 [3]으로 내려간다.

[3]의 자식은 [6]의 7과 [7]의 1이므로 더 큰 7과 교환해 4가 [6]에 자리 잡는다. [6]은 크기 8 힙에서 자식이 없어 연산이 끝난다.

8, 4, 6, 7, … 배열: 4가 루트 자식 자리에 남아 있어 자식 7보다 작으므로 힙 조건을 어긴다.
8, 5, 4, 6, … 배열: [3]의 4가 자식 7보다 작아 힙 조건을 어기며, 4는 오른쪽 서브트리로만 내려가므로 나올 수 없다.
8, 7, 6, 3, … 배열: 오른쪽 서브트리의 7이 [2]로 옮겨 가 있어, 4 하나만 아래로 내리는 연산 결과와 다르다.

문제 4

다음은 초기상태 배열을 오름차순으로 정렬하는 단계들이다. 이와 같이 정렬을 수행하는 알고리즘으로 옳은 것은?

초기상태: [69, 10, 30, 3, 16, 8]

step 1: [3, 10, 30, 69, 16, 8]
step 2: [3, 8, 30, 69, 16, 10]
step 3: [3, 8, 10, 69, 16, 30]
step 4: [3, 8, 10, 16, 69, 30]
step 5: [3, 8, 10, 16, 30, 69]

1선택 정렬(selection sort)

2버블 정렬(bubble sort)

3합병 정렬(merge sort)

4기수 정렬(radix sort)

정답 및 해설

제시된 과정은 선택 정렬이다.

매 단계마다 미정렬 구간의 최솟값을 찾아 구간 맨 앞 원소와 교환한다. 첫 단계에서 최솟값 3이 69와, 다음 단계에서 8이 10과 자리를 바꾸는 식으로 앞에서부터 하나씩 확정된다.

버블 정렬은 인접한 두 원소만 비교·교환하므로 첫 단계에서 3이 멀리 떨어진 맨 앞으로 한 번에 옮겨질 수 없다.
합병 정렬은 배열을 반씩 나눈 뒤 정렬된 부분 배열을 합치므로 앞에서부터 원소가 하나씩 확정되는 모양이 아니다.
기수 정렬은 자릿수별로 분배·수집하므로 일의 자리 기준 첫 단계에서 10·30이 맨 앞에 모이는 등 다른 순서가 나온다.

문제 5

다음 중위 표기법 수식을 후위 표기법 수식으로 옳게 변환한 것은?

(A * B) － (C / D) － E

1A B * C D E － / －

2A B * C D / － E －

3A B * C D － / E －

4* A B － / C D － E

정답 및 해설

올바른 후위 표기는 A B * C D / － E －이다.

뺄셈은 왼쪽 결합이므로 수식은 ((A*B) － (C/D)) － E로 묶인다. 괄호 안부터 변환하면 A B *와 C D /가 되고, 이 둘의 뺄셈 뒤에 E를 놓고 마지막 뺄셈을 붙인다.

A B * C D E － / －는 C / (D － E)처럼 E를 나눗셈 안에 넣은 형태라 원래 식과 다르다.
A B * C D － / E －는 (A*B) / (C－D) － E를 뜻해 뺄셈과 나눗셈의 순서가 바뀌었다.
* A B － / C D － E처럼 연산자가 피연산자 앞에 오는 것은 전위 표기의 형태이다.

문제 6

그림과 같이 연결되어 있는 11개의 여행지를 관광객들이 모두 방문할 수 있도록 안내하기 위해 C언어로 구현한 Course() 함수를 다음과 같이 제시하고 있다. 여행지 H를 파라미터로 하여 알고리즘을 호출했을 때, 출력결과의 (가) ～ (라)에 들어갈 내용을 바르게 연결한 것은? (단, 상위 노드 기준으로 n->left는 왼쪽으로 순회하고 n->right는 오른쪽으로 순회한다)

typedef struct node {
    char name;
    struct node *left;
    struct node *right;
} node;

void Course(node *n) {
    if(n != null) {
        Course(n->left);
        Course(n->right);
        printf("%c->", n->name);
    }
}

○ 출력결과
(가) -> □ -> (나) -> □ -> (다) -> □ ->
□ -> □ -> □ -> (라) -> □ ->

1(가) H / (나) A / (다) Z / (라) K

2(가) H / (나) T / (다) S / (라) K

3(가) N / (나) H / (다) U / (라) T

4(가) N / (나) T / (다) E / (라) S

정답 및 해설

Course()는 왼쪽·오른쪽 서브트리를 먼저 처리한 뒤 노드를 출력하는 후위 순회이므로 (가)~(라)는 각각 N, T, E, S이다.

그림의 트리에서 H의 왼쪽 서브트리 F를 먼저 순회하면 N → U → T → A → E → F 순으로 출력되고, 이어서 오른쪽 서브트리에서 Z → Y → K → S, 마지막으로 H가 출력된다.

전체 출력은 N → U → T → A → E → F → Z → Y → K → S → H이며, (가)는 첫째, (나)는 셋째, (다)는 다섯째, (라)는 열째 값이다.

H·A·Z·K 조합: 루트 H는 후위 순회에서 맨 마지막에 출력되므로 첫째 자리에 올 수 없다.
H·T·S·K 조합: 첫째 자리는 가장 왼쪽 단말 N이며, 열째 자리는 K가 아닌 S이다.
N·H·U·T 조합: H는 마지막에 출력되며, 셋째 자리는 A의 오른쪽 자식 T이다.

문제 7

다음 데이터를 순서대로 삽입하여 불균형이 발생했을 때 회전 연산을 수행하여 균형 상태를 유지하는 AVL 트리를 구성하였다. 구성된 AVL 트리에서 단말 노드(leaf node)에 해당하는 값만을 모두 고르면?

50, 60, 70, 90, 80, 75, 73, 72, 78

172, 73, 90

272, 75, 90

350, 73, 75, 90

450, 72, 78, 90

정답 및 해설

최종 AVL 트리의 단말 노드는 50, 72, 78, 90이다.

50·60·70 삽입 후 RR 회전으로 60이 루트가 되고, 90·80 삽입 시 70에서 RL 회전으로 80(70, 90)이 된다. 75 삽입 시 루트 60에서 RL 회전이 일어나 70(60(50), 80(75, 90))이 된다.

73·72 삽입 시 75에서 LL 회전으로 73(72, 75)이 되고, 78 삽입 시 80에서 LR 회전이 일어나 최종 트리는 70(60(50), 75(73(72), 80(78, 90)))이다.

72, 73, 90은 73이 72를 자식으로 가진 내부 노드라서 틀렸다.
72, 75, 90은 75가 회전 후 서브트리의 루트가 되는 내부 노드이며 단말인 50·78도 빠졌다.
50, 73, 75, 90은 73과 75가 모두 자식을 가진 내부 노드라서 틀렸다.

문제 8

그림과 같은 그래프를 대상으로 다음 알고리즘을 적용하였을 때, 결과에 대한 설명으로 옳지 않은 것은? (단, 탐색의 시작 정점은 1이고, Q는 큐 객체이며, Q.enqueue()와 Q.dequeue()는 큐 Q에 대한 삽입과 삭제 연산이고, 각 정점의 방문을 표시하는 것은 visited[] 배열을 이용한다)

_FS(v) {
    visited[v] <- YES;        // 정점 v에 대한 방문 표시
    Q.enqueue(v)
    while(!Q.empty()) {       // Q가 비어있지 않은 동안
        w <- Q.dequeue();
        for all u ∈ (w에 인접한 정점) {
            if(visited[u] != YES) {
                visited[u] <- YES;
                Q.enqueue(u);
            }
        }
    }
}

1알고리즘의 수행에 따른 노드의 방문 순서는 1 → 2 → 5 → 9 → 8 → 4 → 7 → 6 → 3이다.

2너비 우선 탐색(BFS, Breadth First Search) 알고리즘이다.

3시작 정점으로부터 가까운 정점들을 먼저 방문하고 멀리 떨어져 있는 정점들을 나중에 방문하는 탐색방법이다.

4알고리즘은 그래프의 모든 정점을 방문한다.

정답 및 해설

방문 순서가 1 → 2 → 5 → 9 → 8 → 4 → 7 → 6 → 3이라는 설명이 옳지 않다.

제시된 알고리즘은 큐에 정점을 넣고 꺼내며 인접 정점을 차례로 방문하는 너비 우선 탐색이다. 정점 1을 꺼낼 때 인접 정점 2, 3, 4가 모두 먼저 방문되므로 그 뒤에야 5, 6, 7, 8, 9가 방문된다(번호가 작은 인접 정점부터 넣으면 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9).

2 다음에 바로 5로 내려가는 순서는 한 경로를 끝까지 파고드는 깊이 우선 탐색의 방문 순서이다.

너비 우선 탐색 알고리즘이라는 설명: 큐(FIFO)를 사용하므로 옳다.
가까운 정점을 먼저, 먼 정점을 나중에 방문한다는 설명: 시작 정점으로부터의 거리 순으로 방문하는 BFS의 특징이다.
모든 정점을 방문한다는 설명: 그래프가 연결되어 있어 시작 정점 1에서 모든 정점에 도달한다.

문제 9

다음 C언어 함수 ABC()에 대한 설명으로 옳은 것은?

void ABC(int A[], int n) {
    int i, j, tmp;
    for(i = n - 1; i > 0; i--) {
        j = 0;
        while(j < i) {
            if(A[j] < A[j + 1]) {
                tmp = A[j];
                A[j] = A[j + 1];
                A[j + 1] = tmp;
            }
            j = j + 1;
        }
    }
}

1코드 수행 완료 후, A[0]에는 가장 큰 원소가 저장되어 있다.

2코드 수행 완료 후, 배열 A의 원소는 오름차순으로 정렬되어 있다.

3최선의 경우와 최악의 경우의 수행 시간 복잡도가 다르다.

4코드는 삽입 정렬(insertion sort)을 구현한 것이다.

정답 및 해설

함수 실행이 끝나면 A[0]에 가장 큰 원소가 저장된다.

인접한 두 원소를 비교해 앞의 값이 더 작으면 교환하는 버블 정렬로, 매 반복마다 가장 작은 값이 뒤로 밀려나 배열이 내림차순으로 정렬된다.

작은 값이 뒤로 가도록 교환하므로 결과는 오름차순이 아니라 내림차순이다.
교환이 없어도 조기 종료하는 장치가 없어 비교 횟수가 항상 같으므로, 최선과 최악 모두 $\mathrm{O}(n^2)$ 로 같다.
인접 원소를 비교·교환하는 방식은 삽입 정렬이 아니라 버블 정렬이다.

문제 10

다음 자료를 차수가 3인 B－트리에 순서대로 삽입하여 그림과 같은 B－트리를 생성하였을 때, (가) ～ (다)에 들어갈 값을 바르게 연결한 것은?

75, 15, 10, 12, 5, 30, 1, 2, 25, 27, 34, 60

1(가) 25 / (나) 34 / (다) 12

2(가) 25 / (나) 60 / (다) 15

3(가) 30 / (나) 34 / (다) 15

4(가) 30 / (나) 60 / (다) 12

정답 및 해설

모든 자료를 삽입하면 (가)는 30, (나)는 60, (다)는 12이다.

차수 3인 B-트리는 노드당 키가 최대 2개이며, 3개가 되면 가운데 키를 부모로 올려 분할한다. 75·15·10 삽입에서 15가, 5 삽입에서 10이, 2 삽입에서 2가 올라가며 루트 [2, 10, 15]가 다시 분할되어 루트는 [10]이 된다.

이후 25 삽입 시 [25, 30, 75]에서 30이 올라가 [15, 30]이 되고, 60 삽입 시 [34, 60, 75]에서 60이 올라가 [15, 30, 60]이 분할되며 30이 루트로 올라간다.

최종 트리는 루트 [10, 30], 중간 노드 [2]·[15]·[60], 단말 노드 [1]·[5]·[12]·[25, 27]·[34]·[75]이다.

(가)가 25인 조합: 25는 [25, 27] 단말 노드에 남고 루트로 올라간 키는 30이다.
(나)가 34인 조합: 34는 60 분할 때 왼쪽 단말 노드로 남는다.
(다)가 15인 조합: 15는 가운데 중간 노드의 키이며, 그 첫 단말 노드에는 12가 있다.

문제 11

다음은 재귀 호출을 이용하여 피보나치(Fibonacci) 수열값을 찾는 파이썬 코드이다. 이 코드의 시간 복잡도는? (단, n은 0 이상의 정수이다)

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

\mathrm{O}(n)

\mathrm{O}(n^2)

\mathrm{O}(2^n)

\mathrm{O}(\log n)

정답 및 해설

이 재귀 피보나치 함수의 시간 복잡도는 지수 시간 $\mathrm{O}(2^n)$ 이다.

한 번 호출될 때마다 fib(n-1)과 fib(n-2)를 다시 호출하고 계산 결과를 저장하지 않으므로 같은 값을 중복 계산한다.

$T(n) = T(n-1) + T(n-2) + \mathrm{O}(1)$ 이므로 호출 수가 피보나치 수처럼 늘어나며, 상한은 $\mathrm{O}(2^n)$ 이다.

$\mathrm{O}(n)$ 은 계산값을 저장하는 동적 프로그래밍이나 반복문으로 구현했을 때의 복잡도이다.
$\mathrm{O}(n^2)$ 은 호출 트리가 매 단계 두 갈래로 갈라지는 증가 속도를 반영하지 못한다.
$\mathrm{O}(\log n)$ 은 행렬 거듭제곱을 이용한 방법의 복잡도이다.

문제 12

분할 정복(divide-and-conquer) 방식의 정렬 알고리즘에 대한 설명으로 옳지 않은 것은?

12-way 합병 정렬의 분할은 분할 대상을 반으로 나눈다.

2퀵정렬(quick sort)의 분할은 분할 대상에 대하여 피봇(pivot)을 기준으로 나눈다.

3합병 정렬과 다르게 퀵정렬에서는 모든 분할이 완료되면 정렬도 완료된다.

4합병 정렬은 추가 데이터 저장공간이 필요 없는 제자리 정렬 알고리즘이다.

정답 및 해설

옳지 않은 설명은 합병 정렬이 추가 저장공간이 필요 없는 제자리 정렬이라는 내용이다.

합병 정렬은 정렬된 두 부분 배열을 합칠 때 입력 크기만큼의 보조 배열이 필요하므로 제자리 정렬이 아니다.

2-way 합병 정렬은 분할 대상을 반으로 나누므로 옳다.
퀵 정렬은 피봇보다 작은 값과 큰 값으로 분할하므로 옳다.
퀵 정렬은 분할 과정에서 원소 위치가 확정되어 분할이 끝나면 정렬도 끝나지만, 합병 정렬은 분할 후 합병 단계에서 정렬이 이루어지므로 옳다.

문제 13

배열로 운영하는 원형 큐에 대해 다음과 같이 연산 1에서 7까지의 연산을 차례로 수행했을 때, 수행이 완료된 후 큐의 상태로 옳은 것은? (단, 현재 상태에서 front ＝ 0, rear ＝ 2이다)

[0]	[1]	[2]	[3]	[4]
	Z	X

연산 1. 원소 Y 삽입
연산 2. 원소 3개 삭제
연산 3. 원소 Q 삽입
연산 4. 원소 M 삽입
연산 5. 원소 A 삽입
연산 6. 원소 K 삽입
연산 7. 원소 2개 삭제

[0]	[1]	[2]	[3]	[4]
M				Q

[0]	[1]	[2]	[3]	[4]
	A	K

[0]	[1]	[2]	[3]	[4]
			Y	Q

[0]	[1]	[2]	[3]	[4]
M	A

정답 및 해설

연산을 모두 마친 뒤 큐에는 [1]에 A, [2]에 K만 남는다.

원형 큐는 front가 첫 원소의 바로 앞 칸, rear가 마지막 원소를 가리키고, 인덱스는 5로 나눈 나머지로 순환한다. 처음에는 [1]에 Z, [2]에 X가 있다.

Y 삽입으로 rear=3, 3개 삭제로 Z·X·Y가 빠져 front=3이 된다. Q·M·A·K를 차례로 [4]·[0]·[1]·[2]에 넣어 rear=2가 되고, 2개 삭제로 먼저 들어온 Q와 M이 빠져 front=0이 된다.

[0]에 M, [4]에 Q가 남는 상태는 먼저 들어온 Q·M부터 삭제되는 선입선출 순서와 맞지 않는다.
[3]에 Y, [4]에 Q가 남는 상태는 앞선 3개 삭제에서 Y까지 빠진다는 점을 놓친 것이다.
[0]에 M, [1]에 A가 남는 상태는 K가 [2]에 삽입되고 M이 삭제된다는 점을 반영하지 못했다.

문제 14

다음 그래프를 대상으로 크루스칼(Kruskal) 알고리즘을 적용하여 최소 신장 트리(MST, Minimum Spanning Tree)를 구성하고자 할 때, 생성되는 MST에 5번째 추가되는 간선과 비용을 바르게 연결한 것은?

1간선 (b, c) / 비용 16

2간선 (d, g) / 비용 18

3간선 (d, e) / 비용 22

4간선 (e, g) / 비용 25

정답 및 해설

5번째로 추가되는 간선은 (d, e), 비용 22이다.

크루스칼 알고리즘은 간선을 비용 오름차순으로 검사해 사이클을 만들지 않는 간선만 채택한다. 순서대로 (a, f) 10, (c, d) 12, (b, g) 15, (b, c) 16이 채택된다.

다음 (d, g) 18은 이미 g-b-c-d로 연결된 두 정점을 잇게 되어 사이클이 생기므로 버려지고, 이어지는 (d, e) 22가 다섯 번째로 채택된다.

(b, c) 비용 16: 네 번째로 채택되는 간선이다.
(d, g) 비용 18: 사이클을 형성해 MST에 포함되지 않는다.
(e, g) 비용 25: e가 이미 d를 통해 연결된 뒤라 사이클이 생겨 제외된다.

문제 15

문자열 매칭을 위한 알고리즘으로 옳은 것은?

1합병 정렬 알고리즘

2라빈 카프(Rabin-Karp) 알고리즘

3백트래킹(backtracking) 알고리즘

4후위 순회(postorder traversal) 알고리즘

정답 및 해설

문자열 매칭 알고리즘은 라빈-카프 알고리즘이다.

라빈-카프는 패턴과 본문 구간을 해시 값으로 바꿔 비교하고, 한 칸 이동할 때 해시를 상수 시간에 갱신해 일치 후보를 빠르게 찾는다.

합병 정렬은 분할 정복 방식의 정렬 알고리즘이다.
백트래킹은 해 공간을 탐색하다 유망하지 않으면 되돌아가는 탐색 기법이다.
후위 순회는 트리의 노드를 왼쪽·오른쪽 서브트리 다음 루트 순으로 방문하는 순회 방법이다.

문제 16

다음은 단일 출발점 최단 경로를 찾기 위한 다익스트라(Dijkstra) 알고리즘을 의사(pseudo) 코드로 기술한 것이다. 이 코드에서 (가)에 들어갈 내용으로 옳은 것은?

// 입력: 가중 방향 그래프 G, 인접 행렬 A, 시작 정점 s
// 출력: s로부터 다른 모든 정점까지의 최단 경로의 길이
Dijkstra(G, A, s) {
    U = {s};
    for(모든 정점 v ∈ G)
        D[v] = A[s][v];
    while(U != G) {
        D[w]가 최소인 정점 w ∈ (G - U)를 선택
        U = U ∪ {w};
        for(w에 인접한 모든 정점 v) {
            D[v] = (가);
        }
    }
}

1min(D[v], D[v] ＋ A[v][w])

2min(D[v], D[w] ＋ A[v][w])

3min(D[v], D[v] ＋ A[w][v])

4min(D[v], D[w] ＋ A[w][v])

정답 및 해설

(가)에 들어갈 갱신식은 min(D[v], D[w] ＋ A[w][v])이다.

새로 확정된 정점 w를 거쳐 v로 가는 경로의 길이는 s에서 w까지의 최단 거리 D[w]에 간선 w→v의 가중치 A[w][v]를 더한 값이다. 이것이 기존 D[v]보다 작으면 갱신한다(완화).

D[v] ＋ A[v][w]는 w를 거치는 경로가 아니라 v에서 출발하는 값이라 의미가 없다.
D[w] ＋ A[v][w]는 방향 그래프에서 간선 방향을 v→w로 거꾸로 읽은 것이다.
D[v] ＋ A[w][v]는 w까지의 거리 대신 v의 거리를 더해 w를 경유하는 경로가 아니다.

문제 17

KMP(Knuth-Morris-Pratt) 알고리즘과 보이어－무어(Boyer-Moore) 알고리즘에 대한 설명으로 옳지 않은 것은?

1KMP 알고리즘은 패턴 문자열의 첫 문자부터 순차적으로 대상 문자열과 부분 문자열의 일치 여부를 판단한다.

2KMP 알고리즘은 패턴 문자열과 대상 문자열을 한 차례 비교한 후 얻을 수 있는 추가 정보로 비교 횟수를 감소시킨다.

3보이어－무어 알고리즘은 패턴 문자열의 마지막 문자부터 역순으로 대상 문자열과 부분 문자열의 일치 여부를 판단한다.

4보이어－무어 알고리즘은 전처리(preprocessing) 과정 없이 곧바로 일치 여부를 판단할 수 있다.

정답 및 해설

옳지 않은 설명은 보이어-무어 알고리즘이 전처리 없이 곧바로 비교한다는 내용이다.

보이어-무어는 비교 전에 패턴을 분석해 나쁜 문자 이동표·착한 접미부 이동표를 만들어 두고, 불일치 시 이 표로 건너뛸 거리를 정한다.

KMP는 패턴의 첫 문자부터 왼쪽에서 오른쪽으로 비교하므로 옳다.
KMP는 앞선 비교에서 얻은 접두부·접미부 일치 정보(실패 함수)로 비교 횟수를 줄이므로 옳다.
보이어-무어는 패턴의 마지막 문자부터 역순으로 비교하므로 옳다.

문제 18

다음 조건에 따라 주어진 그래프에 대해 깊이 우선 탐색(DFS, Depth First Search) 방법을 이용하여 트리를 만들 경우, 나올 수 있는 트리의 개수와 수행하는 백트래킹 횟수를 바르게 연결한 것은?

○ DFS의 시작 정점은 A로 하고, 정점의 접근 순서는 알파벳 순서로 한다.
○ DFS는 사이클을 형성하지 않으면서 백트래킹을 통해 시작 정점으로 돌아왔을 때, 시작 정점에서 방문하지 않은 접근 가능한 인접 정점이 없으면 종료한다.
○ DFS의 종료시점에 그래프에 방문하지 않은 정점들이 존재하면, 방문하지 않은 정점들 중 알파벳 순서가 가장 앞선 정점을 시작 정점으로 하여 DFS를 다시 시작한다.
○ 그래프 안에 방문하지 않은 정점이 존재하지 않을 때까지 DFS를 반복한다.

1트리의 개수 1 / 백트래킹 횟수 3

2트리의 개수 1 / 백트래킹 횟수 4

3트리의 개수 2 / 백트래킹 횟수 3

4트리의 개수 2 / 백트래킹 횟수 5

정답 및 해설

DFS를 조건대로 수행하면 트리는 2개, 백트래킹은 5회이다.

A에서 시작해 A → B → C로 내려가면 C는 나가는 간선이 없어 B로 되돌아가고(1회), B → D로 간 뒤 D의 인접 정점 A·C가 모두 방문되어 B로(2회), B에서 더 갈 곳이 없어 A로(3회) 되돌아간다.

A → F로 간 뒤 F의 인접 정점 A·C가 이미 방문되어 A로 되돌아가고(4회), A에 남은 정점이 없어 첫 트리 {A, B, C, D, F}가 끝난다.

남은 정점 중 가장 앞선 E에서 다시 시작해 E → G로 간 뒤 G의 인접 정점 D·E가 방문되어 E로 되돌아가며(5회), 두 번째 트리 {E, G}가 만들어진다.

트리 1개·백트래킹 3회 조합: E와 G는 A에서 출발하는 간선으로 도달할 수 없어 DFS를 다시 시작해야 하므로 트리가 2개이다.
트리 1개·백트래킹 4회 조합: 4회는 첫 트리의 백트래킹만 센 값이며, E에서 다시 시작하는 두 번째 트리가 빠졌다.
트리 2개·백트래킹 3회 조합: 첫 트리에서만 4회, 두 번째 트리에서 1회가 발생해 합계 5회이다.

문제 19

다음은 n개의 데이터에 대한 평균을 재귀적으로 계산하는 프로그램이다. (가) ～ (다)에 들어갈 내용을 바르게 연결한 것은? (단, n ≥ 1이다)

float AVG(float (가), int n) {
 if(n == 1) return (나);
  else
   return (data[n - 1] + (n - 1) * AVG(data, n - 1)) / (다);
}

1(가) data[] / (나) 0 / (다) n

2(가) data[] / (나) 1 / (다) (n-1)

3(가) *data / (나) data[0] / (다) n

4(가) *data / (나) data[n-1] / (다) (n-1)

정답 및 해설

(가)는 *data, (나)는 data[0], (다)는 n이다.

원소가 하나면 평균은 그 원소 자신이므로 data[0]을 반환한다.

앞 n-1개의 평균에 (n-1)을 곱하면 그 합이 되고, 여기에 마지막 원소 data[n-1]을 더하면 n개의 합이므로 n으로 나누어야 평균이 된다. 매개변수는 배열을 받는 포인터 *data로 선언한다.

(나)를 0으로 두면 원소가 하나일 때 평균이 항상 0이 되어 틀렸다.
(나)를 1로, (다)를 (n-1)로 두면 기저값과 나누는 개수가 모두 맞지 않는다.
(나)를 data[n-1]로, (다)를 (n-1)로 두면 n개 합을 n-1로 나누게 되어 평균이 아니다.

문제 20

작업 선택 문제를 다루는 다음 알고리즘은 각 작업의 시작 시간 s와 완료 시간 f가 정해진

n

개의 작업 t[0..n-1]가 주어질 때, 하나의 기계만 사용하여 충돌 없이 수행할 수 있는 최대 개수의 작업을 선택한다. 이 알고리즘의 (가), (나)에 들어갈 내용을 바르게 연결한 것은? (단, n ≥ 2인 정수, count는 선택한 작업의 개수, t[i].s는 작업 t[i]의 시작 시간, t[i].f는 작업 t[i]의 종료 시간이고, jobs 배열은 선택된 작업을 저장한다)

ActSelect(n, t[]) {
    (가) 의 오름차순으로 작업 t[]를 정렬;
    count = 0, last = 0, jobs[];
    jobs[count] = 0;
    for(i = 0; i < n; i++)
        if( (나) ) {
            count++;
            last = i;
            jobs[count] = last;
        }
    return jobs;
}

1(가) 시작 시간 / (나) t[i].s >= t[last].f

2(가) 시작 시간 / (나) t[i].f >= t[last].s

3(가) 완료 시간 / (나) t[i].s >= t[last].f

4(가) 완료 시간 / (나) t[i].f >= t[last].s

정답 및 해설

(가)는 완료 시간, (나)는 t[i].s >= t[last].f이다.

작업 선택 문제의 탐욕 전략은 가장 일찍 끝나는 작업부터 고르는 것으로, 그래야 남은 시간에 더 많은 작업을 넣을 수 있다.

정렬 후에는 현재 작업의 시작 시간이 마지막으로 선택한 작업의 종료 시간 이후일 때만 충돌이 없으므로 선택한다.

시작 시간 순으로 정렬하면 일찍 시작하지만 오래 걸리는 작업이 먼저 뽑혀 최대 개수를 보장하지 못한다.
시작 시간 순 정렬에 종료·시작 시간을 비교하는 조건은 정렬 기준과 겹침 판정이 모두 틀렸다.
완료 시간 순 정렬이라도 현재 작업의 종료 시간과 마지막 작업의 시작 시간을 비교하면 시간 겹침을 막지 못한다.

문제 21

동적 프로그래밍(dynamic programming) 방법으로 최소의 원소단위 곱셈 횟수를 갖도록 연쇄 행렬곱셈(matrix-chain multiplication)의 순서를 정하려 한다.

c_{i,j}

를 행렬

M_i

부터

M_j

까지의 연쇄 행렬곱셈의 최소 비용이라고 할 때,

c_{i,j}

에 대한 관계식으로 옳은 것은? (단,

i \lt j

이고, 각 행렬의 차원이

p_0, p_1, \ldots ,p_n

일 때, 행렬

M_i

의 크기는

p_{i-1} \times p_i

이다)

c_{i,j} = \begin{cases} 0 & \text{if } i = j \\ \min_{i \le k \le j-1}\{c_{i,k}+c_{k+1,j}+p_{i-1}p_kp_j\} & \text{if } i \lt j \end{cases}

c_{i,j} = \begin{cases} 0 & \text{if } i = j \\ \min_{i \le k \le j-1}\{c_{i,k}+c_{k,j}+p_{i-1}p_{k-1}p_j\} & \text{if } i \lt j \end{cases}

c_{i,j} = \begin{cases} 0 & \text{if } i = j \\ \min_{i \le k \le j-1}\{c_{i,k-1}+c_{k,j}+p_{i-1}p_{k-1}p_j\} & \text{if } i \lt j \end{cases}

c_{i,j} = \begin{cases} 0 & \text{if } i = j \\ \min_{i \le k \le j-1}\{c_{i,k}+c_{k,j}+p_{i-1}p_kp_j\} & \text{if } i \lt j \end{cases}

정답 및 해설

올바른 관계식은 $c_{i,j}=\min_{i \le k \le j-1}\{c_{i,k}+c_{k+1,j}+p_{i-1}p_kp_j\}$ 이다.

분할점 k에서 $M_i \cdots M_k$ 와 $M_{k+1} \cdots M_j$ 로 나누면 두 결과 행렬의 크기는 $p_{i-1} \times p_k$ 와 $p_k \times p_j$ 이고, 이를 곱하는 비용이 $p_{i-1}p_kp_j$ 이다.

$c_{i,k}+c_{k,j}+p_{i-1}p_{k-1}p_j$ 식은 행렬 $M_k$ 를 두 부분에 중복 포함하고 곱셈 비용의 차원도 맞지 않는다.
$c_{i,k-1}+c_{k,j}$ 식은 k의 범위가 $i \le k \le j-1$ 이므로 k=i일 때 정의되지 않는 $c_{i,i-1}$ 가 나오고 마지막 분할도 빠진다.
$c_{i,k}+c_{k,j}+p_{i-1}p_kp_j$ 식은 $M_k$ 를 양쪽 부분에 중복 포함한다.

문제 22

동적 프로그래밍은 한 번 계산된 값을 메모리에 저장한 후, 저장된 값을 필요할 때마다 가져다 쓰는 방법이다. 동적 프로그래밍을 적용하여 구현한 다음 Java 프로그램에서 피보나치 수열 fibo(6)을 구하기 위해 저장되어 있는 fibo(3)의 결과를 가져다 쓰는 횟수는?

public class Fibonacci {
    static int[] dp = new int[100];

    public static void main(String[] args) {
        System.out.println(fibo(6));
    }

    public static int fibo(int num) {
        if(num == 0) {
            return 0;
        }
        if(num == 1) {
            return 1;
        }
        if(dp[num] != 0) {
            return dp[num];
        }
        return dp[num] = fibo(num - 1) + fibo(num - 2);
    }
}

정답 및 해설

fibo(6)을 구하는 동안 저장된 fibo(3)의 값을 꺼내 쓰는 것은 한 번이다.

호출은 fibo(6)→fibo(5)→fibo(4)→fibo(3)→fibo(2) 순으로 왼쪽 가지를 먼저 내려가며 dp[2]·dp[3]·dp[4]·dp[5]를 차례로 저장한다.

fibo(3)은 fibo(4) 안에서 처음 계산되고, 이후 fibo(5)가 오른쪽 가지로 fibo(3)을 부를 때 dp[3]을 반환한다. fibo(6)의 오른쪽 가지 fibo(4)는 dp[4]에서 바로 반환되므로 fibo(3)을 다시 부르지 않는다.

0회는 fibo(5)의 오른쪽 호출이 저장값으로 처리된다는 점을 놓친 것이다.
2회나 3회는 저장값이 없을 때처럼 fibo(4)를 다시 전개한 경우로, 메모이제이션에서는 일어나지 않는다.

문제 23

배낭 문제(knapsack problem)에 대한 설명으로 옳은 것은?

10－1 배낭 문제와 분할 가능 배낭 문제는 다항식 시간(polynomial-time) 문제이다.

2분할 가능 배낭 문제는 최적 부분 구조를 갖지만, 0－1 배낭 문제는 그렇지 않다.

30－1 배낭 문제는 물건을 나눌 수 없어서 그리디(greedy) 알고리즘을 적용하여 해결할 수 있으며, 분할 가능 배낭 문제는 물건을 나눌 수 있어 동적 프로그래밍으로 해결해야 한다.

4분할 가능 배낭 문제는 ‘단위 무게당 가치가 가장 높은 물건을 선택’하는 방식이 항상 최적해를 보장하지만, 0－1 배낭 문제는 그렇지 않다.

정답 및 해설

옳은 설명은 분할 가능 배낭 문제는 단위 무게당 가치가 높은 물건부터 고르는 탐욕법이 최적해를 보장하지만 0-1 배낭 문제는 그렇지 않다는 것이다.

0-1 배낭 문제는 물건을 쪼갤 수 없어 탐욕 선택이 남는 용량을 낭비할 수 있으므로 동적 프로그래밍으로 풀어야 한다.

0-1 배낭 문제는 NP-난해 문제(결정 문제는 NP-완전)로, 다항식 시간 알고리즘이 알려져 있지 않다.
0-1 배낭 문제도 최적 부분 구조를 가지며, 그래서 동적 프로그래밍을 적용할 수 있다.
탐욕 알고리즘이 맞는 쪽은 분할 가능 배낭이고, 동적 프로그래밍이 필요한 쪽은 0-1 배낭이므로 설명이 뒤바뀌었다.

문제 24

알고리즘들에 대한 설명으로 옳지 않은 것은?

1크루스칼의 최소 신장 트리 알고리즘은 가중치가 가장 작으면서 사이클을 만들지 않는 간선을 추가하여 트리를 구성한다.

2프림(Prim)의 최소 신장 트리 알고리즘은 현재까지 만들어진 트리에 최소 가중치로 연결되는 정점을 트리에 추가한다.

3허프만(Huffman) 압축에서 파일에 빈번히 나타나는 문자는 긴 이진코드를 할당하고, 드물게 나타나는 문자는 짧은 이진코드를 할당한다.

4벨만－포드(Bellman-Ford)의 최단 경로 알고리즘은 음의 가중치를 갖는 간선이 존재하는 상황에서도 단일 출발점 최단 경로 문제를 해결하는 알고리즘이다.

정답 및 해설

옳지 않은 설명은 허프만 압축에서 자주 나오는 문자에 긴 코드를 준다는 내용이다.

허프만 코드는 빈도가 높은 문자에 짧은 코드, 빈도가 낮은 문자에 긴 코드를 할당해 전체 비트 수를 줄인다.

크루스칼 알고리즘은 가중치가 작은 간선부터 사이클을 만들지 않는 것만 추가하므로 옳다.
프림 알고리즘은 현재 트리에 최소 가중치로 연결되는 정점을 하나씩 추가하므로 옳다.
벨만-포드 알고리즘은 음의 가중치 간선이 있어도 단일 출발점 최단 경로를 구하므로 옳다.

문제 25

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

○ 주어진 문제에 대해 근사해나 일정 확률 이상의 최적해를 출력함
○ 근사해나 간혹 틀린 해를 허용할 수 있는 경우에 사용 가능함
○ 효율적인 결정론적 알고리즘이 밝혀져 있지 않은 문제에 효과적임

1유클리드(Euclid) 알고리즘

2스트라센(Strassen) 알고리즘

3몬테카를로(Monte Carlo) 알고리즘

4플로이드－워샬(Floyd-Warshall) 알고리즘

정답 및 해설

설명에 해당하는 알고리즘은 몬테카를로 알고리즘이다.

몬테카를로는 난수를 이용하는 확률적 알고리즘으로, 정해진 시간 안에 끝나지만 결과가 근사해이거나 일정 확률로 틀릴 수 있다.

유클리드 알고리즘은 최대공약수를 정확히 구하는 결정론적 알고리즘이다.
스트라센 알고리즘은 분할 정복으로 행렬 곱셈 횟수를 줄이는 결정론적 알고리즘이다.
플로이드-워샬 알고리즘은 동적 프로그래밍으로 모든 정점 쌍의 최단 경로를 정확히 구한다.

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

25년 1회차

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

문제 1

알고리즘의 조건에 대한 설명으로 옳지 않은 것은?

1입력: 외부에서 제공되는 자료가 0개 이상이어야 한다.

2출력: 적어도 1개 이상의 결과를 만들어야 한다.

3명확성: 명령어들은 현재 실행 가능한 연산이어야 한다.

4유한성: 한정된 수의 단계 후에는 반드시 종료되어야 한다.

정답 및 해설

알고리즘 조건의 정의를 바꿔 쓴 것은 명확성에 대한 설명이다.

입력 조건은 외부에서 주어지는 자료가 0개 이상이면 된다는 뜻으로 옳다.
출력 조건은 적어도 하나 이상의 결과를 만들어야 한다는 뜻으로 옳다.
유한성 조건은 한정된 단계를 거친 뒤 반드시 종료해야 한다는 뜻으로 옳다.

문제 2

점근 표기법에 대한 설명으로 옳은 것은?

1알고리즘의 수행 시간을 대략적으로 나타내는 방법이다.

2O(Big-oh) 표기는 최소한의 알고리즘 수행 시간을 나타내기 위해 사용한다.

3n개 정수 배열에 대한 순차 탐색 알고리즘은 O(1) 시간 복잡도를 가진다.

4증가 함수

10n^2+3n+2

는

\mathrm{O}(n)

으로 표기할 수 있다.

정답 및 해설

점근 표기법은 입력 크기가 커질 때 수행 시간의 증가 추세를 대략적으로 나타내는 방법이다.

상수 계수와 낮은 차수 항을 무시하고 가장 빠르게 증가하는 항만으로 복잡도를 표현한다.

O 표기는 수행 시간의 점근적 상한을 나타내며, 하한을 나타내는 것은 Ω 표기이다.
순차 탐색은 최악의 경우 n개 원소를 모두 비교하므로 $\mathrm{O}(n)$ 이다.
$10n^2+3n+2$ 는 최고차항이 $n^2$ 이므로 $\mathrm{O}(n^2)$ 이며, $\mathrm{O}(n)$ 으로 표기할 수 없다.

문제 3

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
-	9	6	8	5	3	7	1	2	4

정답 및 해설

교환 후 힙 재구성을 마치면 배열은 -, 8, 6, 7, 5, 3, 4, 1, 2, 9가 된다.

[3]의 자식은 [6]의 7과 [7]의 1이므로 더 큰 7과 교환해 4가 [6]에 자리 잡는다. [6]은 크기 8 힙에서 자식이 없어 연산이 끝난다.

8, 4, 6, 7, … 배열: 4가 루트 자식 자리에 남아 있어 자식 7보다 작으므로 힙 조건을 어긴다.
8, 5, 4, 6, … 배열: [3]의 4가 자식 7보다 작아 힙 조건을 어기며, 4는 오른쪽 서브트리로만 내려가므로 나올 수 없다.
8, 7, 6, 3, … 배열: 오른쪽 서브트리의 7이 [2]로 옮겨 가 있어, 4 하나만 아래로 내리는 연산 결과와 다르다.

문제 4

다음은 초기상태 배열을 오름차순으로 정렬하는 단계들이다. 이와 같이 정렬을 수행하는 알고리즘으로 옳은 것은?

초기상태: [69, 10, 30, 3, 16, 8]

step 1: [3, 10, 30, 69, 16, 8]
step 2: [3, 8, 30, 69, 16, 10]
step 3: [3, 8, 10, 69, 16, 30]
step 4: [3, 8, 10, 16, 69, 30]
step 5: [3, 8, 10, 16, 30, 69]

1선택 정렬(selection sort)

2버블 정렬(bubble sort)

3합병 정렬(merge sort)

4기수 정렬(radix sort)

정답 및 해설

제시된 과정은 선택 정렬이다.

버블 정렬은 인접한 두 원소만 비교·교환하므로 첫 단계에서 3이 멀리 떨어진 맨 앞으로 한 번에 옮겨질 수 없다.
합병 정렬은 배열을 반씩 나눈 뒤 정렬된 부분 배열을 합치므로 앞에서부터 원소가 하나씩 확정되는 모양이 아니다.
기수 정렬은 자릿수별로 분배·수집하므로 일의 자리 기준 첫 단계에서 10·30이 맨 앞에 모이는 등 다른 순서가 나온다.

문제 5

다음 중위 표기법 수식을 후위 표기법 수식으로 옳게 변환한 것은?

(A * B) － (C / D) － E

1A B * C D E － / －

2A B * C D / － E －

3A B * C D － / E －

4* A B － / C D － E

정답 및 해설

올바른 후위 표기는 A B * C D / － E －이다.

A B * C D E － / －는 C / (D － E)처럼 E를 나눗셈 안에 넣은 형태라 원래 식과 다르다.
A B * C D － / E －는 (A*B) / (C－D) － E를 뜻해 뺄셈과 나눗셈의 순서가 바뀌었다.
* A B － / C D － E처럼 연산자가 피연산자 앞에 오는 것은 전위 표기의 형태이다.

문제 6

typedef struct node {
    char name;
    struct node *left;
    struct node *right;
} node;

void Course(node *n) {
    if(n != null) {
        Course(n->left);
        Course(n->right);
        printf("%c->", n->name);
    }
}

○ 출력결과
(가) -> □ -> (나) -> □ -> (다) -> □ ->
□ -> □ -> □ -> (라) -> □ ->

1(가) H / (나) A / (다) Z / (라) K

2(가) H / (나) T / (다) S / (라) K

3(가) N / (나) H / (다) U / (라) T

4(가) N / (나) T / (다) E / (라) S

정답 및 해설

Course()는 왼쪽·오른쪽 서브트리를 먼저 처리한 뒤 노드를 출력하는 후위 순회이므로 (가)~(라)는 각각 N, T, E, S이다.

전체 출력은 N → U → T → A → E → F → Z → Y → K → S → H이며, (가)는 첫째, (나)는 셋째, (다)는 다섯째, (라)는 열째 값이다.

H·A·Z·K 조합: 루트 H는 후위 순회에서 맨 마지막에 출력되므로 첫째 자리에 올 수 없다.
H·T·S·K 조합: 첫째 자리는 가장 왼쪽 단말 N이며, 열째 자리는 K가 아닌 S이다.
N·H·U·T 조합: H는 마지막에 출력되며, 셋째 자리는 A의 오른쪽 자식 T이다.

문제 7

50, 60, 70, 90, 80, 75, 73, 72, 78

172, 73, 90

272, 75, 90

350, 73, 75, 90

450, 72, 78, 90

정답 및 해설

최종 AVL 트리의 단말 노드는 50, 72, 78, 90이다.

73·72 삽입 시 75에서 LL 회전으로 73(72, 75)이 되고, 78 삽입 시 80에서 LR 회전이 일어나 최종 트리는 70(60(50), 75(73(72), 80(78, 90)))이다.

72, 73, 90은 73이 72를 자식으로 가진 내부 노드라서 틀렸다.
72, 75, 90은 75가 회전 후 서브트리의 루트가 되는 내부 노드이며 단말인 50·78도 빠졌다.
50, 73, 75, 90은 73과 75가 모두 자식을 가진 내부 노드라서 틀렸다.

문제 8

_FS(v) {
    visited[v] <- YES;        // 정점 v에 대한 방문 표시
    Q.enqueue(v)
    while(!Q.empty()) {       // Q가 비어있지 않은 동안
        w <- Q.dequeue();
        for all u ∈ (w에 인접한 정점) {
            if(visited[u] != YES) {
                visited[u] <- YES;
                Q.enqueue(u);
            }
        }
    }
}

1알고리즘의 수행에 따른 노드의 방문 순서는 1 → 2 → 5 → 9 → 8 → 4 → 7 → 6 → 3이다.

2너비 우선 탐색(BFS, Breadth First Search) 알고리즘이다.

3시작 정점으로부터 가까운 정점들을 먼저 방문하고 멀리 떨어져 있는 정점들을 나중에 방문하는 탐색방법이다.

4알고리즘은 그래프의 모든 정점을 방문한다.

정답 및 해설

방문 순서가 1 → 2 → 5 → 9 → 8 → 4 → 7 → 6 → 3이라는 설명이 옳지 않다.

2 다음에 바로 5로 내려가는 순서는 한 경로를 끝까지 파고드는 깊이 우선 탐색의 방문 순서이다.

너비 우선 탐색 알고리즘이라는 설명: 큐(FIFO)를 사용하므로 옳다.
가까운 정점을 먼저, 먼 정점을 나중에 방문한다는 설명: 시작 정점으로부터의 거리 순으로 방문하는 BFS의 특징이다.
모든 정점을 방문한다는 설명: 그래프가 연결되어 있어 시작 정점 1에서 모든 정점에 도달한다.

문제 9

다음 C언어 함수 ABC()에 대한 설명으로 옳은 것은?

void ABC(int A[], int n) {
    int i, j, tmp;
    for(i = n - 1; i > 0; i--) {
        j = 0;
        while(j < i) {
            if(A[j] < A[j + 1]) {
                tmp = A[j];
                A[j] = A[j + 1];
                A[j + 1] = tmp;
            }
            j = j + 1;
        }
    }
}

1코드 수행 완료 후, A[0]에는 가장 큰 원소가 저장되어 있다.

2코드 수행 완료 후, 배열 A의 원소는 오름차순으로 정렬되어 있다.

3최선의 경우와 최악의 경우의 수행 시간 복잡도가 다르다.

4코드는 삽입 정렬(insertion sort)을 구현한 것이다.

정답 및 해설

함수 실행이 끝나면 A[0]에 가장 큰 원소가 저장된다.

인접한 두 원소를 비교해 앞의 값이 더 작으면 교환하는 버블 정렬로, 매 반복마다 가장 작은 값이 뒤로 밀려나 배열이 내림차순으로 정렬된다.

작은 값이 뒤로 가도록 교환하므로 결과는 오름차순이 아니라 내림차순이다.
교환이 없어도 조기 종료하는 장치가 없어 비교 횟수가 항상 같으므로, 최선과 최악 모두 $\mathrm{O}(n^2)$ 로 같다.
인접 원소를 비교·교환하는 방식은 삽입 정렬이 아니라 버블 정렬이다.

문제 10

다음 자료를 차수가 3인 B－트리에 순서대로 삽입하여 그림과 같은 B－트리를 생성하였을 때, (가) ～ (다)에 들어갈 값을 바르게 연결한 것은?

75, 15, 10, 12, 5, 30, 1, 2, 25, 27, 34, 60

1(가) 25 / (나) 34 / (다) 12

2(가) 25 / (나) 60 / (다) 15

3(가) 30 / (나) 34 / (다) 15

4(가) 30 / (나) 60 / (다) 12

정답 및 해설

모든 자료를 삽입하면 (가)는 30, (나)는 60, (다)는 12이다.

이후 25 삽입 시 [25, 30, 75]에서 30이 올라가 [15, 30]이 되고, 60 삽입 시 [34, 60, 75]에서 60이 올라가 [15, 30, 60]이 분할되며 30이 루트로 올라간다.

최종 트리는 루트 [10, 30], 중간 노드 [2]·[15]·[60], 단말 노드 [1]·[5]·[12]·[25, 27]·[34]·[75]이다.

(가)가 25인 조합: 25는 [25, 27] 단말 노드에 남고 루트로 올라간 키는 30이다.
(나)가 34인 조합: 34는 60 분할 때 왼쪽 단말 노드로 남는다.
(다)가 15인 조합: 15는 가운데 중간 노드의 키이며, 그 첫 단말 노드에는 12가 있다.

문제 11

다음은 재귀 호출을 이용하여 피보나치(Fibonacci) 수열값을 찾는 파이썬 코드이다. 이 코드의 시간 복잡도는? (단, n은 0 이상의 정수이다)

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

\mathrm{O}(n)

\mathrm{O}(n^2)

\mathrm{O}(2^n)

\mathrm{O}(\log n)

정답 및 해설

이 재귀 피보나치 함수의 시간 복잡도는 지수 시간 $\mathrm{O}(2^n)$ 이다.

한 번 호출될 때마다 fib(n-1)과 fib(n-2)를 다시 호출하고 계산 결과를 저장하지 않으므로 같은 값을 중복 계산한다.

$T(n) = T(n-1) + T(n-2) + \mathrm{O}(1)$ 이므로 호출 수가 피보나치 수처럼 늘어나며, 상한은 $\mathrm{O}(2^n)$ 이다.

$\mathrm{O}(n)$ 은 계산값을 저장하는 동적 프로그래밍이나 반복문으로 구현했을 때의 복잡도이다.
$\mathrm{O}(n^2)$ 은 호출 트리가 매 단계 두 갈래로 갈라지는 증가 속도를 반영하지 못한다.
$\mathrm{O}(\log n)$ 은 행렬 거듭제곱을 이용한 방법의 복잡도이다.

문제 12

분할 정복(divide-and-conquer) 방식의 정렬 알고리즘에 대한 설명으로 옳지 않은 것은?

12-way 합병 정렬의 분할은 분할 대상을 반으로 나눈다.

2퀵정렬(quick sort)의 분할은 분할 대상에 대하여 피봇(pivot)을 기준으로 나눈다.

3합병 정렬과 다르게 퀵정렬에서는 모든 분할이 완료되면 정렬도 완료된다.

4합병 정렬은 추가 데이터 저장공간이 필요 없는 제자리 정렬 알고리즘이다.

정답 및 해설

옳지 않은 설명은 합병 정렬이 추가 저장공간이 필요 없는 제자리 정렬이라는 내용이다.

합병 정렬은 정렬된 두 부분 배열을 합칠 때 입력 크기만큼의 보조 배열이 필요하므로 제자리 정렬이 아니다.

2-way 합병 정렬은 분할 대상을 반으로 나누므로 옳다.
퀵 정렬은 피봇보다 작은 값과 큰 값으로 분할하므로 옳다.
퀵 정렬은 분할 과정에서 원소 위치가 확정되어 분할이 끝나면 정렬도 끝나지만, 합병 정렬은 분할 후 합병 단계에서 정렬이 이루어지므로 옳다.

문제 13

[0]	[1]	[2]	[3]	[4]
	Z	X

연산 1. 원소 Y 삽입
연산 2. 원소 3개 삭제
연산 3. 원소 Q 삽입
연산 4. 원소 M 삽입
연산 5. 원소 A 삽입
연산 6. 원소 K 삽입
연산 7. 원소 2개 삭제

[0]	[1]	[2]	[3]	[4]
M				Q

[0]	[1]	[2]	[3]	[4]
	A	K

[0]	[1]	[2]	[3]	[4]
			Y	Q

[0]	[1]	[2]	[3]	[4]
M	A

정답 및 해설

연산을 모두 마친 뒤 큐에는 [1]에 A, [2]에 K만 남는다.

원형 큐는 front가 첫 원소의 바로 앞 칸, rear가 마지막 원소를 가리키고, 인덱스는 5로 나눈 나머지로 순환한다. 처음에는 [1]에 Z, [2]에 X가 있다.

[0]에 M, [4]에 Q가 남는 상태는 먼저 들어온 Q·M부터 삭제되는 선입선출 순서와 맞지 않는다.
[3]에 Y, [4]에 Q가 남는 상태는 앞선 3개 삭제에서 Y까지 빠진다는 점을 놓친 것이다.
[0]에 M, [1]에 A가 남는 상태는 K가 [2]에 삽입되고 M이 삭제된다는 점을 반영하지 못했다.

문제 14

1간선 (b, c) / 비용 16

2간선 (d, g) / 비용 18

3간선 (d, e) / 비용 22

4간선 (e, g) / 비용 25

정답 및 해설

5번째로 추가되는 간선은 (d, e), 비용 22이다.

다음 (d, g) 18은 이미 g-b-c-d로 연결된 두 정점을 잇게 되어 사이클이 생기므로 버려지고, 이어지는 (d, e) 22가 다섯 번째로 채택된다.

(b, c) 비용 16: 네 번째로 채택되는 간선이다.
(d, g) 비용 18: 사이클을 형성해 MST에 포함되지 않는다.
(e, g) 비용 25: e가 이미 d를 통해 연결된 뒤라 사이클이 생겨 제외된다.

문제 15

문자열 매칭을 위한 알고리즘으로 옳은 것은?

1합병 정렬 알고리즘

2라빈 카프(Rabin-Karp) 알고리즘

3백트래킹(backtracking) 알고리즘

4후위 순회(postorder traversal) 알고리즘

정답 및 해설

문자열 매칭 알고리즘은 라빈-카프 알고리즘이다.

라빈-카프는 패턴과 본문 구간을 해시 값으로 바꿔 비교하고, 한 칸 이동할 때 해시를 상수 시간에 갱신해 일치 후보를 빠르게 찾는다.

합병 정렬은 분할 정복 방식의 정렬 알고리즘이다.
백트래킹은 해 공간을 탐색하다 유망하지 않으면 되돌아가는 탐색 기법이다.
후위 순회는 트리의 노드를 왼쪽·오른쪽 서브트리 다음 루트 순으로 방문하는 순회 방법이다.

문제 16

// 입력: 가중 방향 그래프 G, 인접 행렬 A, 시작 정점 s
// 출력: s로부터 다른 모든 정점까지의 최단 경로의 길이
Dijkstra(G, A, s) {
    U = {s};
    for(모든 정점 v ∈ G)
        D[v] = A[s][v];
    while(U != G) {
        D[w]가 최소인 정점 w ∈ (G - U)를 선택
        U = U ∪ {w};
        for(w에 인접한 모든 정점 v) {
            D[v] = (가);
        }
    }
}

1min(D[v], D[v] ＋ A[v][w])

2min(D[v], D[w] ＋ A[v][w])

3min(D[v], D[v] ＋ A[w][v])

4min(D[v], D[w] ＋ A[w][v])

정답 및 해설

(가)에 들어갈 갱신식은 min(D[v], D[w] ＋ A[w][v])이다.

D[v] ＋ A[v][w]는 w를 거치는 경로가 아니라 v에서 출발하는 값이라 의미가 없다.
D[w] ＋ A[v][w]는 방향 그래프에서 간선 방향을 v→w로 거꾸로 읽은 것이다.
D[v] ＋ A[w][v]는 w까지의 거리 대신 v의 거리를 더해 w를 경유하는 경로가 아니다.

문제 17

KMP(Knuth-Morris-Pratt) 알고리즘과 보이어－무어(Boyer-Moore) 알고리즘에 대한 설명으로 옳지 않은 것은?

1KMP 알고리즘은 패턴 문자열의 첫 문자부터 순차적으로 대상 문자열과 부분 문자열의 일치 여부를 판단한다.

2KMP 알고리즘은 패턴 문자열과 대상 문자열을 한 차례 비교한 후 얻을 수 있는 추가 정보로 비교 횟수를 감소시킨다.

3보이어－무어 알고리즘은 패턴 문자열의 마지막 문자부터 역순으로 대상 문자열과 부분 문자열의 일치 여부를 판단한다.

4보이어－무어 알고리즘은 전처리(preprocessing) 과정 없이 곧바로 일치 여부를 판단할 수 있다.

정답 및 해설

옳지 않은 설명은 보이어-무어 알고리즘이 전처리 없이 곧바로 비교한다는 내용이다.

보이어-무어는 비교 전에 패턴을 분석해 나쁜 문자 이동표·착한 접미부 이동표를 만들어 두고, 불일치 시 이 표로 건너뛸 거리를 정한다.

KMP는 패턴의 첫 문자부터 왼쪽에서 오른쪽으로 비교하므로 옳다.
KMP는 앞선 비교에서 얻은 접두부·접미부 일치 정보(실패 함수)로 비교 횟수를 줄이므로 옳다.
보이어-무어는 패턴의 마지막 문자부터 역순으로 비교하므로 옳다.

문제 18

1트리의 개수 1 / 백트래킹 횟수 3

2트리의 개수 1 / 백트래킹 횟수 4

3트리의 개수 2 / 백트래킹 횟수 3

4트리의 개수 2 / 백트래킹 횟수 5

정답 및 해설

DFS를 조건대로 수행하면 트리는 2개, 백트래킹은 5회이다.

A → F로 간 뒤 F의 인접 정점 A·C가 이미 방문되어 A로 되돌아가고(4회), A에 남은 정점이 없어 첫 트리 {A, B, C, D, F}가 끝난다.

남은 정점 중 가장 앞선 E에서 다시 시작해 E → G로 간 뒤 G의 인접 정점 D·E가 방문되어 E로 되돌아가며(5회), 두 번째 트리 {E, G}가 만들어진다.

트리 1개·백트래킹 3회 조합: E와 G는 A에서 출발하는 간선으로 도달할 수 없어 DFS를 다시 시작해야 하므로 트리가 2개이다.
트리 1개·백트래킹 4회 조합: 4회는 첫 트리의 백트래킹만 센 값이며, E에서 다시 시작하는 두 번째 트리가 빠졌다.
트리 2개·백트래킹 3회 조합: 첫 트리에서만 4회, 두 번째 트리에서 1회가 발생해 합계 5회이다.

문제 19

다음은 n개의 데이터에 대한 평균을 재귀적으로 계산하는 프로그램이다. (가) ～ (다)에 들어갈 내용을 바르게 연결한 것은? (단, n ≥ 1이다)

float AVG(float (가), int n) {
 if(n == 1) return (나);
  else
   return (data[n - 1] + (n - 1) * AVG(data, n - 1)) / (다);
}

1(가) data[] / (나) 0 / (다) n

2(가) data[] / (나) 1 / (다) (n-1)

3(가) *data / (나) data[0] / (다) n

4(가) *data / (나) data[n-1] / (다) (n-1)

정답 및 해설

(가)는 *data, (나)는 data[0], (다)는 n이다.

원소가 하나면 평균은 그 원소 자신이므로 data[0]을 반환한다.

(나)를 0으로 두면 원소가 하나일 때 평균이 항상 0이 되어 틀렸다.
(나)를 1로, (다)를 (n-1)로 두면 기저값과 나누는 개수가 모두 맞지 않는다.
(나)를 data[n-1]로, (다)를 (n-1)로 두면 n개 합을 n-1로 나누게 되어 평균이 아니다.

문제 20

작업 선택 문제를 다루는 다음 알고리즘은 각 작업의 시작 시간 s와 완료 시간 f가 정해진

n

ActSelect(n, t[]) {
    (가) 의 오름차순으로 작업 t[]를 정렬;
    count = 0, last = 0, jobs[];
    jobs[count] = 0;
    for(i = 0; i < n; i++)
        if( (나) ) {
            count++;
            last = i;
            jobs[count] = last;
        }
    return jobs;
}

1(가) 시작 시간 / (나) t[i].s >= t[last].f

2(가) 시작 시간 / (나) t[i].f >= t[last].s

3(가) 완료 시간 / (나) t[i].s >= t[last].f

4(가) 완료 시간 / (나) t[i].f >= t[last].s

정답 및 해설

(가)는 완료 시간, (나)는 t[i].s >= t[last].f이다.

작업 선택 문제의 탐욕 전략은 가장 일찍 끝나는 작업부터 고르는 것으로, 그래야 남은 시간에 더 많은 작업을 넣을 수 있다.

정렬 후에는 현재 작업의 시작 시간이 마지막으로 선택한 작업의 종료 시간 이후일 때만 충돌이 없으므로 선택한다.

시작 시간 순으로 정렬하면 일찍 시작하지만 오래 걸리는 작업이 먼저 뽑혀 최대 개수를 보장하지 못한다.
시작 시간 순 정렬에 종료·시작 시간을 비교하는 조건은 정렬 기준과 겹침 판정이 모두 틀렸다.
완료 시간 순 정렬이라도 현재 작업의 종료 시간과 마지막 작업의 시작 시간을 비교하면 시간 겹침을 막지 못한다.

문제 21

동적 프로그래밍(dynamic programming) 방법으로 최소의 원소단위 곱셈 횟수를 갖도록 연쇄 행렬곱셈(matrix-chain multiplication)의 순서를 정하려 한다.

c_{i,j}

를 행렬

M_i

부터

M_j

까지의 연쇄 행렬곱셈의 최소 비용이라고 할 때,

c_{i,j}

에 대한 관계식으로 옳은 것은? (단,

i \lt j

이고, 각 행렬의 차원이

p_0, p_1, \ldots ,p_n

일 때, 행렬

M_i

의 크기는

p_{i-1} \times p_i

이다)

c_{i,j} = \begin{cases} 0 & \text{if } i = j \\ \min_{i \le k \le j-1}\{c_{i,k}+c_{k+1,j}+p_{i-1}p_kp_j\} & \text{if } i \lt j \end{cases}

c_{i,j} = \begin{cases} 0 & \text{if } i = j \\ \min_{i \le k \le j-1}\{c_{i,k}+c_{k,j}+p_{i-1}p_{k-1}p_j\} & \text{if } i \lt j \end{cases}

c_{i,j} = \begin{cases} 0 & \text{if } i = j \\ \min_{i \le k \le j-1}\{c_{i,k-1}+c_{k,j}+p_{i-1}p_{k-1}p_j\} & \text{if } i \lt j \end{cases}

c_{i,j} = \begin{cases} 0 & \text{if } i = j \\ \min_{i \le k \le j-1}\{c_{i,k}+c_{k,j}+p_{i-1}p_kp_j\} & \text{if } i \lt j \end{cases}

정답 및 해설

올바른 관계식은 $c_{i,j}=\min_{i \le k \le j-1}\{c_{i,k}+c_{k+1,j}+p_{i-1}p_kp_j\}$ 이다.

$c_{i,k}+c_{k,j}+p_{i-1}p_{k-1}p_j$ 식은 행렬 $M_k$ 를 두 부분에 중복 포함하고 곱셈 비용의 차원도 맞지 않는다.
$c_{i,k-1}+c_{k,j}$ 식은 k의 범위가 $i \le k \le j-1$ 이므로 k=i일 때 정의되지 않는 $c_{i,i-1}$ 가 나오고 마지막 분할도 빠진다.
$c_{i,k}+c_{k,j}+p_{i-1}p_kp_j$ 식은 $M_k$ 를 양쪽 부분에 중복 포함한다.

문제 22

public class Fibonacci {
    static int[] dp = new int[100];

    public static void main(String[] args) {
        System.out.println(fibo(6));
    }

    public static int fibo(int num) {
        if(num == 0) {
            return 0;
        }
        if(num == 1) {
            return 1;
        }
        if(dp[num] != 0) {
            return dp[num];
        }
        return dp[num] = fibo(num - 1) + fibo(num - 2);
    }
}

정답 및 해설

fibo(6)을 구하는 동안 저장된 fibo(3)의 값을 꺼내 쓰는 것은 한 번이다.

호출은 fibo(6)→fibo(5)→fibo(4)→fibo(3)→fibo(2) 순으로 왼쪽 가지를 먼저 내려가며 dp[2]·dp[3]·dp[4]·dp[5]를 차례로 저장한다.

0회는 fibo(5)의 오른쪽 호출이 저장값으로 처리된다는 점을 놓친 것이다.
2회나 3회는 저장값이 없을 때처럼 fibo(4)를 다시 전개한 경우로, 메모이제이션에서는 일어나지 않는다.

문제 23

배낭 문제(knapsack problem)에 대한 설명으로 옳은 것은?

10－1 배낭 문제와 분할 가능 배낭 문제는 다항식 시간(polynomial-time) 문제이다.

2분할 가능 배낭 문제는 최적 부분 구조를 갖지만, 0－1 배낭 문제는 그렇지 않다.

4분할 가능 배낭 문제는 ‘단위 무게당 가치가 가장 높은 물건을 선택’하는 방식이 항상 최적해를 보장하지만, 0－1 배낭 문제는 그렇지 않다.

정답 및 해설

0-1 배낭 문제는 물건을 쪼갤 수 없어 탐욕 선택이 남는 용량을 낭비할 수 있으므로 동적 프로그래밍으로 풀어야 한다.

0-1 배낭 문제는 NP-난해 문제(결정 문제는 NP-완전)로, 다항식 시간 알고리즘이 알려져 있지 않다.
0-1 배낭 문제도 최적 부분 구조를 가지며, 그래서 동적 프로그래밍을 적용할 수 있다.
탐욕 알고리즘이 맞는 쪽은 분할 가능 배낭이고, 동적 프로그래밍이 필요한 쪽은 0-1 배낭이므로 설명이 뒤바뀌었다.

문제 24

알고리즘들에 대한 설명으로 옳지 않은 것은?

1크루스칼의 최소 신장 트리 알고리즘은 가중치가 가장 작으면서 사이클을 만들지 않는 간선을 추가하여 트리를 구성한다.

2프림(Prim)의 최소 신장 트리 알고리즘은 현재까지 만들어진 트리에 최소 가중치로 연결되는 정점을 트리에 추가한다.

3허프만(Huffman) 압축에서 파일에 빈번히 나타나는 문자는 긴 이진코드를 할당하고, 드물게 나타나는 문자는 짧은 이진코드를 할당한다.

정답 및 해설

옳지 않은 설명은 허프만 압축에서 자주 나오는 문자에 긴 코드를 준다는 내용이다.

허프만 코드는 빈도가 높은 문자에 짧은 코드, 빈도가 낮은 문자에 긴 코드를 할당해 전체 비트 수를 줄인다.

크루스칼 알고리즘은 가중치가 작은 간선부터 사이클을 만들지 않는 것만 추가하므로 옳다.
프림 알고리즘은 현재 트리에 최소 가중치로 연결되는 정점을 하나씩 추가하므로 옳다.
벨만-포드 알고리즘은 음의 가중치 간선이 있어도 단일 출발점 최단 경로를 구하므로 옳다.

문제 25

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

1유클리드(Euclid) 알고리즘

2스트라센(Strassen) 알고리즘

3몬테카를로(Monte Carlo) 알고리즘

4플로이드－워샬(Floyd-Warshall) 알고리즘

정답 및 해설

설명에 해당하는 알고리즘은 몬테카를로 알고리즘이다.

몬테카를로는 난수를 이용하는 확률적 알고리즘으로, 정해진 시간 안에 끝나지만 결과가 근사해이거나 일정 확률로 틀릴 수 있다.

유클리드 알고리즘은 최대공약수를 정확히 구하는 결정론적 알고리즘이다.
스트라센 알고리즘은 분할 정복으로 행렬 곱셈 횟수를 줄이는 결정론적 알고리즘이다.
플로이드-워샬 알고리즘은 동적 프로그래밍으로 모든 정점 쌍의 최단 경로를 정확히 구한다.