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

레드-블랙 트리의 특성으로 옳은 것은 모든 노드가 레드 또는 블랙이라는 것과 레드 노드의 자식은 항상 블랙이라는 것이다.
레드-블랙 트리는 색 규칙(루트·NIL 리프는 블랙, 레드 노드 연속 금지, 루트에서 각 NIL까지 블랙 노드 수 동일)으로 높이를 $O(\log n)$로 유지한다.
루트 노드는 레드가 아니라 블랙이어야 한다.
모든 리프 노드(NIL)도 레드가 아니라 블랙이다.

동적 계획법에서 부분 문제들 사이에 의존 관계가 없다는 설명은 옳지 않다.
동적 계획법은 큰 문제의 해가 작은 부분 문제의 해에 의존하고, 같은 부분 문제가 반복해서 나타나는(중복 부분 문제) 상황에 쓰인다. 부분 문제들이 서로 독립적인 것은 분할 정복의 특징이다.
부분 문제의 해를 테이블에 저장해 다시 풀지 않는 것은 동적 계획법의 핵심이다.
문제를 작은 문제로 나누어 풀고 그 해로 원래 문제의 해를 구하는 것은 옳은 설명이다.
최적의 해가 부분 문제의 최적해로 구성된다는 최적성의 원리가 성립해야 적용할 수 있다.

옳지 않은 것은 push를 요소를 제거하는 연산으로 설명한 것이다.
스택에서 top의 요소를 꺼내 외부로 건네주는 연산은 pop이고, push는 top 위치에 새 요소를 삽입하는 연산이다.
나중에 들어온 데이터가 먼저 나가는 후입 선출(LIFO) 구조는 스택의 정의이다.
먼저 들어온 데이터가 맨 아래, 최근 데이터가 맨 위에 쌓이는 구조라는 설명은 옳다.
함수 호출 시 복귀 주소를 스택에 저장해 가장 최근 호출한 함수로 돌아가는 것도 옳다.

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

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

설명에 해당하는 기법은 백트래킹이다.
백트래킹은 상태 공간 트리를 깊이 우선 탐색하다가 해가 될 가능성이 없는 노드를 만나면 부모로 되돌아가 다른 경로를 탐색하며, 결정 문제와 최적화 문제 모두에 쓰인다.
k-NN은 가장 가까운 k개의 이웃으로 분류·회귀를 하는 기계학습 기법으로 되돌아가는 탐색과 무관하다.
그리디 알고리즘은 매 순간 최선의 선택을 하고 되돌아가지 않는다.
분할 정복은 문제를 독립적인 부분 문제로 나누어 풀고 결합하는 기법이다.

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

가능한 깊이 우선 탐색 순서는 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를 방문할 수 없다.

생성된 최소 신장 트리의 간선은 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개로 고정된다.

설명에 해당하는 정렬은 삽입 정렬이다.
삽입 정렬은 앞부분을 정렬된 상태로 유지하며 뒷부분의 원소를 하나씩 알맞은 위치에 끼워 넣는다. 이미 정렬된 입력이면 원소마다 비교 한 번으로 끝나 최선 $O(n)$, 역순이면 최악 $O(n^2)$이다.
버블 정렬은 인접 원소 교환으로 큰 값을 뒤로 보내며, 정렬된 뒷부분을 만드는 방식이다.
병합 정렬은 분할 정복으로 최선·최악 모두 $O(n\log n)$이다.
선택 정렬은 입력 상태와 관계없이 최솟값을 찾으므로 최선의 경우에도 $O(n^2)$이다.

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을 삽입할 때 분할 연산이 필요하다: 오버플로를 해소하려면 리프와 루트에서 차례로 분할해야 한다.

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

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

옳은 설명은 간선 <i, j>가 있으면 정점 i가 정점 j를 선행한다는 것이다.
위상 정렬은 방향 비순환 그래프(DAG)의 정점을 모든 간선 i→j에 대해 i가 j보다 앞에 오도록 나열하는 것이다.
DFS의 종료 순서를 역순으로 나열하는 방식으로 위상 정렬을 구현할 수 있다.
선후 관계가 없는 정점들의 순서는 바꿀 수 있으므로 위상 정렬 결과는 여러 개 존재할 수 있다.
사이클이 없어도 무방향 그래프에는 선행 관계가 없으므로 적용할 수 없고, 방향 그래프에만 적용된다.

프로그램은 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가 출력된다.

허프만 코드로 인코딩한 전체 비트 수는 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)

기수 정렬에 대한 옳은 설명은 추가 저장공간이 필요하다는 것과 안정적 정렬이라는 것이다.
기수 정렬은 키를 자릿수별로 나누어 각 자릿수에 대해 버킷(또는 계수 정렬)으로 분배하는 방식이며, 하위 자릿수 결과를 보존하려면 각 단계의 정렬이 안정적이어야 한다.
원소끼리 크기를 비교하지 않고 자릿수 값으로 분배하므로 비교 기반 정렬이 아니다.
자릿수가 d, 기수가 k이면 시간 복잡도는 $O(d(n+k))$로, 비교 정렬의 하한인 $O(n\log n)$이 아니라 선형 시간에 가깝다.

(가)에 들어갈 코드로 옳지 않은 것은 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이므로 옳다.

프로그램은 회전 횟수 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이다.

모든 정점을 한 번씩 방문하고 출발점으로 돌아오는 최단 경로 문제는 여행자 문제(TSP)이다.
TSP는 최소 비용 해밀턴 순환을 찾는 문제로, 대표적인 NP-하드 최적화 문제이다.
통 채우기 문제는 크기가 다른 물건을 최소 개수의 통에 담는 문제이다.
정점 커버 문제는 모든 간선의 끝점 중 하나 이상을 포함하는 최소 정점 집합을 찾는 문제이다.
그래프 색칠하기 문제는 인접한 정점이 다른 색이 되도록 최소 색 수로 칠하는 문제이다.

옳지 않은 것은 평균 경우 분석이 모든 입력의 수행 시간을 알고 계산하므로 많이 사용된다는 설명이다.
평균 경우 분석은 입력의 확률 분포를 가정해야 하고 계산이 어려워 실제로는 덜 쓰이며, 성능을 보장하는 최악 경우 분석이 시간 복잡도의 척도로 가장 많이 사용된다.
최악 경우 분석은 어떤 입력에도 그 이상 걸리지 않는다는 상한의 의미를 가진다.
최선 경우 분석은 수행 시간이 가장 적게 걸리는 입력에 대한 분석이다.
상각 분석은 일련의 연산 전체 시간을 연산 수로 나누어 연산당 평균 비용을 구한다.

알고리즘 개발 단계는 설계 → 정확성 검증 → 분석 → 구현 순서이다.
먼저 문제를 해결할 절차를 설계하고, 그 절차가 모든 입력에 대해 올바른 결과를 내는지 정확성을 검증한 뒤, 시간·공간 효율을 분석하고, 마지막으로 프로그래밍 언어로 구현한다.
분석은 정확성이 검증된 알고리즘을 대상으로 하므로 정확성 검증보다 앞설 수 없다.
설계되지 않은 알고리즘은 분석할 대상이 없으므로 분석이 설계보다 먼저 올 수 없다.

그리디 알고리즘에 해당하는 것은 크루스칼 알고리즘이다.
크루스칼 알고리즘은 사이클을 만들지 않는 범위에서 가중치가 가장 작은 간선을 매번 선택해 최소 신장 트리를 만드는 탐욕적 선택 방식이다.
0/1 배낭 문제는 물건을 쪼갤 수 없어 그리디로 최적해가 보장되지 않으며 동적 계획법으로 푼다.
플로이드-워셜 알고리즘은 경유 정점을 하나씩 늘려 가는 동적 계획법이다.
최장 공통 부분 수열은 부분 문제 표를 채우는 동적 계획법으로 구한다.

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

프로그램은 이진 탐색 트리의 전위 순회 결과 [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