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

알고리즘의 입력은 0개 이상이면 되므로, 입력이 반드시 1개 이상 존재해야 한다는 설명이 옳지 않다.
알고리즘의 조건은 입력(0개 이상), 출력(1개 이상), 명확성, 유한성, 효과성이다. 난수 생성처럼 외부 입력 없이도 결과를 내는 알고리즘이 있다.
1개 이상의 결과를 생성해야 한다는 것은 출력 조건으로 옳다.
한정된 단계 실행 후 반드시 종료해야 한다는 것은 유한성으로 옳다.
각 명령이 모호하지 않고 명확해야 한다는 것은 명확성으로 옳다.

재귀 피보나치는 호출이 지수적으로 늘어나므로 시간 복잡도가 $O(\log_2(n))$라는 설명이 옳지 않다.
fib(n)은 fib(n-1)과 fib(n-2)를 모두 다시 호출해 같은 값을 중복 계산하므로, 호출 횟수가 피보나치 수에 비례해 늘어나는 지수 시간($O(2^n)$ 상한)이 된다.
fib(4)·fib(5)·fib(6)·fib(7)을 호출할 때 fib(3)의 호출 횟수는 1, 2, 3, 5회로 피보나치 수열처럼 늘어 fib(7)에서 5회가 맞다.
제시된 점화식은 코드의 두 기저 조건과 재귀 호출을 그대로 옮긴 것으로 옳다.
반복문으로 직전 두 항만 유지하며 계산하면 $O(n)$으로 성능이 개선된다.

추상 데이터 타입은 자료와 연산의 명세일 뿐 처리 절차를 나타내지 않으므로, 추상 데이터 타입만으로 기술하는 것은 알고리즘 기술 방법이 아니다.
알고리즘은 문제를 푸는 단계적 절차이므로 자연어, 순서도, 의사 코드, 프로그래밍 언어처럼 실행 순서를 표현할 수 있는 수단으로 기술한다.
순서도는 처리 흐름을 도형으로 나타내는 기술 방법이다.
의사 코드는 특정 언어에 얽매이지 않고 절차를 표현하는 대표적 기술 방법이다.
자연어 기술도 단계가 명확하면 알고리즘 기술 방법이 된다.

DFS 방문 순서를 트리에 대입하면 ㉠은 e, ㉡은 h, ㉢은 i이다.
깊이 우선 탐색의 방문 순서는 전위 순회 순서와 같다. a의 왼쪽 자식 b 아래에서 c와 그 자식 d, 둘째 자식 e(㉠), 셋째 자식 f와 그 자식 g·h(㉡)를 차례로 방문한다.
이어서 a의 오른쪽 자식 i(㉢)와 그 서브트리 j, k, l, m을 방문한다.
e·g·c 조합: f의 두 자식 중 g가 먼저 방문되므로 ㉡ 자리는 h이고, c는 b의 첫 자식이다.
k·g·i 조합: k는 a의 오른쪽 서브트리에 속해 b의 자식 자리에 올 수 없다.
k·h·c 조합: ㉠은 b의 둘째 자식 e이고, ㉢은 오른쪽 서브트리의 루트 i이다.

빈칸에는 return n + sum(n - 1)이 들어간다.
1부터 n까지의 합은 n에 1부터 n-1까지의 합을 더한 값이므로 $S(n)=n+S(n-1)$이고, 인자가 1씩 줄어 기저 조건 n == 1에 도달한다.
예: sum(3) = 3 + sum(2) = 3 + 2 + sum(1) = 6
n에서 sum(n - 1)을 빼면 합이 아니라 차가 되어 sum(2)가 1이 되는 등 결과가 틀린다.
n에 sum(n + 1)을 더하면 인자가 커지기만 해 n == 1에 도달하지 못하고 무한 재귀에 빠진다.
n에서 sum(n + 1)을 빼는 경우도 인자가 증가해 종료되지 않는다.

힙에 데이터 하나를 삽입한 뒤 재정비하는 비용은 $O(\log_2(n))$이므로 $O(n\log_2(n))$라는 설명이 옳지 않다.
새 원소를 마지막 위치에 넣고 부모와 비교·교환하며 올라가는데, 완전 이진 트리의 높이가 $\lfloor \log_2 n \rfloor$이므로 교환은 높이만큼만 일어난다.
완전 이진 트리는 빈자리 없이 채워지므로 1차원 배열(부모 i, 자식 2i·2i+1)로 구현할 수 있다.
최대 힙은 모든 부모가 자식보다 크거나 같은 힙 성질을 만족한다.
루트 삭제 후에는 마지막 원소를 루트로 옮겨 아래로 내려가며 재정비하므로 $O(\log_2(n))$이다.

퀵 정렬은 피봇을 기준으로 원소를 좌우로 나누는 과정에서 교환(swap)을 반복하므로, 교환하지 않는다는 설명이 옳지 않다.
오히려 병합 정렬이 교환 대신 보조 배열에 원소를 복사·병합하는 방식이다.
두 정렬은 부분 배열에 자기 자신을 다시 호출하는 재귀 함수로 구현할 수 있다.
두 정렬 모두 분할 → 정복 → 결합의 분할 정복 구조다.
퀵 정렬은 피봇 값에 따라, 병합 정렬은 중간 위치에서 배열을 나눈다.

(다) 상태는 end = 8, cur = 2에서 교환이 일어난 직후다.
end = 9 회차: 6이 오른쪽으로 이동하며 2, 3, 4, 0, 5, 1과 차례로 교환되고, 9가 8, 7과 교환되어 2, 3, 4, 0, 5, 1, 6, 8, 7, 9가 된다.
end = 8 회차: cur = 0(2와 3), cur = 1(3과 4)은 교환이 없고, cur = 2에서 4 > 0이므로 교환해 2, 3, 0, 4, 5, 1, 6, 8, 7, 9, 즉 (다)가 된다.
end = 8, cur = 4는 같은 회차에서 5와 1을 교환하는 시점이라 (다)보다 더 진행된 상태다.
end = 7, cur = 2 시점에는 직전 회차에서 8과 7이 이미 교환되어 끝부분이 7, 8, 9이므로 (다)와 다르다.
end = 7, cur = 4 역시 끝부분이 7, 8, 9로 정리된 뒤라 (다)와 맞지 않는다.

제시된 코드는 삽입(insertion) 정렬이다.
i번째 원소를 cur에 두고, 앞쪽의 이미 정렬된 구간에서 cur보다 큰 원소를 한 칸씩 오른쪽으로 밀어낸 뒤 빈자리에 cur을 끼워 넣는 구조다.
쉘 정렬은 일정 간격(gap)으로 떨어진 원소끼리 삽입 정렬을 하고 간격을 줄여 가는데, 이 코드는 간격 없이 인접 원소만 비교한다.
기수 정렬은 자릿수별로 버킷에 분배하는 비교 없는 정렬이지만, 이 코드는 원소끼리 대소를 비교한다.
선택 정렬은 남은 구간의 최솟값을 찾아 교환하는 방식이라, 원소를 밀어 옮기는 이 코드와 다르다.

$\mathrm{P} \neq \mathrm{NP}$일 때 옳은 그림은 P가 NP 안에 NP-완전과 겹치지 않게 있고, NP-완전이 NP와 NP-하드의 겹친 영역에 놓인 것이다.
P의 문제는 모두 NP에 속하고, NP-완전은 NP이면서 NP-하드인 문제로 정의된다. P와 NP가 다르면 NP-완전 문제는 다항 시간에 풀 수 없으므로 P는 NP-완전·NP-하드와 겹치지 않는다.
NP 원 안에 NP-완전이 따로 있고 P가 겹친 영역에 놓인 그림: NP-완전을 NP-하드 밖에 두고 P를 NP-하드에 넣었다.
NP-하드 원 안에 NP-완전이 따로 있고 P가 겹친 영역에 놓인 그림: NP-완전을 NP 밖에 두고 P를 NP-하드에 넣었다.
NP-하드 원 안에 P가 있고 NP-완전이 겹친 영역에 놓인 그림: P를 NP 밖에 두어 P가 NP에 포함된다는 사실에 어긋난다.

설명은 동적 프로그래밍에 해당한다.
재귀 관계식으로 문제를 작은 부분 문제로 나누고, 작은 문제의 해답을 표에 저장해 두었다가 큰 문제의 해답을 구하는 상향식(bottom-up) 방법이 동적 프로그래밍의 특징이다.
브루트포스는 가능한 모든 경우를 전부 시도하는 방법으로, 부분 문제의 해답을 저장해 재사용하지 않는다.
백트래킹은 상태 공간 트리를 깊이 우선으로 탐색하다 유망하지 않으면 되돌아가는 방법이다.
분기 한정법은 한계값(bound)으로 유망하지 않은 노드를 가지치기하며 최적해를 찾는 방법이다.

이진 탐색은 탐색 구간을 절반으로 나눠 한쪽만 재귀적으로 푸는 분할 정복 알고리즘이다.
가운데 원소와 비교해 문제를 크기 절반의 부분 문제 하나로 줄이므로, 분할 정복의 가장 단순한 형태다.
분할 정복 알고리즘의 복잡도는 문제마다 다르다. 병합 정렬은 $O(n\log_2(n))$, 퀵 정렬은 최악 $O(n^2)$이므로 일괄적으로 $O(\log_2(n))$라 할 수 없다.
분할 정복은 보통 재귀로 큰 문제를 작은 문제로 나누므로, 반복문만 사용한다는 설명은 틀리다.
선택 문제는 분할 원소(피봇)를 기준으로 나누므로 부분 문제 크기가 피봇 위치에 따라 달라지며, 항상 절반씩 분할되는 것은 아니다.

전체 시간 복잡도는 $O(n^2)$이다.
이중 반복문: 안쪽 반복이 j회씩 실행되므로 $1+2+\cdots+n=\dfrac{n(n+1)}{2}$회
단일 반복문: n회
합계: $\dfrac{n(n+1)}{2}+n$이며 최고차항이 $n^2$이다.
$O(n)$은 뒤쪽 단일 반복문만 센 값으로, 이중 반복을 반영하지 못한다.
$O(n\log_2(n))$는 반복 범위가 절반씩 줄어드는 구조에서 나오며, 여기서 안쪽 반복은 j까지 선형으로 늘어난다.
$O(2^n)$은 지수적 재귀 등에서 나타나며, 다항 횟수만 실행되는 이 코드와 무관하다.

㉠은 a, ㉡은 temp * temp, ㉢은 temp * temp * a이다.
x가 1이면 $a^1=a$를 반환한다. x가 짝수면 $a^x=(a^{x/2})^2$이므로 temp를 제곱하고, 홀수면 $a^x=(a^{(x-1)/2})^2\cdot a$이므로 제곱에 a를 한 번 더 곱한다.
예: power(2, 5)는 temp = power(2, 2) = 4이고, 4 * 4 * 2 = 32이다.
㉠을 a * a, ㉡을 temp * a로 둔 조합은 x가 1일 때 $a^2$를 반환하고 짝수 지수에서도 temp를 제곱하지 않아 틀린다.
㉠을 a * a, ㉢을 a * a * temp로 둔 조합은 x가 1일 때 $a^2$를 반환하고 홀수 지수에서 temp를 제곱하지 않아 틀린다.
㉡을 temp * a, ㉢을 a * a * temp로 둔 조합은 ㉠은 맞지만 짝수·홀수 경우 모두 temp를 제곱하지 않아 거듭제곱 값이 맞지 않는다.

정렬된 배열의 이진 탐색은 $O(\log_2(n))$이다.
비교할 때마다 탐색 구간이 절반으로 줄어 $n \to n/2 \to n/4 \to \cdots \to 1$이 되므로, 최악에도 약 $\log_2 n$회 비교로 끝난다. 점화식은 $T(n)=T(n/2)+O(1)$이다.
$O(n)$은 처음부터 하나씩 확인하는 순차 탐색의 복잡도다.
$O(n\log_2(n))$은 병합 정렬·힙 정렬 같은 비교 정렬의 복잡도다.
$O(n^2)$은 삽입·선택 정렬 등의 최악 복잡도로 탐색과 무관하다.

시간 복잡도는 $\Theta(n^2)$이다.
마스터 정리 적용: $a=9,\ b=3,\ f(n)=8n$
$n^{\log_b a}=n^{\log_3 9}=n^2$
$f(n)=8n=O(n^{2-\epsilon})$ ($\epsilon=1$)이므로 첫째 경우에 해당해 $T(n)=\Theta(n^2)$이다. 초기값 T(1)=27은 상수배에만 영향을 준다.
$\Theta(1)$은 n과 무관한 상수 시간으로, 재귀 호출이 9개씩 늘어나는 이 식과 맞지 않는다.
$\Theta(\log_2(n))$은 $T(n)=T(n/2)+c$처럼 부분 문제가 하나일 때의 결과다.
$\Theta(n)$은 비재귀 항 8n만 본 것으로, 지배적인 재귀 부분 $n^2$를 놓친 값이다.

각 묶음에서 가장 빠르게 증가하는 항을 취하면 ㉠은 $O(n^2)$, ㉡은 $O(1)$, ㉢은 $O(n^3)$이다.
빅오 표기는 최고차항만 남기고 계수를 버린다. ㉡의 6,450,254는 n과 무관한 상수이고, ㉠의 최고차항은 $2n^2$, ㉢의 최고차항은 $4n^3$이다.
지수·상수·$n^k$ 조합: ㉠ 묶음에는 지수항이 없으며 ㉢의 차수는 3으로 정해진다.
제곱·로그·$n^k$ 조합: 상수인 ㉡을 로그로 잡았고 ㉢의 차수도 3으로 특정된다.
제곱·로그·세제곱 조합: ㉡은 상수이므로 가장 엄격한 표기는 로그가 아니라 상수 시간이다.

물건을 쪼갤 수 없는 0-1 배낭 문제에서 탐욕 알고리즘은 최적해를 보장하지 못한다.
무게당 가치가 큰 순으로 담는 탐욕 전략은 물건을 쪼갤 수 있는 분할 가능 배낭 문제에서만 최적이며, 0-1 배낭은 동적 프로그래밍(또는 분기 한정법)으로 최적해를 구한다.
예: 용량 50에 (무게 10, 가치 60), (20, 100), (30, 120)이면 무게당 가치 순 탐욕은 160을 얻지만 최적은 뒤의 두 물건을 담은 220이다.
탐욕 알고리즘도 무게당 가치로 정렬해야 하므로 $O(n\log_2(n))$이 들며 $O(n)$이 아니다.
무게당 가치를 기준으로 고르는 것은 탐욕 알고리즘의 방식이며, 동적 프로그래밍은 물건 수와 용량별 최대 가치 표를 채운다.
힙(우선순위 큐)으로 유망한 노드부터 탐색하는 것은 분기 한정법이며, 동적 프로그래밍은 표를 사용한다.

삽입 정렬은 최선 $\Omega(n)$, 최악 $O(n^2)$로 옳게 짝지어져 있다.
이미 정렬된 입력이면 원소마다 한 번만 비교해 선형 시간에 끝나고, 역순 입력이면 매번 앞 원소를 모두 밀어야 해 이차 시간이 된다.
선택 정렬은 입력 상태와 관계없이 남은 구간 전체에서 최솟값을 찾으므로 최선도 $\Omega(n^2)$이다.
힙 정렬은 최악에도 $O(n\log_2(n))$을 보장하므로 최악 $O(n^2)$가 틀리다.
퀵 정렬은 피봇이 계속 한쪽 끝으로 치우치면 최악 $O(n^2)$가 되므로 최악 $O(n\log_2(n))$가 틀리다.

크루스칼 알고리즘에서 다섯 번째로 MST에 포함되는 간선은 (c, e)이다.
가중치 오름차순으로 (a, b) 2, (c, f) 3, (g, f) 4, (b, g) 5가 사이클 없이 채택되어 a, b, g, f, c가 한 집합이 된다.
가중치 6인 (b, c)는 같은 집합의 두 노드를 이어 사이클을 만들므로 버리고, 같은 가중치의 (c, e)가 다섯 번째로 채택된다.
(b, c): 가중치는 같지만 사이클을 만들어 제외된다.
(b, g): 네 번째로 채택된 간선이다.
(d, e): 가중치 8로 (c, e) 다음, 여섯 번째로 채택된다.

갱신 횟수가 옳은 것은 e 3회, h 1회이다.
a(0) 확정: b=2, e=11, d=13
b(2) 확정: c=10, e=9, f=5
f(5) 확정: c=6, i=6
c(6)·i(6) 확정: h=7, e=8
h(7) 확정: d=11, g=8
e(8)·g(8) 확정: d=10
∞에서 처음 값이 들어가는 것도 갱신으로 세면 e는 ∞→11→9→8로 3회, h는 ∞→7로 1회다.
b·c 조합: c는 ∞→10→6으로 2회 갱신된다.
f·g 조합: f는 ∞→5로 1회만 갱신된다.
d·i 조합: d는 ∞→13→11→10으로 3회, i는 ∞→6으로 1회다.

㉠은 from, to, temp, ㉡은 temp, from, to이다.
매개변수 순서는 (출발, 경유, 도착)이다. 먼저 위쪽 n-1개를 to를 경유해 from에서 temp로 옮기므로 hanoi(n – 1, from, to, temp)이다.
가장 큰 원판을 from에서 to로 옮긴 뒤, temp에 있는 n-1개를 from을 경유해 to로 옮기므로 hanoi(n – 1, temp, from, to)이다.
㉡을 from, temp, to로 둔 조합은 원판을 옮겨 둔 temp가 아니라 이미 비운 from에서 다시 출발하므로 n-1개가 to로 가지 않는다.
㉠을 temp, from, to, ㉡을 from, to, temp로 둔 조합은 첫 호출이 원판이 없는 temp에서 출발하게 되어 위쪽 원판을 치울 수 없다.
㉠을 temp, from, to, ㉡을 from, temp, to로 둔 조합은 두 재귀 호출의 출발 기둥이 모두 잘못되었다.

해시 값이 같아도 문자열이 실제로 같다는 보장이 없으므로(해시 충돌), 해시 값이 일치하면 바로 종료한다는 설명이 옳지 않다.
해시 값이 일치하면 해당 위치의 문자를 하나씩 직접 비교해 실제 일치인지 확인하고, 모든 출현 위치를 찾을 때까지 다음 위치로 계속 진행한다.
길이 m인 창을 한 칸씩 옮기므로 대상 문자열의 해시 값은 최대 $n-m+1$개, 패턴의 해시 값은 1개다.
문자열을 다항식으로 보고 해시를 계산할 때 호너의 방법을 쓰면 곱셈 횟수를 줄일 수 있다.
해시 값이 너무 커지면 나머지 연산으로 값을 일정 범위로 유지한다.

KMP는 전처리를 포함해 $O(m+n)$이므로 $O(mn)$이라는 설명이 옳지 않다.
패턴의 실패 함수(접두사·접미사 일치 정보)를 $O(m)$에 미리 만들고, 대상 문자열은 비교 위치를 되돌리지 않고 $O(n)$에 한 번 훑는다. $O(mn)$은 단순 매칭의 최악 복잡도다.
대상과 패턴의 문자를 하나씩 비교하며 매칭 여부를 판단하는 것은 KMP의 기본 동작이다.
매칭 실패 시 미리 만든 실패 함수 값을 이용해 패턴의 비교 재시작 위치를 정한다.
이미 일치한 접두사 정보를 재활용해 불필요한 비교를 건너뛰므로 비교 횟수가 줄어든다.

허프만 트리에서 ㉠은 i, ㉡은 e, ㉢은 k, ㉣은 b이다.
빈도가 가장 작은 두 노드를 반복해 합치면 g(1)+d(2)=3, 3+b(4)=7, k(6)+7=13, e(8)+13=21, 21+i(25)=46, 46+a(50)=96 순이다.
따라서 루트 오른쪽 문자 노드가 a, 그 아래로 ㉠ i, ㉡ e, ㉢ k가 차례로 붙고, 내부 노드 7의 오른쪽 ㉣이 b, 맨 아래 두 문자 노드가 g와 d이다.
a·i·b·k 조합: a는 루트 바로 아래 문자 노드이고, b(4)는 k(6)보다 먼저 합쳐져 더 깊이 놓인다.
a·i·k·b 조합: a는 루트 바로 아래 문자 노드이므로 ㉠ 자리는 i, ㉡ 자리는 e이다.
i·e·d·g 조합: 가장 드문 g와 d는 맨 아래 두 문자 노드로 묶이고, ㉢·㉣은 k와 b이다.