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

정점이 6개인 무방향 완전 그래프의 간선 수는 15개이다.
완전 그래프는 서로 다른 모든 정점 쌍이 간선 하나로 연결되므로, 간선 수는 정점 2개를 고르는 조합의 수와 같다.
$\dfrac{n(n-1)}{2} = \dfrac{6 \times 5}{2} = 15$
6개는 정점 6개를 한 바퀴 잇는 사이클 그래프의 간선 수에 불과하다.
12개는 모든 정점의 차수가 4인 그래프의 간선 수로, 완전 그래프의 차수 5보다 작다.
21개는 정점이 7개인 완전 그래프의 간선 수이다.

(가)~(다)는 차례로 (2, 5) → (2, 5, 7) → (5, 7)이다.
큐는 선입선출(FIFO) 구조로, 삭제는 맨 앞에서, 삽입은 맨 뒤에서 일어난다.
(1, 2, 5)에서 dequeue로 맨 앞의 1이 빠져 (2, 5), enqueue(7)로 뒤에 7이 붙어 (2, 5, 7), 다시 dequeue로 맨 앞의 2가 빠져 (5, 7)이 된다.
(1, 2) → (1, 2, 7) → (1, 2)는 맨 뒤에서 꺼내는 스택(LIFO) 방식으로 처리한 결과이다.
(2, 5) → (5, 7) → (7)은 enqueue(7)에서도 원소를 하나 삭제한 것처럼 처리해 연산 정의와 맞지 않는다.
(2, 5, 1)로 시작하는 결과는 삭제한 1을 다시 뒤에 넣은 회전처럼 처리한 것으로, 삭제 연산의 정의와 맞지 않는다.

옳지 않은 설명은 노드 B가 노드 F보다 큰 키 값을 가져야 한다는 것이다.
최대 힙은 완전 이진 트리이면서 부모의 키가 자식의 키보다 크거나 같다는 조건만 만족하면 된다. B는 A의 왼쪽 서브트리, F는 C의 자식으로 서로 조상·자손 관계가 아니므로 둘 사이의 크기는 정해지지 않는다.
완전 이진 트리 조건: 힙은 배열로 표현하기 위해 마지막 레벨을 왼쪽부터 채운 완전 이진 트리여야 한다.
루트 A의 키: 모든 노드의 조상이므로 가장 큰 키를 가진다.
B와 D의 키가 같은 경우: 부모가 자식보다 크거나 같으면 되므로 같은 키도 허용된다.

그리디로 최적해가 보장되지 않는 것은 0-1 배낭 문제이다.
물건을 쪼갤 수 없으므로 단위 무게당 가치가 큰 순으로 담으면 남는 용량을 낭비해 최적을 놓칠 수 있어, 동적 계획법으로 풀어야 한다. 물건을 쪼갤 수 있는 분할 배낭 문제는 그리디로 최적해를 얻는다.
허프만 코딩은 빈도가 가장 작은 두 노드를 반복 병합하는 그리디로 최적 접두 코드를 만든다.
최소 신장 트리는 크루스칼·프림 알고리즘이 가장 가벼운 안전 간선을 고르는 그리디로 최적해를 보장한다.
다익스트라 최단 경로는 간선 가중치가 음수가 아니면 거리가 가장 짧은 정점부터 확정하는 그리디로 최적해를 보장한다.

이 재귀 알고리즘의 시간 복잡도는 $\Theta(\log n)$이다.
호출 한 번마다 덧셈 하나의 상수 작업을 하고, 크기를 절반으로 줄여 한 번만 재귀하므로 점화식은 $T(n) = T(n/2) + \Theta(1)$이다.
n이 0 이하가 될 때까지 절반씩 줄어드는 횟수는 약 $\log_2 n$회이므로 전체 시간은 $\Theta(\log n)$이다.
$\Theta(n)$은 크기를 1씩 줄이는 재귀 $T(n)=T(n-1)+\Theta(1)$의 복잡도이다.
$\Theta(n\log n)$은 두 번 재귀하고 선형 작업을 하는 $T(n)=2T(n/2)+\Theta(n)$의 복잡도이다.
$\Theta(n^2)$은 크기를 1씩 줄이며 매번 선형 작업을 하는 $T(n)=T(n-1)+\Theta(n)$의 복잡도이다.

빈칸에는 i in range(1, n+1)이 들어간다.
파이썬 range(a, b)는 a부터 b-1까지의 정수를 만들므로, 1부터 n까지 더하려면 끝값을 n+1로 주어야 한다.
range(-1, n+1)은 -1과 0이 함께 더해져 결과가 1 작아진다.
range(0, n)은 0부터 n-1까지라 마지막 n이 빠진다.
range(1, n)은 1부터 n-1까지라 마지막 n이 빠진다.

옳지 않은 것은 NP-Complete 문제 중에 NP에 속하지 않는 문제가 있다는 설명이다.
NP-Complete는 정의상 NP에 속하면서 모든 NP 문제가 다항식 시간에 환원되는 문제이므로, 모든 NP-Complete 문제는 NP에 속한다. NP에 속하지 않을 수 있는 것은 NP-Hard 문제이다.
P를 다항식 시간에 해결할 수 있는 문제군으로 설명한 것은 옳다.
NP를 비결정론적 다항식 시간에 해결할 수 있는(해를 다항식 시간에 검증할 수 있는) 문제군으로 설명한 것은 옳다.
모든 NP 문제가 각 NP-Complete 문제로 환원되므로, 하나를 다항식 시간에 풀면 다른 NP-Complete 문제도 다항식 시간에 풀린다는 설명은 옳다.

fib(17) 실행 시 fib(8)은 55회, fib(10)은 21회 호출된다.
fib(k)를 호출하는 것은 fib(k+1)과 fib(k+2)뿐이므로, 호출 횟수를 C(k)라 하면 $C(k)=C(k+1)+C(k+2)$, $C(17)=C(16)=1$이 되어 피보나치 수열을 이룬다. 즉 $C(k)=F(18-k)$이다.
$C(8)=F(10)=55$
$C(10)=F(8)=21$
52회·13회 조합은 두 값이 모두 틀리다. 13회는 fib(11)의 호출 횟수이다.
52회·21회 조합은 fib(10)은 맞지만 fib(8)을 55회가 아닌 52회로 잡아 틀리다.
55회·13회 조합은 fib(8)은 맞지만 13회는 fib(11)의 호출 횟수이다.

옳지 않은 설명은 노드 25를 삭제할 때 그 자리에 노드 30을 놓는다는 것이다.
25는 왼쪽 자식 20과 오른쪽 자식 30을 모두 가지므로, 그 자리에는 왼쪽 서브트리의 최댓값 20이나 오른쪽 서브트리의 최솟값 27이 와야 한다. 30을 올리면 30의 왼쪽에 있던 27·29와 20을 함께 재배치해야 해 이동 횟수가 최소가 되지 않는다.
노드 8 삭제: 자식이 없는 리프이므로 부모 15의 해당 포인터만 NIL로 바꾸면 된다.
노드 50 삭제: 오른쪽 자식 60 하나만 가지므로 부모 40이 60을 직접 가리키게 하면 된다.
노드 60 삭제: 자식이 둘이므로 선행자 55나 후계자 66을 그 자리에 놓는다.

레드-블랙 트리는 루트 35 아래 레드 20(자식 블랙 10·블랙 25, 25의 오른쪽 레드 30)과 블랙 50(자식 레드 40·레드 60)이 놓인 트리이다.
이 트리는 이진 검색 트리 순서를 지키고, 레드 노드의 자식이 모두 블랙이며, 루트에서 모든 외부 노드까지의 블랙 노드 수가 2개로 같다.
루트 30의 왼쪽 블랙 10 아래 레드 20, 그 아래 레드 25가 이어진 트리: 레드 노드가 연속해 레드 자식을 가질 수 없다는 조건을 어긴다.
루트 30의 오른쪽 블랙 65 아래 레드 40, 그 아래 블랙 50이 있는 트리: 50을 거치는 경로만 블랙 노드가 3개가 되어 블랙 높이가 다르다.
루트 30의 오른쪽 레드 50 아래 블랙 40의 오른쪽에 55가 있는 트리: 55가 50의 왼쪽 서브트리에 있어 이진 검색 트리 순서를 어긴다.

옳지 않은 것은 별도 체이닝과 오픈 주소 방법 모두 추가 저장 공간이 필요 없다는 설명이다.
별도 체이닝은 충돌한 원소를 테이블 밖의 연결 리스트에 매달므로 노드와 포인터를 위한 추가 공간이 필요하다. 추가 공간 없이 테이블 내부의 빈 칸을 찾아 저장하는 것은 오픈 주소 방법이다.
충돌이 없으면 해시 함수 계산 한 번으로 주소가 정해지므로 검색·저장이 $O(1)$이라는 설명은 옳다.
해시 함수를 나누기(제산) 방법뿐 아니라 곱하기(승산) 방법으로도 만들 수 있다는 설명은 옳다.
적재율이 높을수록 충돌이 잦아져 성능이 떨어지므로 적재율이 성능에 중요한 영향을 준다는 설명은 옳다.

프림 알고리즘으로 선택되는 마지막 정점은 C이다.
매 단계 트리와 바깥 정점을 잇는 최소 간선을 고르면 B(7), D(8), E(4), H(3) 순으로 붙는다. 이때 남은 후보는 B–F 9, D–C 10, H–C 11, H–G 14이므로 F가 9로 선택된다.
이어서 F–G 1로 G가 붙고, 마지막으로 G–C 2로 C가 선택된다.
F: 다섯 번째로 선택되며 B–F 간선 9가 D–C 10보다 작아 C보다 먼저 붙는다.
G: F가 들어온 직후 가중치 1인 F–G 간선으로 여섯 번째에 선택된다.
H: E가 들어온 직후 E–H 간선 3으로 네 번째에 선택된다.

정점 a에서 f까지의 최단 거리는 10이며, 경로는 a→b→c→e→d→f이다.
a에서 b까지 1, b→c 간선 2로 c까지 3이 되어 직행 간선 a→c 5보다 짧다. c→e 1로 e까지 4가 되고, e→d 2로 d까지 6이 되어 a→d 8보다 짧다.
f로 가는 간선은 d→f 4와 e→f 7이므로 6+4=10이 4+7=11보다 작다.
11: e에서 f로 바로 가는 경로의 거리로, d를 거치는 경로보다 1 길다.
12: a→d 직행 간선 8에 d→f 4를 더한 거리로 최단이 아니다.
13: 어떤 최단 경로 갱신 과정에서도 f의 최종 거리로 남지 않는다.

실행 결과는 9이다.
test(n)은 n이 음수가 될 때까지 n을 2씩 줄이며 더한다.
test(5) = 5 + test(3)
= 5 + 3 + test(1)
= 5 + 3 + 1 + test(-1)
= 9 + 0 = 9
5는 첫 항만 더하고 재귀 결과를 빠뜨린 값이다.
8은 5+3까지만 더하고 test(1)의 1을 빠뜨린 값이다.
10은 1부터 4까지의 합으로, 2씩 감소하는 5+3+1과 맞지 않는다.

크루스칼 알고리즘에서 마지막으로 포함되는 간선은 (c, d)이다.
가중치 순으로 (a, c) 1, (h, g) 1, (a, e) 2, (b, c) 2, (e, g) 2를 채택하면 a, b, c, e, g, h가 하나로 묶인다. 가중치 3에서는 (h, e)가 사이클을 만들어 버리고 (g, f)를 채택한다.
가중치 4·5의 (h, c), (a, b), (c, g)는 모두 사이클을 만들고, d를 처음 연결하는 (c, d) 5가 일곱 번째 간선으로 채택되어 신장 트리가 완성된다.
(a, b): a와 b가 이미 (a, c)·(b, c)로 연결되어 있어 사이클을 만들므로 제외된다.
(a, c): 가중치 1로 가장 먼저 채택되는 간선이다.
(b, c): 가중치 2로 초반에 채택되는 간선이다.

그리디로 최소 개수를 보장하는 동전 집합은 10, 50, 100, 200이다.
각 동전이 바로 아래 동전의 배수(50=10×5, 100=50×2, 200=100×2)이면, 큰 동전 하나를 작은 동전 여러 개로 바꿔도 개수가 줄지 않으므로 큰 동전부터 고르는 그리디가 최적이 된다.
10, 50, 60, 200: 100원을 그리디는 60+10×4로 5개를 쓰지만 50×2의 2개가 최적이다.
10, 40, 50, 100: 80원을 그리디는 50+10×3으로 4개를 쓰지만 40×2의 2개가 최적이다.
10, 50, 100, 130: 150원을 그리디는 130+10×2로 3개를 쓰지만 100+50의 2개가 최적이다.

압축 코드를 디코딩한 문자열은 adebcb이다.
트리에서 왼쪽 0, 오른쪽 1을 따라가면 a=00, b=01, c=100, d=101, e=11이다. 허프만 코드는 접두어 코드이므로 앞에서부터 리프에 닿을 때마다 끊어 읽는다.
00 | 101 | 11 | 01 | 100 | 01 로 나누면 a, d, e, b, c, b가 된다.
abbedcb: 둘째 문자를 01로 읽었으나 실제 둘째 묶음은 101(d)이다.
abcde: 각 문자 코드를 순서대로 이으면 00 01 100 101 11이 되어 주어진 코드와 다르다.
adebd: 다섯째 묶음 100은 d가 아니라 c이고, 마지막 01(b)이 빠졌다.

원소 P를 찾기까지 4개의 원소와 비교한다.
이진 탐색은 범위의 중간 인덱스 $\lfloor (\mathrm{low}+\mathrm{high})/2 \rfloor$의 원소와 비교하며 범위를 절반씩 줄인다. 비교 순서는 N → T → Q → P이다.
범위 0~14, 중간 7(N) < P → 범위 8~14
중간 11(T) > P → 범위 8~10
중간 9(Q) > P → 범위 8~8
중간 8(P) 일치 → 탐색 종료
2개는 N, T까지만 비교한 상태로 아직 P에 도달하지 않았다.
3개는 Q까지만 비교한 상태로 범위 8~8의 P가 남아 있다.
5개는 P를 찾은 뒤에도 비교를 계속한 값으로, 일치하는 순간 탐색은 끝난다.

원소 20은 주소 8에 저장된다.
이중 해싱은 충돌할 때마다 $h_2(k)$만큼 건너뛰며 빈 칸을 찾는다.
14 삽입: $h_1(14)=1$, $h_2(14)=1+3=4$
i=0 → 1(66 있음), i=1 → 5(18 있음), i=2 → $(1+2 \cdot 4) \bmod 13 = 9$(빈칸) → 14는 주소 9에 저장
20 삽입: $h_1(20)=7$, $h_2(20)=1+9=10$
i=0 → 7(72 있음)
i=1 → $17 \bmod 13 = 4$(69 있음)
i=2 → $27 \bmod 13 = 1$(66 있음)
i=3 → $37 \bmod 13 = 11$(50 있음)
i=4 → $47 \bmod 13 = 8$(빈칸) → 저장
주소 6은 20의 탐사 순서 7, 4, 1, 11, 8에 나타나지 않는다.
주소 9는 앞서 삽입한 14가 차지한 자리이며 20의 탐사 순서에도 없다.
주소 10은 $h_2(20)$ 값과 혼동한 것으로, 20의 탐사 순서에 나타나지 않는다.

삽입 결과는 루트 7, 왼쪽 2(자식 1과 5, 5의 자식 4·6), 오른쪽 8(오른쪽 자식 9)인 트리이다.
4는 7의 왼쪽에 들어가 루트 8의 왼쪽 높이가 오른쪽보다 2 커지고, 경로가 왼쪽→오른쪽이므로 LR 이중 회전으로 7이 루트가 되어 7(2(1, 4), 8(-, 9))이 된다.
5는 4의 오른쪽에 들어가도 균형이 유지된다. 6이 5의 오른쪽에 들어가면 노드 4에서 RR 불균형이 생겨 좌회전 한 번으로 5(4, 6)이 된다.
루트가 6인 트리: 노드 7의 오른쪽에 9, 그 왼쪽에 8이 매달려 7의 좌우 높이 차가 2가 되므로 AVL 트리가 아니다.
루트 7의 왼쪽 자식이 5인 트리: 6 삽입 때 불균형은 노드 4에서만 생기므로 2가 5 아래로 내려가는 회전은 일어나지 않는다.
루트가 4인 트리: 4를 삽입할 때 LR 회전으로 루트가 7이 되며, 이후 삽입에서 루트가 다시 바뀌지 않는다.

실행 결과는 29 26 40 22 40 74 43 88 61 60이다.
마지막 원소 a[9]=40을 피벗으로 삼아 피벗 이하인 원소를 앞쪽으로 교환하는 로무토 분할이다. 단, 반복이 range(0, n-2)이므로 j=0~7만 검사한다.
j=0: 29 ≤ 40 → i=0, 제자리
j=3: 26 → i=1, a[1]과 교환 → 29 26 60 88 40 …
j=4: 40 → i=2, a[2]와 교환 → 29 26 40 88 60 …
j=7: 22 → i=3, a[3]과 교환 → 29 26 40 22 60 74 43 88 61 40
끝으로 a[4]와 a[9] 교환 → 29 26 40 22 40 74 43 88 61 60
29 22 26 40 40 74 43 88 61 60은 교환이 일어난 순서(26 → 40 → 22)를 무시하고 앞부분을 다르게 배치한 결과이다.
29 22 40 26 40 74 43 88 61 60은 22가 26보다 앞에 있어, 26이 먼저 a[1]로 교환되는 진행과 맞지 않는다.
29 26 22 40 40 74 43 60 61 88은 22와 40의 순서가 바뀌었고, 마지막 교환으로 a[4]의 60이 맨 끝에 와야 하는데 88이 와 있다.

옳지 않은 것은 $\Theta(g(n))$를 극한값이 0인 함수의 집합으로 정의한 것이다.
$\lim_{n \to \infty} f(n)/g(n) = 0$은 f가 g보다 엄격히 느리게 증가한다는 뜻으로 little-o, 즉 $o(g(n))$의 정의이다.
$\Theta(g(n))$는 모든 $n \ge n_0$에 대하여 $c_1 g(n) \le f(n) \le c_2 g(n)$인 양의 상수 $c_1, c_2, n_0$가 존재하는 함수의 집합이다.
$O(g(n))$를 $c \cdot g(n)$이 f(n)의 상한이 되는 함수의 집합으로 정의한 것은 옳다.
$\Omega(g(n))$를 $c \cdot g(n)$이 f(n)의 하한이 되는 함수의 집합으로 정의한 것은 옳다.
$\omega(g(n))$를 극한값이 무한대인, 즉 f가 g보다 엄격히 빠르게 증가하는 함수의 집합으로 정의한 것은 옳다.

간격 3까지 처리한 배열은 6 4 2 8 13 9 18 17 21 24 26이다.
셸 정렬은 간격 h만큼 떨어진 원소끼리 부분 배열을 만들어 각각 삽입 정렬한다.
간격 5: (9, 17, 8) → (8, 9, 17), (18, 13) → (13, 18), (26, 2) → (2, 26), (21, 6) → (6, 21), (4, 24) 유지
→ 8 13 2 6 4 9 18 26 21 24 17
간격 3: 인덱스 0·3·6·9의 (8, 6, 18, 24) → (6, 8, 18, 24), 인덱스 1·4·7·10의 (13, 4, 26, 17) → (4, 13, 17, 26), 인덱스 2·5·8의 (2, 9, 21) 유지
→ 6 4 2 8 13 9 18 17 21 24 26
4 9 13 26 6 8 18 24 2 17 21은 간격 3 부분 배열의 정렬 결과와 맞지 않는다. 인덱스 0에는 해당 그룹의 최솟값 6이 와야 한다.
9 2 6 13 4 17 21 8 26 24 18은 간격 5 처리를 건너뛰고 원래 배열에 간격 3만 적용한 결과이다.
9 18 26 4 17 21 2 6 13 8 24는 간격으로 떨어진 원소가 아니라 이웃한 세 원소씩 묶어 정렬한 결과이다.

이 코드는 브루트-포스(brute-force) 알고리즘이다.
문자가 일치하면 두 포인터를 함께 전진하고, 불일치하면 pt = pt - p + 1로 이번 비교 시작 위치의 다음 칸으로 되돌아가 패턴을 처음(p = 0)부터 다시 비교한다. 모든 시작 위치를 하나씩 시도하므로 최악 $O(n_1 n_2)$이다.
라빈-카프는 패턴과 텍스트 구간의 해시값을 비교하는데, 코드에 해시 계산이 없다.
오토마타 매칭은 상태 전이표를 미리 만들어 텍스트를 되돌아가지 않고 한 번 훑는데, 코드는 pt를 뒤로 되돌린다.
보이어-무어는 패턴을 오른쪽 끝부터 비교하고 불일치 문자 정보로 크게 건너뛰는데, 코드는 왼쪽부터 비교하고 한 칸씩만 이동한다.

(가)~(라)는 차례로 1, 2, 3, 1이다.
pi[i]는 패턴 앞 i글자에서 접두사와 접미사가 일치하는 최대 길이이다(pi[0] = -1).
pi[5]: abcba → a 일치 → 1
pi[6]: abcbab → ab 일치 → 2
pi[7]: abcbabc → abc 일치 → 3
pi[8]: abcbabca → 코드에서 pn[7]=a ≠ pn[3]=b라 k = pi[3] = 0으로 돌아간 뒤 pn[7] = pn[0] = a가 일치 → 1
1, 1, 1, 1은 (나)·(다)에서 일치 길이가 ab, abc로 늘어나는 것을 반영하지 않았다.
1, 2, 3, 0은 마지막 a가 첫 글자 a와 일치하는 것을 놓쳤다.
3, 3, 3, 0은 abcba의 접두사·접미사 일치가 a 하나뿐이라 (가)부터 맞지 않는다.