[7급 국가직 알고리즘] 25년 1회차 기출문제 정답·해설 페이지

알고리즘 조건의 정의를 바꿔 쓴 것은 명확성에 대한 설명이다.
명확성은 각 명령어의 의미가 모호하지 않고 분명해야 한다는 조건이며, 명령어가 실제로 실행 가능한 연산이어야 한다는 것은 유효성(효과성)에 해당한다.
입력 조건은 외부에서 주어지는 자료가 0개 이상이면 된다는 뜻으로 옳다.
출력 조건은 적어도 하나 이상의 결과를 만들어야 한다는 뜻으로 옳다.
유한성 조건은 한정된 단계를 거친 뒤 반드시 종료해야 한다는 뜻으로 옳다.

점근 표기법은 입력 크기가 커질 때 수행 시간의 증가 추세를 대략적으로 나타내는 방법이다.
상수 계수와 낮은 차수 항을 무시하고 가장 빠르게 증가하는 항만으로 복잡도를 표현한다.
O 표기는 수행 시간의 점근적 상한을 나타내며, 하한을 나타내는 것은 Ω 표기이다.
순차 탐색은 최악의 경우 n개 원소를 모두 비교하므로 $\mathrm{O}(n)$이다.
$10n^2+3n+2$는 최고차항이 $n^2$이므로 $\mathrm{O}(n^2)$이며, $\mathrm{O}(n)$으로 표기할 수 없다.

교환 후 힙 재구성을 마치면 배열은 -, 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 하나만 아래로 내리는 연산 결과와 다르다.

제시된 과정은 선택 정렬이다.
매 단계마다 미정렬 구간의 최솟값을 찾아 구간 맨 앞 원소와 교환한다. 첫 단계에서 최솟값 3이 69와, 다음 단계에서 8이 10과 자리를 바꾸는 식으로 앞에서부터 하나씩 확정된다.
버블 정렬은 인접한 두 원소만 비교·교환하므로 첫 단계에서 3이 멀리 떨어진 맨 앞으로 한 번에 옮겨질 수 없다.
합병 정렬은 배열을 반씩 나눈 뒤 정렬된 부분 배열을 합치므로 앞에서부터 원소가 하나씩 확정되는 모양이 아니다.
기수 정렬은 자릿수별로 분배·수집하므로 일의 자리 기준 첫 단계에서 10·30이 맨 앞에 모이는 등 다른 순서가 나온다.

올바른 후위 표기는 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처럼 연산자가 피연산자 앞에 오는 것은 전위 표기의 형태이다.

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이다.

최종 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가 모두 자식을 가진 내부 노드라서 틀렸다.

방문 순서가 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에서 모든 정점에 도달한다.

함수 실행이 끝나면 A[0]에 가장 큰 원소가 저장된다.
인접한 두 원소를 비교해 앞의 값이 더 작으면 교환하는 버블 정렬로, 매 반복마다 가장 작은 값이 뒤로 밀려나 배열이 내림차순으로 정렬된다.
작은 값이 뒤로 가도록 교환하므로 결과는 오름차순이 아니라 내림차순이다.
교환이 없어도 조기 종료하는 장치가 없어 비교 횟수가 항상 같으므로, 최선과 최악 모두 $\mathrm{O}(n^2)$로 같다.
인접 원소를 비교·교환하는 방식은 삽입 정렬이 아니라 버블 정렬이다.

모든 자료를 삽입하면 (가)는 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가 있다.

이 재귀 피보나치 함수의 시간 복잡도는 지수 시간 $\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)$은 행렬 거듭제곱을 이용한 방법의 복잡도이다.

옳지 않은 설명은 합병 정렬이 추가 저장공간이 필요 없는 제자리 정렬이라는 내용이다.
합병 정렬은 정렬된 두 부분 배열을 합칠 때 입력 크기만큼의 보조 배열이 필요하므로 제자리 정렬이 아니다.
2-way 합병 정렬은 분할 대상을 반으로 나누므로 옳다.
퀵 정렬은 피봇보다 작은 값과 큰 값으로 분할하므로 옳다.
퀵 정렬은 분할 과정에서 원소 위치가 확정되어 분할이 끝나면 정렬도 끝나지만, 합병 정렬은 분할 후 합병 단계에서 정렬이 이루어지므로 옳다.

연산을 모두 마친 뒤 큐에는 [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이 삭제된다는 점을 반영하지 못했다.

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를 통해 연결된 뒤라 사이클이 생겨 제외된다.

문자열 매칭 알고리즘은 라빈-카프 알고리즘이다.
라빈-카프는 패턴과 본문 구간을 해시 값으로 바꿔 비교하고, 한 칸 이동할 때 해시를 상수 시간에 갱신해 일치 후보를 빠르게 찾는다.
합병 정렬은 분할 정복 방식의 정렬 알고리즘이다.
백트래킹은 해 공간을 탐색하다 유망하지 않으면 되돌아가는 탐색 기법이다.
후위 순회는 트리의 노드를 왼쪽·오른쪽 서브트리 다음 루트 순으로 방문하는 순회 방법이다.

(가)에 들어갈 갱신식은 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를 경유하는 경로가 아니다.

옳지 않은 설명은 보이어-무어 알고리즘이 전처리 없이 곧바로 비교한다는 내용이다.
보이어-무어는 비교 전에 패턴을 분석해 나쁜 문자 이동표·착한 접미부 이동표를 만들어 두고, 불일치 시 이 표로 건너뛸 거리를 정한다.
KMP는 패턴의 첫 문자부터 왼쪽에서 오른쪽으로 비교하므로 옳다.
KMP는 앞선 비교에서 얻은 접두부·접미부 일치 정보(실패 함수)로 비교 횟수를 줄이므로 옳다.
보이어-무어는 패턴의 마지막 문자부터 역순으로 비교하므로 옳다.

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회이다.

(가)는 *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로 나누게 되어 평균이 아니다.

(가)는 완료 시간, (나)는 t[i].s >= t[last].f이다.
작업 선택 문제의 탐욕 전략은 가장 일찍 끝나는 작업부터 고르는 것으로, 그래야 남은 시간에 더 많은 작업을 넣을 수 있다.
정렬 후에는 현재 작업의 시작 시간이 마지막으로 선택한 작업의 종료 시간 이후일 때만 충돌이 없으므로 선택한다.
시작 시간 순으로 정렬하면 일찍 시작하지만 오래 걸리는 작업이 먼저 뽑혀 최대 개수를 보장하지 못한다.
시작 시간 순 정렬에 종료·시작 시간을 비교하는 조건은 정렬 기준과 겹침 판정이 모두 틀렸다.
완료 시간 순 정렬이라도 현재 작업의 종료 시간과 마지막 작업의 시작 시간을 비교하면 시간 겹침을 막지 못한다.

올바른 관계식은 $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$를 양쪽 부분에 중복 포함한다.

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)를 다시 전개한 경우로, 메모이제이션에서는 일어나지 않는다.

옳은 설명은 분할 가능 배낭 문제는 단위 무게당 가치가 높은 물건부터 고르는 탐욕법이 최적해를 보장하지만 0-1 배낭 문제는 그렇지 않다는 것이다.
0-1 배낭 문제는 물건을 쪼갤 수 없어 탐욕 선택이 남는 용량을 낭비할 수 있으므로 동적 프로그래밍으로 풀어야 한다.
0-1 배낭 문제는 NP-난해 문제(결정 문제는 NP-완전)로, 다항식 시간 알고리즘이 알려져 있지 않다.
0-1 배낭 문제도 최적 부분 구조를 가지며, 그래서 동적 프로그래밍을 적용할 수 있다.
탐욕 알고리즘이 맞는 쪽은 분할 가능 배낭이고, 동적 프로그래밍이 필요한 쪽은 0-1 배낭이므로 설명이 뒤바뀌었다.

옳지 않은 설명은 허프만 압축에서 자주 나오는 문자에 긴 코드를 준다는 내용이다.
허프만 코드는 빈도가 높은 문자에 짧은 코드, 빈도가 낮은 문자에 긴 코드를 할당해 전체 비트 수를 줄인다.
크루스칼 알고리즘은 가중치가 작은 간선부터 사이클을 만들지 않는 것만 추가하므로 옳다.
프림 알고리즘은 현재 트리에 최소 가중치로 연결되는 정점을 하나씩 추가하므로 옳다.
벨만-포드 알고리즘은 음의 가중치 간선이 있어도 단일 출발점 최단 경로를 구하므로 옳다.

설명에 해당하는 알고리즘은 몬테카를로 알고리즘이다.
몬테카를로는 난수를 이용하는 확률적 알고리즘으로, 정해진 시간 안에 끝나지만 결과가 근사해이거나 일정 확률로 틀릴 수 있다.
유클리드 알고리즘은 최대공약수를 정확히 구하는 결정론적 알고리즘이다.
스트라센 알고리즘은 분할 정복으로 행렬 곱셈 횟수를 줄이는 결정론적 알고리즘이다.
플로이드-워샬 알고리즘은 동적 프로그래밍으로 모든 정점 쌍의 최단 경로를 정확히 구한다.