



최초의 힙은 루트 19 아래 왼쪽에 13(자식 7·1), 오른쪽에 15가 오는 최대 힙이다.
7, 1, 15, 13, 19를 완전이진트리로 배치한 뒤 마지막 비단말 노드부터 위로 heapify한다. 1은 자식 13·19 중 큰 19와 교환되고, 루트 7은 19와 교환된 뒤 다시 자식 13과 교환되어 배열 [19, 13, 15, 7, 1]이 된다. 이후 최댓값부터 차례로 꺼내면 내림차순으로 정렬된다.
- 루트가 1인 트리는 작은 값이 위로 오는 최소 힙 형태라 이 정렬의 최초 힙이 아니다.
- 루트 13 아래 왼쪽 7(자식 1), 오른쪽 15(자식 19)인 트리는 이진 탐색 트리 형태로, 부모가 자식보다 작은 곳이 있어 힙이 아니다.
- 루트 7 아래 왼쪽 1, 오른쪽 15(자식 13·19)인 트리도 이진 탐색 트리 형태이며 완전이진트리 조건과 힙 조건을 모두 어긴다.
(단, False는 from에서 to까지의 간선이 없고, True는 from에서 to까지의 간선이 있음을 의미한다)
| to from | a | b | c | d |
|---|---|---|---|---|
| a | False | False | True | False |
| b | True | False | False | False |
| c | False | False | False | True |
| d | True | False | True | False |
이 인접행렬이 나타내는 그래프는 간선 집합이 E = {<b,a>, <a,c>, <d,c>, <d,a>, <c,d>}인 방향 그래프이다.
True인 칸 (from, to)마다 간선이 하나씩 생긴다. True 칸은 a→c, b→a, c→d, d→a, d→c의 5개뿐이다.
- <d,b>와 자기 루프 <b,b>를 포함한 집합: 두 칸 모두 False이고, d→a와 d→c가 빠져 있다.
- <a,b>를 포함한 집합: a행 b열이 False이므로 간선이 아니며, d→a도 빠져 있다.
- <d,b>와 <a,d>를 포함한 집합: 두 칸 모두 False이고, c→d와 d→c가 빠져 있다.

Kruskal 알고리즘에서 네 번째로 건설할 구간은 인천 ↔ 목포이다.
Kruskal은 간선을 가중치 오름차순으로 정렬해 사이클을 만들지 않는 가장 가벼운 간선부터 고른다. 순서는 포항–부산 3, 서울–인천 4, 목포–진주 4, 인천–목포 7, 인천–진주 8 … 이다.
앞의 세 간선을 고른 뒤 인천–목포(가중치 7)는 서울·인천 묶음과 목포·진주 묶음을 잇는 간선이라 사이클이 생기지 않으므로 네 번째로 채택된다.
- 포항 ↔ 부산은 가중치 3으로 가장 가벼워 첫 번째로 선택된다.
- 서울 ↔ 인천은 가중치 4로 목포–진주와 함께 두 번째·세 번째로 선택된다.
- 진주 ↔ 부산은 가중치 14로 가장 무거워, 그 차례가 오기 전에 진주와 부산이 이미 같은 트리로 이어져 사이클이 생기므로 신장 트리에 포함되지 않는다.
선형 조사법으로 넣으면 충돌은 모두 4회 일어난다.
70, 17, 26, 69, 72, 53, 31은 각각 인덱스 [0], [7], [6], [9], [2], [3], [1]에 충돌 없이 들어간다.
27은 [7]에서 1회 충돌 후 [8]에, 23은 [3]에서 1회 충돌 후 [4]에 들어간다. 13은 [3]과 [4]에서 2회 충돌한 뒤 [5]에 들어간다.
합계: 1 + 1 + 2 = 4





루트 52를 삭제하면 오른쪽 서브트리의 최솟값인 54(중위 후속자)가 루트 자리로 올라간 트리가 된다.
자식이 둘인 노드를 삭제할 때는 오른쪽 서브트리의 가장 왼쪽 노드로 대체한다. 84 → 63 → 54로 내려가 54가 후속자가 되고, 54의 오른쪽 자식 58은 54가 있던 자리인 63의 왼쪽 자식으로 붙는다.
- 61을 루트로 한 트리는 후속자도 선행자(47)도 아닌 노드를 올리고 전체를 재배치한 형태라 삭제 연산의 결과가 아니다.
- 58을 루트로 한 트리도 후속자가 아닌 노드를 올리고 서브트리를 재구성해 삭제 연산의 결과와 다르다.
- 84를 루트로 한 트리는 오른쪽 서브트리에 84보다 작은 63·54 등이 있어 이진 탐색 트리 조건을 어긴다.
삭제 후 재정렬된 힙의 마지막 원소는 17이다.
9개를 차례로 삽입하며 부모보다 크면 위로 올리면 힙 배열은 [31, 22, 29, 21, 20, 24, 27, 17, 18]이 된다.
루트 31을 삭제하고 마지막 원소 18을 루트로 옮긴 뒤 아래로 내리면 29, 27과 차례로 자리를 바꿔 [29, 22, 27, 21, 20, 24, 18, 17]이 된다. 따라서 마지막 자리는 17이다.
단계1) 피봇값 : ( ㉠ )
- 왼쪽으로부터 비교 : ( ㉡ )에서 비교 멈춤
- 오른쪽으로부터 비교 : ( ㉢ )에서 비교 멈춤
- ( ㉣ )과(와) ( ㉤ )의 저장 위치 교환
정렬 방법 ㉠ ㉡ ㉢ ㉣ ㉤
피봇을 쓰는 정렬은 퀵 정렬이고, 첫 원소 60을 피봇으로 잡으면 92와 42의 위치를 교환한다.
왼쪽부터는 피봇보다 큰 값을 찾아 50, 13을 지나 92에서 멈추고, 오른쪽부터는 피봇보다 작은 값을 찾아 바로 42에서 멈춘다. 이어 두 값의 저장 위치를 바꾼다.
- 쉘 정렬과 짝지은 나열: 쉘 정렬은 간격을 줄여 가며 삽입 정렬을 반복하는 방식으로 피봇을 쓰지 않는다.
- 피봇을 52로 둔 퀵 정렬 나열: 분할 구간의 첫 원소를 피봇으로 삼는 기본 방식과 맞지 않는다.
| to from | A | B | C | D | E |
|---|---|---|---|---|---|
| A | 0 | 2 | 5 | ∞ | 3 |
| B | ∞ | 0 | ∞ | 4 | 10 |
| C | ∞ | ∞ | 0 | 6 | 2 |
| D | ∞ | ∞ | ∞ | 0 | ∞ |
| E | ∞ | ∞ | 1 | 2 | 0 |
A에서 나머지 정점까지의 최단경로 합은 14이다.
다익스트라 알고리즘으로 B = 2, E = 3이 먼저 확정된다. E를 거치면 C는 3 + 1 = 4로 직접 가는 5보다 짧고, D는 3 + 2 = 5로 B를 거치는 2 + 4 = 6보다 짧다.
합계: 2 + 4 + 5 + 3 = 14
- A→C를 직접 간선 5로 두면 합이 15가 되어 E를 경유하는 더 짧은 경로를 놓친다.
int numGreaterThan(T, k)
{
if (T == NULL) return 0;
else if (T.key <= k) return numGreaterThan(T.right, k);
else return _________________________________;
}
빈칸에는 T.right.numDesc + numGreaterThan(T.left, k) + 1이 들어간다.
T.key > k이면 오른쪽 부분 트리의 키는 모두 T.key보다 커서 그 개수 numDesc가 전부 포함되고, T 자신도 1개로 더해진다. 왼쪽 부분 트리는 k보다 큰 키가 일부만 있을 수 있어 재귀로 센다.
- 오른쪽 부분 트리 개수에서 1만 빼는 식: 루트와 왼쪽 부분 트리를 모두 빠뜨린다.
- 왼쪽 재귀 결과에 1만 더하는 식: 오른쪽 부분 트리 전체를 빠뜨린다.
- 오른쪽 개수와 왼쪽 재귀 결과에서 1을 빼는 식: 루트 T를 더해야 할 자리에서 오히려 1을 뺀다.
| A | F | E | C | B | D |




A, F, E, C, B, D를 차례로 넣으면 최종 AVL 트리는 루트 C, 왼쪽 B(자식 A), 오른쪽 E(자식 D·F)가 된다.
A, F, E 삽입 시 A에서 RL 불균형이 생겨 E가 루트(A, F)가 된다. C를 A의 오른쪽에 넣고 B를 넣으면 A에서 다시 RL 불균형이 생겨 B가 A·C의 부모가 된다.
마지막 D가 C의 오른쪽에 붙으면 루트 E의 왼쪽 높이가 3, 오른쪽이 1이 되어 LR 회전으로 C가 루트로 올라가고, D는 E의 왼쪽 자식이 된다.
- 루트 D, 왼쪽 B(A, C), 오른쪽 F(자식 E)인 트리는 균형은 맞지만 삽입·회전 과정에서 D가 루트로 오지 않는다.
- 루트 C, 왼쪽 A(오른쪽 자식 B)인 트리는 LR 회전 뒤에도 B가 왼쪽 자식 A를 유지한다는 점과 맞지 않는다.
- 루트 D, 오른쪽 E 아래 F만 있는 트리도 D가 루트가 되는 회전이 일어나지 않으므로 결과가 아니다.
시간 복잡도가 가장 큰 것은 이다.
빅오 표기에서는 상수 계수와 낮은 차수 항을 버리고 최고차 항만 남겨 비교한다.
- : 으로 가장 작다.
- : 이다.
- : 으로, 여기에 이 곱해진 것보다 작다.
A(2, 3, 2)는 B(14)에 저장된다.
각 차원의 크기는 5, 3, 3이고, 행우선 저장에서는 마지막 첨자가 가장 빨리 변한다.
오프셋:
B는 1부터 시작하므로 인덱스는 1 + 13 = 14이다.
0이 아닌 원소만 3원소쌍 배열로 저장하는 방식이 저장 관점에서 효율적이다.
0이 아닌 원소는 개이므로, 3원소쌍으로 저장하면 약 칸으로 전체 칸보다 훨씬 적다.
- 2차원 배열에 전 원소를 저장하는 설명: 90%를 차지하는 0까지 모두 저장해 공간 낭비가 크다.
- 0이 아닌 원소에 1,000개 공간이 필요하다는 설명: 0이 아닌 원소는 100,000개이므로 맞지 않다.
- 연결 리스트가 전치에 더 효율적이라는 설명: 3원소쌍 배열도 열별 개수로 위치를 정하는 빠른 전치로 효율적으로 처리할 수 있어 연결 리스트가 낫다고 단정할 수 없다.
S :
| T | |||||
|---|---|---|---|---|---|
| 3 | 6 |
| R | F | ||||
|---|---|---|---|---|---|
| 2 | 7 | 4 |
다음 문장들이 순서대로 실행된 후 S와 Q의 상태는?
Q.remove(); S.push(Q.front());
| 3 | 6 |
| 2 | 7 | 4 |
| 3 | 6 | 7 |
| 2 | 4 |
| 3 | 6 | 7 | 4 |
| 2 | 7 | 4 |
| 3 | 6 | 7 | 4 |
| 2 | 4 |
실행 후 S = [3, 6, 7, 4]가 되고, Q에서는 7이 삭제되어 2와 4만 남는다.
Q의 front 값은 7이다. S.push(Q.front())로 7을 넣고, S.push(S.top())으로 7을 하나 더 넣었다가 S.pop()으로 꺼내 S = [3, 6, 7]이 된다.
Q.remove()로 7이 삭제되어 front가 4로 옮겨지고, S.push(Q.front())로 4가 S에 들어간다.
- S와 Q가 처음과 같은 상태: 삽입·삭제가 전혀 반영되지 않았다.
- S가 [3, 6, 7]에서 멈춘 상태: 마지막 push로 들어간 4가 빠졌다.
- Q에 7이 그대로 남은 상태: remove로 front의 7이 삭제된 것이 반영되지 않았다.




포인터 하나로 큐를 구현할 때 가장 효율적인 것은 마지막 노드를 가리키는 원형리스트이다.
원형리스트에서 마지막 노드 D를 가리키면 그 다음 노드가 곧 첫 노드 A이다. 삽입은 ptr 뒤에 새 노드를 붙이고 ptr을 옮기면 되고, 삭제는 ptr의 다음 노드를 떼어내면 되므로 두 연산 모두 상수 시간에 끝난다.
- 첫 노드를 가리키는 원형리스트는 삽입 위치인 마지막 노드를 찾으려면 리스트를 끝까지 순회해야 한다.
- 첫 노드(가장 최근 입력 D)를 가리키는 역원형리스트는 가장 먼저 들어온 A를 삭제하려면 A의 앞 노드를 찾아 순회해야 한다.
- 마지막 노드(A)를 가리키는 역원형리스트는 삽입은 쉽지만, A를 삭제하려면 앞 노드 B를 찾아 순회해야 한다.
int F(int L[], int p, int q)
{
if (p<q)
{ int r, f1, f2;
r = (p+q)/2;
f1 = 2*F(L, p, r);
f2 = 2*F(L, r+1, q);
return f1+f2;
}
else if (p == q)
return L[p]*L[p];
else
return 0;
}
F(L, 0, n-1)의 시간 복잡도는 이다.
함수는 구간을 반으로 나눠 두 번 재귀 호출하고, 나머지 곱셈·덧셈은 상수 시간이다. 따라서 이다.
마스터 정리에서 이 상수항보다 크므로 이다. 재귀 트리로 보아도 호출 수는 약 2n개이다.
- : 단계마다 병합 같은 선형 작업이 있어야 나오는데, 이 함수는 단계마다 상수 작업뿐이다.
- : 결과값에 2를 곱하는 것은 값 계산일 뿐 호출 횟수를 늘리지 않는다.
- : 재귀 깊이는 이므로 호출 수가 지수적으로 늘지 않는다.
(단, 배열의 인덱스는 내림(floor)함수를 적용하여 구한다)
비교 횟수가 가장 많은 데이터는 12이다.
9개(인덱스 0~8)에서 첫 중간값은 인덱스 4의 15이다. 12를 찾으면 15 → 6 → 11 → 12 순으로 4회 비교한다.
- 4: 15 → 6 → 4로 3회 비교한다.
- 6: 15 → 6으로 2회 비교한다.
- 11: 15 → 6 → 11로 3회 비교한다.
| 10 | 5 | 8 | 50 | 1 |
㉡ 최소 대기를 위해 위와 같은 고객들의 도착 순서를 조정한 후의 모든 고객이 큐에서 대기하는 전체 시간
㉢ 최대 대기를 위해 위와 같은 고객들의 도착 순서를 조정한 후의 모든 고객이 큐에서 대기하는 전체 시간
㉠ ㉡ ㉢
㉠ 121, ㉡ 45, ㉢ 251이다.
각 고객의 대기 시간은 앞선 고객들의 서비스 시간 합이므로, 짧은 작업을 먼저 하면 최소, 긴 작업을 먼저 하면 최대가 된다.
㉠ 주어진 순서: 0 + 10 + 15 + 23 + 73 = 121
㉡ 짧은 순(1, 5, 8, 10, 50): 0 + 1 + 6 + 14 + 24 = 45
㉢ 긴 순(50, 10, 8, 5, 1): 0 + 50 + 60 + 68 + 73 = 251

노드 2에서 너비우선탐색을 하면 방문 순서는 2 → 1 → 3 → 0 → 6 → 4 → 5이다.
BFS는 큐를 쓰며 인접리스트에 적힌 순서대로 미방문 노드를 넣는다. 2의 리스트에서 1·3, 1에서 0·6, 3에서 4(2·6은 이미 방문), 0에서 5를 추가하므로 큐에 들어간 순서가 곧 방문 순서다.
- 2 → 1 → 0 → 5 → 4 → 3 → 6은 1에서 0, 0에서 5로 깊게 내려간 깊이우선탐색의 순서다.
- 2 → 1 → 3 → 0 → 4 → 5 → 6은 1의 이웃 6보다 3의 이웃 4를 먼저 방문해 큐 순서를 어겼다.
- 2 → 1 → 0 → 5 → 4 → 6 → 3은 시작 정점과 바로 인접한 3을 마지막에 방문해 너비우선 원칙에 맞지 않는다.
typedef struct node_struct {
int data;
struct node_struct *left, *right;
} node_t;
void JOB_Tree(node_t *root) {
node_t *temp;
if (root == NULL) return;
temp = root->right;
root->right = root->left; root->left = temp;
JOB_Tree(root->left); JOB_Tree(root->right);
}이 함수는 트리를 좌우 대칭(미러)으로 바꾼다.
각 노드에서 왼쪽·오른쪽 자식 포인터를 맞바꾼 뒤, 두 서브트리에 같은 작업을 재귀로 반복한다. 결국 모든 노드의 좌우가 뒤집힌다.
- 왼쪽 서브트리를 오른쪽으로 복사한다는 설명: 새 노드를 만들지 않고 포인터만 교환하므로 복사가 아니다.
- 왼쪽 서브트리를 오른쪽으로 이동한다는 설명: 한쪽만 옮기는 것이 아니라 양쪽을 서로 교환한다.
- 오른쪽 서브트리를 왼쪽으로 이동한다는 설명: 역시 양쪽이 동시에 바뀌고 하위 노드까지 모두 뒤집힌다.