간선의 총 개수는 18개다.
노드가 개인 트리는 간선이 개이므로, 트리 개로 된 숲의 간선 수는 노드 수 − 트리 수가 된다.
- 간선 19개: 트리가 2개인 숲일 때의 값이다.
- 간선 20개: 전체가 하나의 트리(연결 그래프)일 때의 값이다.
- 간선 21개: 간선 수가 노드 수와 같으면 반드시 사이클이 생기므로 숲이 될 수 없다.
최악의 경우 필요한 최소 비교 횟수는 , 즉 9회다.
토너먼트 방식으로 최댓값을 찾는 데 회가 들고, 두 번째로 큰 값은 반드시 최댓값에게 직접 진 값 가운데 있다.
최댓값은 번 비교에 참여했으므로, 그 3개 중 최댓값을 고르는 데 2회가 더 든다.
- 8회: 최댓값을 찾는 7회에 1회만 더한 값으로, 후보 3개를 가리기에 부족하다.
- 13회: 최댓값을 찾은 뒤 나머지 7개를 순차 비교한 회로, 최소 횟수가 아니다.
점근적 시간 복잡도는 이다.
재귀 트리로 펼치면 각 레벨의 비용 합이 으로 최대 이다.
가장 짧은 가지의 깊이는 , 가장 긴 가지의 깊이는 으로 모두 이므로, 전체 비용은 레벨당 × 깊이 이 된다.
- : 비용 인 레벨이 로그 개만큼 쌓이므로 선형보다 크다.
- : 레벨당 비용이 을 넘지 않고 깊이도 로그이므로 지나치게 크다.
- : 레벨당 비용 이 로그 깊이만큼만 쌓이므로 제곱에 이르지 않는다.
전위 순회: A − B − D − E − C − F
중위 순회: D − B − E − A − C − F
후위 순회 결과는 D − E − B − F − C − A이다.
전위 순회의 첫 원소 A가 루트이고, 중위 순회에서 A의 왼쪽 D, B, E가 왼쪽 서브트리, 오른쪽 C, F가 오른쪽 서브트리다.
왼쪽은 전위가 B, D, E이므로 B가 루트이고 D가 왼쪽, E가 오른쪽 자식이다. 오른쪽은 전위·중위가 모두 C, F이므로 C가 루트이고 F는 C의 오른쪽 자식이다.
- D − B − E − C − F − A: 왼쪽 서브트리를 중위 순서로 적은 것으로, 후위에서는 B가 D, E 뒤에 와야 한다.
- D − E − B − C − F − A: 오른쪽 서브트리의 루트 C가 자식 F보다 먼저 나와 후위 순서가 아니다.
- E − D − B − F − C − A: D가 왼쪽 자식이므로 E보다 먼저 방문해야 한다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| T | a | b | a | b | a | d | a | a | b | c | d |
| = | = | = | = | = | ≠ | ||||||
| P | a | b | a | b | a | c |
다음에 비교할 패턴 인덱스는 3이다.
불일치 직전까지 일치한 P[0..4] = ababa에서 가장 긴 접두사이자 접미사는 aba로, 길이가 3이다.
따라서 T의 인덱스 5는 그대로 두고 패턴을 밀어 P[3]부터 비교를 이어 간다.
- 인덱스 0: 실패 함수를 쓰지 않고 패턴 처음부터 다시 비교하는 단순 매칭의 동작이다.
- 인덱스 1: 길이 1인 a만 고려한 값으로, 더 긴 aba를 놓친다.
- 인덱스 2: ab는 ababa의 접미사가 아니므로 경계가 될 수 없다.

노드 25를 노드 22로 대체할 때 노드 15의 포인터를 NULL로 바꾸는 설명이 옳지 않다.
자식이 둘인 노드 25는 왼쪽 서브트리 최댓값 22(또는 오른쪽 서브트리 최솟값 35)로 키를 대체한 뒤, 원래 22가 있던 자리를 지워야 한다. 즉 노드 20의 오른쪽 포인터를 NULL로 바꿔야 하며, 15에서 25를 가리키는 포인터를 NULL로 하면 20·22·35까지 트리에서 떨어져 나간다.
- 루트 15 삭제: 오른쪽 서브트리 최솟값 20을 찾아 대체하는 과정은 한쪽 경로만 따라 내려가므로 수행시간이 트리 높이에 비례한다(옳음).
- 노드 12 삭제: 자식이 5 하나뿐이므로 부모 15의 왼쪽 포인터가 5를 가리키게 하면 된다(옳음).
- 노드 5 삭제: 단말 노드이므로 부모 12의 왼쪽 포인터를 NULL로 바꾸면 된다(옳음).
(a) 입력 초기 배열: 3, 2, 1, 6, 5, 4
(b) 정렬 중간 배열: 1, 2, 3, 6, 5, 4
ㄱ. 삽입 정렬(insertion sort)
ㄴ. 선택 정렬(selection sort)
ㄷ. 버블 정렬(bubble sort)
(b)가 나타날 수 있는 것은 삽입 정렬과 선택 정렬이다.
삽입 정렬은 2를 삽입하면 2, 3, 1, 6, 5, 4가 되고, 이어서 1을 삽입하면 1, 2, 3, 6, 5, 4가 된다.
선택 정렬은 첫 단계에서 최솟값 1을 맨 앞의 3과 교환하므로 곧바로 1, 2, 3, 6, 5, 4가 된다.
- 버블 정렬: 첫 순환 후 2, 1, 3, 5, 4, 6, 둘째 순환 후 1, 2, 3, 4, 5, 6이 되어 (b)가 나타나지 않는다.
힙 정렬은 제자리 정렬이지만 안정 정렬은 아니다.
힙 정렬은 배열 안에서 루트를 마지막 원소와 교환하고 힙을 재구성하므로 추가 배열이 필요 없지만, 멀리 떨어진 원소끼리 교환하기 때문에 같은 키의 상대 순서가 바뀔 수 있다.
- 최소 힙의 최댓값: 리프 어디에나 있을 수 있어 리프 전체(약 절반의 원소)를 살펴야 하므로 이 든다.
- 삽입식 힙 생성: 이미 힙 순서로 들어오는 입력이면 삽입마다 상향 이동이 없어 에 끝나므로 입력 순서와 무관하지 않다.
- 힙 정렬의 시간: 비교 기반 정렬이라 하한을 넘을 수 없으며 이 든다.
A→B A→C B→E C→E D→E
가능한 위상 정렬은 8가지다.
E는 B, C, D 모두의 뒤에 와야 하고 A는 B, C보다 앞서야 하므로, E는 항상 마지막이다.
A, B, C는 A 다음에 B, C가 어느 순서로든 올 수 있어 2가지이고, 제약이 없는 D를 네 자리 중 하나에 끼워 넣으면 된다.
- 4가지: B와 C의 순서를 하나로 고정하고 센 값이다.
옳지 않은 설명은 라운드 K에서 정점 1부터 정점 K까지의 최단 경로를 구한다는 것이다.
벨만-포드의 각 라운드는 모든 간선을 한 번씩 완화하며, K번째 라운드가 끝나면 간선을 K개 이하로 쓰는 최단 경로가 모든 정점에 대해 확정된다. 정점 번호와는 관계가 없다.
- 음의 사이클 판별: N−1 라운드 뒤 한 번 더 완화해 값이 줄어드는 정점이 있으면 시작점에서 도달 가능한 음의 사이클이 있다.
- 시간 복잡도: N−1 라운드마다 간선 M개를 완화하므로 O(NM)이다.
- 거리 추정치: 추정치는 실제로 존재하는 경로의 길이로만 갱신되므로 항상 실제 최단 거리 이상이다.
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | 4 | 1 | 10 | 12 |
| 2 | ∞ | 0 | -3 | ∞ | 8 |
| 3 | 5 | 9 | 0 | 2 | 17 |
| 4 | ∞ | ∞ | ∞ | 0 | 3 |
| 5 | ∞ | ∞ | -1 | ∞ | 0 |

의 2행은 (2, 0, -3, -1, 8)이다.
정점 3을 중간 정점으로 새로 허용하므로 이고, , 의 3행은 (5, 9, 0, 2, 17)이다.
:
:
:
:
- 1열과 4열을 ∞로 둔 행: 2→3→1, 2→3→4 경로가 생겨 각각 2, -1로 갱신되어야 한다.
- 5열을 2로 둔 행: 2→3→5는 14로 기존 8보다 크므로 5열은 8 그대로이다(2는 정점 4를 거치는 다음 단계 값).

마지막으로 최단 경로가 확정되는 정점은 C이다.
A에서 시작해 거리가 가장 작은 정점부터 확정하면 F(3), G(4), J(4), E(5), I(6), B(7), D(7), H(7), C(11) 순이다. G와 J, B·D·H처럼 거리가 같으면 알파벳 순으로 방문한다.
C까지의 최단 거리는 A→B→C(7+4)와 A→G→E→C(4+1+6)가 모두 11로, 나머지 정점의 최단 거리(모두 7 이하)보다 크다.
- D: A→G→E→D(4+1+2)로 거리 7에 확정되어 C보다 먼저 처리된다.
- H: A→G→H(4+3)로 거리 7이며, 같은 거리의 B·D 다음에 확정된다.
- I: A→G→E→I(4+1+1)로 거리 6에 일찍 확정된다.
| 입력키 | A | B | C | D |
|---|---|---|---|---|
| 검색확률 | 0.3 | 0.4 | 0.1 | 0.2 |




최적 이진 검색 트리는 루트 B, 왼쪽 자식 A, 오른쪽 자식 D, D의 왼쪽 자식 C인 트리이다.
평균 비교 횟수는 각 키의 (깊이×검색확률) 합이며, 이 트리는 로 가능한 트리 중 최소이다. 확률이 큰 B·A를 위에, 가장 작은 C를 가장 아래에 둔 결과이다.
- 루트 C, B·D가 자식이고 A가 B 아래인 트리:
- 루트 B, A·C가 자식이고 D가 C 아래인 트리: 로, 확률이 더 큰 D가 더 깊어 손해이다.
- 루트 C, A·D가 자식이고 B가 A 아래인 트리: 으로 확률이 가장 큰 B가 가장 깊다.
행렬
(예: )
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 5 | 3 | 2 | 1 |
| 2 | 1 | 9 | 1 | 2 |
| 3 | 4 | 2 | 8 | 1 |
| 4 | 1 | 1 | 3 | 7 |
옳은 점화식은 이다.
지역 (i, j)에는 왼쪽 (i, j−1)이나 위쪽 (i−1, j)에서만 올 수 있으므로, 두 지역까지의 누적 최대 점수 중 큰 쪽에 현재 지역의 점수를 더한다.
0행·0열을 0으로 두면 첫 행·첫 열도 같은 식으로 처리된다.
- M의 이웃 값 중 큰 쪽을 더하는 식: 바로 앞 지역 하나의 점수만 보아 출발점부터 누적된 합을 반영하지 못한다.
- M의 이웃 값 중 작은 쪽을 더하는 식: 누적 합을 쓰지 않을 뿐 아니라 작은 쪽을 고른다.
- D의 이웃 값 중 작은 쪽을 더하는 식: 누적 합은 쓰지만 최소 점수 경로를 구하게 된다.
(조건1) 좌표 체계는 체스판의 가장 왼쪽 위 칸을 (1행, 1열)로 정의한다. 행 번호는 위쪽에서 아래쪽으로 1부터 4까지, 열 번호는 왼쪽에서 오른쪽으로 1부터 4까지 순서대로 부여된다.
(조건2) 탐색 순서는 1행부터 4행까지 행 번호가 증가하는 순서대로 퀸을 배치한다.
(조건3) 후보 시도는 각 행 내에서는 1열부터 4열까지 열 번호가 작은 칸부터 순서대로 퀸 배치를 시도한다.
(조건4) 퀸은 가로, 세로, 대각선 8방향에 대하여 자기 자신이 위치한 칸을 제외한 모든 칸을 공격할 수 있다. 예를 들어, (1행, 1열)에 위치한 퀸은 (1행, 1열)을 제외하고 1행 전체, 1열 전체, (2행, 2열), (3행, 3열), (4행, 4열)을 공격할 수 있다.
(조건5) 백트래킹 규칙은 어떤 칸에 퀸을 놓았을 때 이미 배치된 다른 퀸에게 공격받는 위치라면 같은 행의 다음 열을 시도한다. 만약 특정 행에서 4개의 열을 모두 시도했음에도 퀸을 놓을 수 없다면, 직전 행으로 되돌아가(backtrack) 해당 행에 배치된 퀸의 위치를 다음 열부터 다시 탐색한다.
(조건6) 해는 1행, 2행, 3행, 4행에 놓인 퀸의 열 번호를 순서대로 나열하여 표기한다.
가장 먼저 찾는 해는 (2, 4, 1, 3)이다.
1행을 1열에 두면 2행 3열 뒤 3행에 놓을 곳이 없고, 2행을 4열로 옮겨도 3행 2열 뒤 4행에 놓을 곳이 없어 1행 1열로는 해가 없다.
1행을 2열로 옮기면 2행 4열, 3행 1열, 4행 3열이 차례로 놓여 해가 완성된다.
- (1, 2, 3, 4): 모든 퀸이 한 대각선 위에 있어 서로 공격한다.
- (2, 4, 3, 1): 2행 4열과 3행 3열이 대각선으로 맞닿는다.
- (3, 1, 4, 2): 올바른 해이지만 1행 3열은 1행 2열보다 나중에 시도되므로 그다음에 찾게 된다.
select(arr, p, r, k)
if p == r
return arr[p]
q←partition(arr, p, r)
i←q - p + 1
if k == i
return arr[q]
else if k < i
return select(arr, p, q-1, (가) )
else
return select(arr, q+1, r, (나) )(가)에는 k, (나)에는 k − i가 들어간다.
i는 피벗이 구간 [p, r]에서 몇 번째로 작은지를 나타내며, 왼쪽 구간 [p, q−1]에는 피벗보다 작은 원소 i−1개가 있다.
k < i이면 찾는 원소가 왼쪽 구간에 있고 순위도 그대로 k번째다. k > i이면 왼쪽 원소와 피벗을 합한 i개를 건너뛰므로 오른쪽 구간에서는 k − i번째가 된다.
- (나)에 k: 오른쪽 구간에서는 앞선 i개가 빠졌으므로 순위를 그대로 쓰면 다른 원소를 찾는다.
- (가)에 k − i: 왼쪽 구간은 시작점이 같아 순위가 줄어들지 않는다.
최소 신장 트리는 그대로 유지되지만 최단 경로는 달라질 수 있다.
신장 트리는 항상 간선이 V−1개이므로 모든 신장 트리의 가중치가 똑같이 (V−1)c만큼 늘어 순위가 바뀌지 않는다.
반면 경로는 간선 수가 제각각이라 간선 k개짜리 경로는 kc만큼 늘어난다. 예컨대 A–B 직접 간선이 3이고 A–C, C–B가 각 1이면 원래는 우회 경로(2)가 최단이지만, c=2를 더하면 직접 간선은 5, 우회 경로는 6이 되어 최단 경로가 직접 간선으로 바뀐다.
- 둘 다 유지된다: 간선 수가 많은 경로가 더 크게 불리해지므로 최단 경로는 유지되지 않을 수 있다.
- 최소 신장 트리만 달라진다: 모든 신장 트리가 같은 양만큼 늘어나므로 최소 신장 트리는 바뀌지 않는다.
- 둘 다 달라질 수 있다: 최단 경로는 맞지만 최소 신장 트리는 바뀌지 않는다.
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | |
| 2 | 2 | 2 | ||
| 3 | 3 | |||
| 4 |
PRINT(s, i, j)
if i == j
print “A”i
else print “(”
PRINT(s, i, s[i, j])
PRINT(s, s[i, j]+1, j)
print “)”출력되는 순서는 이다.
PRINT(s, 1, 4)는 이므로 과 로 나눈다.
PRINT(s, 2, 4)는 이므로 와 로 나누고, 으로 과 가 분리된다. 결국 매번 왼쪽 첫 행렬을 떼어내는 괄호가 된다.
- : , 일 때의 결과다.
- : , 일 때의 결과다.
- : 일 때의 결과다.
[최대 구간합 문제]
Input: 크기가 n인 정수 배열 A (시작 인덱스는 0)
Output: 배열 A의 부분 배열 구간합 중 최댓값
예시) 크기가 3인 정수 배열
| -1 | 2 | -3 |
* 부분 배열 A[i..j]( 0≤i≤j<n) 구간합: 연속한 부분 배열에 포함된 모든 원소의 합, 즉 A[i]+A[i+1]+…+A[j]를 의미한다.
* 재귀 전략: 배열 A를 전반부 A[0..m−1]과 후반부 A[m..n−1]로 나누어 해결한다. (m = ) (단, n=1이면, A[0]을 반환한다.)
올바르면서 계산량이 가장 적은 방법은 경계를 가로지르는 최대합을 c+d로 구하는 분할 정복이다.
최대 구간은 전반부 안, 후반부 안, 또는 경계를 가로지르는 경우 중 하나다. 가로지르는 구간은 A[m−1]에서 끝나는 왼쪽 부분과 A[m]에서 시작하는 오른쪽 부분의 합이므로, 각각을 선형 시간에 최대화해 더하면 된다.
점화식이 이 되어 이다.
- max(a, b): 경계를 가로지르는 구간을 고려하지 않아 틀린 값이 나올 수 있다.
- max(a, b, a+b): a와 b의 구간이 붙어 있지 않을 수 있어 a+b는 실제 구간합이 아니다.
- 가로지르는 모든 부분 배열을 계산: 값은 올바르지만 단계마다 이 들어 계산량이 크다.
옳지 않은 설명은 A가 NP-하드 문제 B로 환원되면 A가 NP-하드라는 것이다.
환원 방향이 반대다. 알려진 NP-하드 문제 B를 A로 다항 시간에 환원할 수 있어야 A가 B만큼 어렵다고 할 수 있으며, A를 B로 환원하는 것은 A가 B보다 어렵지 않다는 뜻일 뿐이다.
- 최소 신장 트리: 크루스칼·프림 알고리즘으로 다항 시간에 풀리는 P 문제이고, P는 NP에 포함되므로 NP에 속한다.
- NP-완비 문제의 다항 시간 해법: 모든 NP 문제가 그 문제로 다항 시간 환원되므로 P=NP가 된다.
- 해밀토니안 사이클: 주어진 정점 순서가 해밀토니안 사이클인지 다항 시간에 검증할 수 있으므로 NP에 속한다.