포화이진트리에서는 항상 비단말노드 수 = 단말노드 수 − 1이므로 차이는 −1이다.
깊이가 k이면 단말노드는 개, 비단말노드는 개다.
따라서 로, 깊이와 무관하게 일정하다.
- 0: 두 개수가 같아야 하는데, 비단말노드가 항상 하나 적다.
- 1: 부호가 반대다. 단말노드 쪽이 하나 더 많다.
- k − 1: 차이는 깊이 k와 무관한 상수다.
#include <stdio.h>
void hanoi_tower(int n, char from, char tmp, char to)
{
if( n==1 ) printf("원판 1을 %c에서 %c로 옮긴다. \n", from, to);
else {
hanoi_tower(n-1, from, to, tmp);
printf("원판 %d을 %c에서 %c로 옮긴다. \n", n, from, to);
hanoi_tower(n-1, tmp, from, to);
}
}
void main()
{
hanoi_tower(4, 'A', 'B', 'C');
}
원판 4개를 옮기는 하노이타워는 총 회 이동하며, 여덟째 줄에는 가장 큰 원판 4을 A에서 C로 옮기는 문장이 출력된다.
재귀 구조상 먼저 원판 3개를 A에서 B로 옮기는 7줄()이 출력되고, 그다음 줄이 원판 4의 이동이며, 이후 7줄은 원판 3개를 B에서 C로 옮기는 과정이다.
- 원판 1을 C에서 B로: 전체 15줄 어디에도 나오지 않는 이동이다.
- 원판 3을 A에서 B로: 앞쪽 과정의 넷째 줄에 출력된다.
- 원판 2을 B에서 C로: 원판 2는 A→C, C→B, B→A, A→C로만 움직여 출력되지 않는다.
개수가 정해진 정렬 데이터에는 배열 + 이진탐색이 가장 적절하다.
크기가 고정이면 배열로 충분하고, 배열은 인덱스로 가운데 원소에 바로 접근할 수 있어 정렬된 상태에서 이진탐색으로 에 찾을 수 있다.
- 배열 − 순차탐색: 가능하지만 이라 정렬된 순서를 활용하지 못한다.
- 단순 연결 리스트 − 순차탐색: 크기가 고정이면 동적 삽입·삭제 장점이 필요 없고, 탐색도 이다.
- 단순 연결 리스트 − 이진탐색: 가운데 노드에 바로 접근할 수 없어 이진탐색이 효율적으로 성립하지 않는다.
| [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
|---|---|---|---|---|---|---|---|---|
| 21 | 37 | 22 | 17 | 11 | 30 | 5 | 10 | 9 |
배열을 최대 히프로 구성하고 루트를 출력·재구성하면 인덱스 6에는 9가 온다.
히프 구성: 마지막 부모부터 올라가며 조정하면 인덱스 3의 22와 30이, 이어서 루트 21과 37이 교환되어 37, 21, 30, 17, 11, 22, 5, 10, 9가 된다.
재구성: 루트 37을 출력하고 마지막 9를 루트로 올려 내린다. 9는 더 큰 자식 30과, 다시 22와 교환되어 30, 21, 22, 17, 11, 9, 5, 10이 된다.
- 5: 인덱스 7에 그대로 남는다.
- 10: 인덱스 8에 남는다.
- 22: 인덱스 3으로 올라간다.

B->left->right = B->right;
C->left = A;
B->right->left = B->left;
C->left = B->left;
옳지 않은 명령은 C->left->right = B->right; C->left = B->left; 이다.
C->left 는 B 이므로 첫 문장은 B 의 right 에 C 를 다시 넣을 뿐이고, 둘째 문장으로 C 의 left 만 A 로 바뀐다. 결국 A->right 가 여전히 B 를 가리켜 순방향 연결에서 B 가 빠지지 않는다.
- B->right->left = B->left; B->left->right = B->right; : C 의 left 를 A 로, A 의 right 를 C 로 바꾸는 표준 삭제 연산이다.
- A->right = C; C->left = A; : A 와 C 를 직접 양방향으로 연결하므로 B 가 제거된다.
- A->right = A->right->right; B->right->left = B->left; : A 의 right 가 C 로, C 의 left 가 A 로 바뀌어 B 가 제거된다.
구성 과정에서 LL 회전과 LR 회전만 사용된다.
20, 16, 15 삽입 시 20에서 LL 회전(16이 루트), 9, 7 삽입 시 15에서 LL 회전이 일어난다.
12는 루트 16의 왼쪽 자식 9의 오른쪽 서브트리로 들어가 LR 회전(15가 루트)이 일어나고, 10, 1, 13은 균형을 유지하며, 5는 7의 왼쪽 자식 1의 오른쪽으로 들어가 다시 LR 회전이 일어난다.
- LL·RR·RL 회전: RR과 RL 불균형은 한 번도 생기지 않는다.
- RR·RL 회전: 실제로 쓰인 LL과 LR이 모두 빠져 있다.
- LL·LR·RL 회전: 오른쪽 자식의 왼쪽으로 치우친 RL 불균형은 생기지 않는다.
| a | b | c | d | e | f | |
|---|---|---|---|---|---|---|
| a | 1 | 1 | ||||
| b | 1 | 1 | ||||
| c | 1 | 1 | ||||
| d | 1 | |||||
| e | 1 | 1 | ||||
| f |
위상 정렬 결과는 a, b, c, e, d, f이다.
간선은 a→b, a→c, b→c, b→d, c→d, c→e, d→f, e→d, e→f이다. 진입차수가 0인 노드를 차례로 꺼내면 a → b → c → e → d → f로 순서가 하나로 정해진다.
- a, b, c, d, e, f: e→d 간선이 있어 d가 e보다 앞설 수 없다.
- a, c, b, e, d, f: b→c 간선이 있어 c가 b보다 앞설 수 없다.
- a, c, e, b, d, f: 역시 c가 b보다 먼저 나와 b→c 간선을 어긴다.
스택에 여섯째로 push 되는 값은 (B + C) * D이다.
후위식 계산에서는 피연산자를 push 하고, 연산자를 만나면 두 값을 pop 해 계산 결과를 push 한다. 연산자 자체는 저장되지 않는다.
A, B, C가 첫째~셋째로 push → +에서 (B + C)가 넷째 → D가 다섯째 → *에서 (B + C) * D가 여섯째 → -에서 최종 결과가 일곱째로 push 된다.
- *: 연산자는 스택에 저장되지 않는다.
- (B + C): 넷째로 push 되는 값이다.
- A - (B + C) * D: 마지막 일곱째로 push 되는 값이다.
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| A | B | C |
다. 두 개의 원소를 삭제 라. F를 삽입
마. 하나의 원소를 삭제 바. G를 삽입
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| E | F | G | D |
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| F | G | D |
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| F | G | C | D |
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| G | B | C | D |
연산 후 큐에는 E, F, G, 빈칸, D(인덱스 0~4)가 남는다.
front는 첫 원소 바로 앞을 가리키므로 A, B, C는 인덱스 1~3에 있다. 삽입은 rear를, 삭제는 front를 로 옮긴 자리에서 일어난다.
D 삽입(인덱스 4) → E 삽입(인덱스 0) → A, B 삭제(front=2) → F 삽입(인덱스 1) → C 삭제(front=3) → G 삽입(인덱스 2).
- F, G, 빈칸, 빈칸, D 상태: 삭제되지 않은 E가 빠져 있고 F, G 위치도 한 칸씩 어긋난다.
- F, G, 빈칸, C, D 상태: C는 마지막 삭제에서 제거되었고 E가 빠져 있다.
- G, 빈칸, B, C, D 상태: B와 C는 이미 삭제되었고 E, F가 빠져 있다.
18을 넣을 때 충돌은 2회 발생한다.
6은 , 3은 3에 저장된다. 8은 3에서 충돌하고 2차 해싱 이동 폭 로 에 저장된다.
18은 에서 충돌(1회), 이동 폭 로 0에서 충돌(2회), 다음 는 비어 있어 저장된다.
- 0회: 1차 해시 주소 3은 이미 3이 차지하고 있다.
- 1회: 이동한 주소 0도 8이 차지하고 있다.
- 3회: 세 번째 탐사 위치 2는 비어 있어 더 충돌하지 않는다.
형제 노드를 항상 A[k+1]로 찾는 규칙은 틀렸다.
k가 짝수면 왼쪽 자식이라 형제가 A[k+1]이지만, k가 홀수면 오른쪽 자식이라 형제는 A[k−1]이다(루트는 형제가 없다).
- 부모 노드 − A[⌊k/2⌋]: 자식 2k와 2k+1을 2로 나눈 몫이 모두 k이므로 옳다.
- 왼쪽 자식 노드 − A[2k]: 레벨순서 연속 저장의 정의대로 옳다.
- 오른쪽 자식 노드 − A[2k+1]: 왼쪽 자식 바로 다음 칸이므로 옳다.
struct list_t {
int data;
struct list_t *link;
};
typedef struct list_t *list_p;
void foobar(list_p *ptr, struct list_t *node)
{
if (*ptr == NULL) {
*ptr = node;
node->link = node;
} else {
node->link = (*ptr)->link;
(*ptr)->link = node;
}
}foobar는 원형 단순 연결 리스트에서 *ptr이 가리키는 노드 뒤에 node를 삽입한다.
구조체의 링크가 link 하나뿐이므로 단순 연결이고, 빈 리스트일 때 node->link = node로 자기 자신을 가리키게 하므로 원형이다. 비어 있지 않으면 node가 기존 다음 노드를 가리키게 한 뒤 (*ptr)->link를 node로 바꿔 뒤에 삽입한다.
- 한 줄 단순 연결 리스트: 한 줄 리스트라면 마지막 link가 NULL이어야 하는데 자기 자신을 가리킨다.
- 한 줄 이중 연결 리스트: 왼쪽·오른쪽 두 링크가 없고 원형 구조다.
- 원형 이중 연결 리스트: 역방향 링크가 없어 이중 연결이 아니다.
단말 노드는 16, 51, 69이다.
45가 루트, 36은 왼쪽, 62는 오른쪽, 2는 36의 왼쪽, 16은 2의 오른쪽, 51은 62의 왼쪽, 75는 62의 오른쪽, 69는 75의 왼쪽에 놓인다. 자식이 없는 노드는 16, 51, 69뿐이다.
- 2, 45, 62, 75 조합: 모두 자식이 있는 내부 노드다.
- 2, 16, 45, 51 조합: 2는 16을, 45는 두 자식을 가진다.
- 36, 62, 69 조합: 36과 62는 자식이 있다.
| i | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] | [11] | [12] | [13] | [14] | [15] |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| E[i] | 3 | 5 | 6 | 8 | 10 | 13 | 15 | 16 | 17 | 21 | 23 | 26 | 27 | 29 | 31 | 33 |
int func(int E[ ], int first, int last, int K)
{
int mid;
if (last < first) return -1;
else {
㉠ mid = (first + last) / 2;
if (K == E[mid]) return mid;
else if (K < E[mid]) return func(E, first, mid-1, K);
else return func(E, mid+1, last, K);
}
}
func는 재귀 이진 탐색이며, 27을 찾을 때까지 ㉠은 4회 수행된다.
(0, 15): mid = 7, E[7] = 16 < 27 → 오른쪽
(8, 15): mid = 11, E[11] = 26 < 27 → 오른쪽
(12, 15): mid = 13, E[13] = 29 > 27 → 왼쪽
(12, 12): mid = 12, E[12] = 27 → 찾음
- 1회: 첫 mid의 값이 16이라 바로 찾지 못한다.
- 2회: 두 번째 mid의 값은 26이다.
- 3회: 세 번째 mid의 값은 29로 아직 27이 아니다.
ㄴ. newNode->llink = p;
ㄷ. newNode->rlink = p->rlink;
ㄹ. p->rlink->llink = newNode;
올바른 순서는 ㄴ − ㄷ − ㄹ − ㄱ이다.
핵심은 p->rlink(기존 오른쪽 노드)를 덮어쓰는 ㄱ을 마지막에 두는 것이다. ㄷ과 ㄹ은 모두 p->rlink로 기존 오른쪽 노드에 접근하므로 ㄱ보다 먼저 실행되어야 한다.
- ㄱ − ㄴ − ㄷ − ㄹ: ㄱ을 먼저 하면 기존 오른쪽 노드의 주소를 잃어 ㄷ에서 newNode가 자기 자신을 가리킨다.
- ㄴ − ㄱ − ㄹ − ㄷ: ㄱ 이후라 ㄹ은 newNode의 llink를, ㄷ은 rlink를 자기 자신으로 만든다.
- ㄴ − ㄷ − ㄱ − ㄹ: ㄱ 이후 p->rlink는 newNode라서 기존 오른쪽 노드의 llink가 갱신되지 않는다.

전체 완료시간을 줄이는 단일 작업은 유일한 임계경로 위의 a5 이다.
각 사건의 가장 이른 시간을 구하면 0→2→4→3→5→8→9 경로(a1, a4, a5, a7, a10, a13)의 길이가 7+3+4+5+5+2=26 으로 가장 길고, 이 경로가 유일한 임계경로이다. 임계경로가 하나뿐이므로 그 위의 작업을 단축하면 프로젝트 완료시간이 줄어든다.
- a0 : 0→1→3 경로는 사건 3 에 9 에 도착해 가장 이른 시간 14 보다 여유가 있어 임계작업이 아니다.
- a6 : 3→6→9 경로는 사건 9 에 22 에 도착해 26 보다 여유가 있다.
- a9 : 4→7 이후 경로는 사건 8·9 에 각각 16·17 에 도착해 여유가 크다.

옳지 않은 설명은 노드 분할이 3회 일어난다는 것으로, 실제 분할은 2회이다.
47 은 단말 (45, 50) 에 들어가 (45, 47, 50) 이 되므로 분할되어 47 이 부모로 올라간다. 루트 (30, 60) 이 (30, 47, 60) 이 되어 다시 분할되고, 47 이 새 루트가 된다.
- 트리의 깊이: 루트 (47), 중간 (30)·(60), 단말의 3단계이므로 깊이 3 이다.
- 단말노드: (30) 아래 (10, 20)·(45), (60) 아래 (50)·(75, 80) 이 된다.
- 루트 노드: 마지막 분할로 올라간 47 하나만 가진다.

세 순회의 일곱째 방문 노드는 차례로 G, E, C 이다.
전위순회는 A B D F C E G H, 중위순회는 B D F A C G E H, 후위순회는 F D B G H E C A 순으로 방문한다. 각 순서열의 일곱째 노드를 뽑으면 G, E, C 가 된다.
- H H E : 전위의 일곱째는 H 가 아니라 G 이다.
- E G E : 전위의 일곱째가 G, 중위의 일곱째가 E 이므로 앞의 두 값이 뒤바뀌었다.
- G E H : 후위의 일곱째는 H 가 아니라 C 이다.

최소 비용 신장 트리의 비용은 32 이다.
크루스칼 알고리즘으로 가중치가 작은 간선부터 사이클이 생기지 않게 고르면 1, 2, 3, 4, 5 가 차례로 채택되고, 7 은 이미 연결된 정점끼리라 사이클이 생겨 제외된다. 가중치 8 간선 중에는 왼쪽 위와 맨 위 정점을 잇는 것만 채택되고, 마지막으로 9 를 넣어 정점 8 개를 간선 7 개로 모두 잇는다.
합계는 1+2+3+4+5+8+9=32 이다.
- 31 : 최소 비용 32 보다 작아 어떤 신장 트리로도 만들 수 없다.
- 34 : 왼쪽 정점을 잇는 데 9 대신 11 을 고르는 식으로 더 비싼 간선을 쓴 값이다.
- 42 : 최소가 아닌 신장 트리의 비용이다.
int length(listPointer last)
{
listPointer temp = last;
int count = 0;
if (last) {
for(count = 1; ㉠ ; count++)
temp = temp->link;
}
return count;
}
㉠에는 temp->link != last가 들어간다.
temp는 last에서, count는 1에서 시작한다. 다음 노드가 last가 아닐 때마다 한 칸 이동하며 count를 늘리면, 한 바퀴를 돌아 last 직전 노드에서 멈출 때 count가 전체 노드 수가 된다. 예컨대 노드가 3개면 두 번 이동해 count = 3이다.
- temp == last->link: 시작 시 temp는 last라 노드가 2개 이상이면 즉시 거짓이 되어 1로 끝난다.
- temp != last->link: 첫 노드에 도달하자마자 멈춰 노드가 2개 이상이면 항상 2를 반환한다.
- temp->link == NULL: 원형 리스트에는 NULL 링크가 없어 처음부터 거짓이 되고 1로 끝난다.