
임계 경로는 V1-V2-V6-V5-V8이며 길이는 27이다.
임계 경로는 시작점에서 끝점까지 가장 긴 경로다. 각 정점의 가장 이른 시작 시간을 구하면 V2=8, V3=5, V4=7, V7=10이다.
V6은 V2를 거친 8+9=17이 최대이고, V5는 V6을 거친 17+5=22가 최대이며, V8은 22+5=27이 된다.
- V1-V3-V6-V5-V8: 5+8+5+5=23으로 27보다 짧다.
- V1-V4-V6-V5-V8: 7+6+5+5=23으로 27보다 짧다.
- V1-V4-V7-V5-V8: 7+3+8+5=23으로 27보다 짧다.
new.data ← x;
㉠
㉡
pre.rlink ← new;
new.llink ← pre;
빈 칸에는 차례로 new.rlink ← pre.rlink, new.rlink.llink ← new가 들어간다.
pre 뒤에 삽입하려면 먼저 새 노드의 오른쪽 링크가 pre의 원래 후속 노드를 가리키게 하고, 그 후속 노드의 왼쪽 링크를 새 노드로 바꾼 뒤 pre.rlink를 갱신해야 한다. pre.rlink를 먼저 덮어쓰면 원래 후속 노드를 잃는다.
- new.rlink.llink에 new.llink를 넣는 조합: 이 시점의 new.llink는 아직 설정되지 않은 값이라 후속 노드의 역방향 링크가 깨진다.
- new.llink ← pre.rlink 뒤에 new.llink.rlink ← new를 두는 조합: 새 노드의 왼쪽 링크는 선행 노드 pre를 가리켜야 하는데 후속 노드를 넣어 방향이 뒤바뀐다.
- new.llink ← pre.rlink 뒤에 new.llink.rlink ← new.rlink를 두는 조합: 왼쪽 링크 방향이 뒤바뀐 데다 초기화되지 않은 new.rlink를 연결에 사용한다.
평균 비교횟수는 이다.
8, 12, 23을 넣으면 8에서 RR 불균형이 생겨 좌회전으로 12가 루트가 된다. 이어 9, 7을 넣으면 루트 12, 왼쪽 8(자식 7, 9), 오른쪽 23이 된다.
6을 넣으면 루트 12에서 LL 불균형이 생겨 우회전하고, 최종 트리는 루트 8, 왼쪽 7(왼쪽 자식 6), 오른쪽 12(자식 9, 23)이다.
비교횟수(깊이)는 8이 1, 7과 12가 2, 6·9·23이 3이다.
(단, 리스트의 시작 주소를 나타내는 포인터는 start이며 노드의 연결포인터 필드는 link이다)
p = start;
q = NULL;
while (p != NULL) {
㉠
p = p->link;
q->link = r;
}
start = q;
㉠에는 r = q; q = p;가 들어간다.
r은 이미 뒤집힌 부분의 머리(직전 q), q는 현재 노드, p는 다음 노드를 가리킨다. r에 q를 보관하고 q를 p로 옮긴 뒤 p를 전진시키고, q->link = r 로 현재 노드의 링크를 뒤집힌 앞부분으로 돌린다.
- q = q->link; r = q; : 첫 반복에서 q가 NULL이라 역참조 오류가 나고, r과 q가 같아져 노드가 자기 자신을 가리킨다.
- r = q; q = p->link; : q가 현재 노드가 아닌 다음 노드가 되어 현재 노드의 링크를 뒤집지 못한다.
- q = q->link; 만 두는 경우: q가 NULL에서 출발하므로 역참조 오류가 나고 r도 설정되지 않는다.
원래 계산된 슬롯을 벗어나 저장되는 데이터는 44, 45, 77, 56의 4개이다.
해시값: 54→10, 27→5, 70→4, 55→0, 13→2, 2→2, 37→4, 23→1, 33→0, 44→0, 45→1, 77→0, 56→1, 6→6, 9→9
버킷 0은 55·33, 버킷 2는 13·2, 버킷 4는 70·37로 찬다. 44는 버킷 0이 차서 버킷 1의 남은 칸으로, 45는 버킷 1·2가 차서 버킷 3으로, 77은 버킷 0~2가 차서 버킷 3의 남은 칸으로 간다.
56은 버킷 1~4가 모두 차 있어 버킷 5로 밀려나고, 6과 9는 제자리에 들어간다. 따라서 선형 조사로 밀려난 데이터는 4개다.
연결리스트 구현과 관련이 없는 것은 비트단위 논리곱이다.
비트 연산자 &는 정수의 비트를 다루는 연산일 뿐, 노드를 만들고 잇는 데에는 자기참조 구조체·동적 할당·포인터가 쓰인다.
- 자기참조 구조체: 노드 구조체가 같은 형의 구조체를 가리키는 포인터 멤버를 가져 다음 노드와 연결된다.
- 동적 메모리 할당: malloc 등으로 실행 중 필요한 만큼 노드를 만들고 free로 해제한다.
- 포인터: 노드 사이의 연결과 리스트의 시작(head)을 가리키는 데 쓰인다.
2 1
3 1 2
4 3 2 1
5 4 2 1 3
( )
7 4 6 1 3 2 5
( )
빈 칸은 차례로 (6 4 5 1 3 2), (8 7 6 4 3 2 5 1)이다.
최대 힙 삽입은 새 키를 배열 끝에 넣고 부모(인덱스 i/2)보다 크면 교환하며 올라간다.
6 삽입: 인덱스 6 → 3 → 1로 올라가 [6 4 5 1 3 2]
7 삽입: 인덱스 7 → 3 → 1로 올라가 [7 4 6 1 3 2 5] (주어진 단계와 일치)
8 삽입: 인덱스 8 → 4 → 2 → 1로 올라가 [8 7 6 4 3 2 5 1]
- (6 4 1 5 3 2)로 시작하는 조합: 6은 인덱스 3을 거쳐 올라가므로 인덱스 3에는 루트였던 5가 내려와야 한다.
- (6 4 5 1 2 3)으로 시작하는 조합: 3은 교환 경로 밖인 인덱스 5에 그대로 있어야 하는데 2와 자리가 바뀌었다.
- (8 7 6 3 4 2 5 1)을 둔 조합: 8이 인덱스 4를 지나며 4를 아래로 내리므로 인덱스 4에는 4, 인덱스 5에는 3이 와야 한다.
옳은 설명은 차수가 0인 노드를 리프 노드라고 한다는 것이다.
리프(단말) 노드는 자식이 없는 노드이므로 자식 수인 차수가 0이다.
- 루트가 많을수록 좋은 트리: 트리의 루트는 하나뿐이며, 루트가 여럿이면 트리가 아니라 포리스트다.
- 재귀 구현이 실행 시간을 줄인다: 재귀는 코드를 간결하게 할 뿐 함수 호출 오버헤드 때문에 반복 구현보다 대체로 느리다.
- 최대 레벨과 높이가 무관하다: 트리의 높이는 노드의 최대 레벨로 정해지므로 둘은 직접 연관된다.




최적 이진탐색트리는 while을 루트로 하고 왼쪽 자식 if, 그 왼쪽 자식 do로 이어지는 트리이며 비용은 1.65이다.
탐색 확률이 가장 큰 while(0.5)을 루트에 두어야 가중 레벨 합이 작아진다. 내부 노드 비용은 이다.
외부 노드의 (레벨-1) 합은 3+3+2+1=9이므로 , 전체 비용은 이다.
- do를 루트로 하고 오른쪽으로 if, while이 이어지는 트리: 로 더 크다.
- if를 루트로 하고 do와 while을 양쪽 자식으로 둔 균형 트리: 으로 더 크다.
- do를 루트로 하고 오른쪽 자식 while, 그 왼쪽 자식 if를 둔 트리: 로 더 크다.
후위 순회 결과는 AB*CD*E/-이다.
전위 순회 -*AB/*CDE에서 루트는 -, 왼쪽 서브트리는 *AB, 오른쪽 서브트리는 /*CDE이다. 오른쪽은 다시 루트 / 아래 왼쪽 *CD, 오른쪽 E로 나뉜다.
즉 식은 (A*B)-((C*D)/E)이고, 후위 순회(왼쪽 → 오른쪽 → 루트)는 AB*, CD*E/, - 순으로 이어진다.
- AB*C*DE/-: ((A*B)*C)-(D/E)를 나타내 트리 구조가 다르다.
- AB*CDE*/-: (A*B)-(C/(D*E))를 나타내 나눗셈과 곱셈의 위치가 바뀌었다.
- ABC*D*E/-: A-(((B*C)*D)/E)를 나타내 왼쪽 서브트리가 A*B가 되지 않는다.
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j = j + i)
for (k = 1; k <= n; k++)
x = x + k + 1;
시간 복잡도는 이다.
j가 i씩 증가하므로 가운데 루프는 약 회, 가장 안쪽 루프는 매번 회 돈다.
조화급수의 합이 이므로 전체는 이다.
- : 가운데 루프 횟수가 상수가 아니라 i에 따라 줄어드는 합이어서 로그 인자가 남는다.
- : j가 1씩 증가할 때의 결과로, 증가폭 i를 반영하지 않았다.
- : 실제 반복 횟수보다 과대한 상한이다.
모든 n (n≥n0)에 대해 f(n)≤cg(n)을 만족하는 두 양의 상수 c와 n0가 존재하면 f(n)=X(g(n))이다.
정의된 X는 점근적 상한인 빅오(O) 표기이다.
충분히 큰 모든 n에서 f(n)이 cg(n) 이하라는 조건이므로 g(n)이 f(n)의 증가율을 위에서 제한한다.
- Ω: 을 요구하는 하한 정의로 부등호 방향이 반대다.
- Θ: 처럼 위아래를 모두 감싸야 하므로 상한 조건만으로는 성립하지 않는다.
- Γ: 알고리즘의 점근 표기로 쓰이지 않는 기호다.
(단, t는 0이 아닌 희소행렬 원소의 개수이며, 배열의 크기는 배열 원소의 수를 의미한다)
필요한 배열 크기는 3t이다.
희소행렬은 0이 아닌 원소만 (행, 열, 값)의 3원소 쌍으로 저장하는 것이 효과적이며, 원소 t개마다 정수 3개가 필요하다.
- m*n: 0까지 모두 저장하는 일반 2차원 배열 방식이라 희소행렬에서는 공간 낭비가 크다.
- t: 값만 저장하면 각 값이 행렬의 어느 위치인지 알 수 없다.
- m+n+t: 값 t개에 행·열 수를 더한 크기로는 각 원소의 행·열 좌표를 모두 나타낼 수 없다.
옳지 않은 것은 선택정렬의 최악 자료이동 횟수도 라는 설명이다.
선택정렬은 비교가 이지만 각 단계에서 최솟값과 한 번만 교환하므로 자료 이동은 최악에도 이다.
- 합병정렬과 힙정렬의 공간: 배열 합병정렬은 크기 n의 보조 배열이 필요하지만 힙정렬은 제자리 정렬이므로 옳다.
- 합병정렬의 시간: 입력 상태와 관계없이 반씩 나누어 합병하므로 항상 으로 옳다.
- 정렬된 입력의 퀵정렬: 첫 원소를 기준으로 하면 분할이 한쪽으로 치우쳐 이 되어 인 힙정렬보다 느리므로 옳다.
A[2][1][2]에 저장되는 값은 18이다.
A[4][2][3]의 행우선 저장에서 첫째 인덱스 1 증가는 칸, 둘째 인덱스 1 증가는 3칸, 셋째 인덱스 1 증가는 1칸이다.
A[0][0][0]이 오프셋 0에서 값 1을 가지므로 오프셋 17의 값은 이다. 17은 오프셋을 값으로 착각한 결과다.
(단, 크기가 a, b인 두 개의 런을 병합하는 시간은 a + b라고 가정한다)
| 런 이름 | r1 | r2 | r3 | r4 | r5 |
|---|---|---|---|---|---|
| 크기 | 2 | 4 | 5 | 7 | 8 |
최소 병합 시간은 58이다.
매번 가장 작은 두 런을 먼저 합치면(허프만 방식) 전체 병합 시간이 최소가 된다.
- 26: 마지막 병합 한 번의 비용(전체 데이터 크기)일 뿐 중간 병합 비용이 빠졌다.
- 84: 큰 런부터 합치는 순서()의 비용으로, 큰 런이 여러 번 다시 병합되어 최소가 아니다.
- 88: 어떤 병합 순서로도 나오지 않는 값이다. 가장 불리한 순서도 85에 그친다.
public static int xxx(int n) {
if (n == 0)
return 4;
return 1 + xxx(n - 1);
}xxx(5)는 9를 반환한다.
n이 0이 아니면 1을 더하며 n-1로 재귀하므로 다섯 차례 1이 더해지고, n이 0이 되면 기저값 4를 반환한다.
- 0: 기저 조건의 n 값을 반환값으로 착각한 것이다.
- 4: 기저값만 보고 재귀 과정에서 더해지는 1을 빠뜨렸다.
- 5: 더해진 1의 개수만 세고 기저값 4를 빠뜨렸다.
옳지 않은 것은 Kruskal 알고리즘이 깊이우선탐색을 사용한다는 설명이다.
Kruskal 알고리즘은 간선을 가중치 순으로 정렬해 차례로 고르고, 사이클 여부를 Union-Find(분리 집합)로 판단한다.
- 연결 요소: 방문하지 않은 정점에서 DFS를 반복 시작하면 한 번의 탐색마다 연결 요소 하나를 얻는다.
- 신장트리: 연결 그래프에서 DFS가 지나간 간선들이 깊이우선 신장트리를 이룬다.
- 시작 정점: DFS는 그래프의 어느 정점에서든 시작할 수 있다.
옳은 설명은 큐의 삽입과 삭제가 모두 O(1) 시간에 수행된다는 것이다.
큐는 front와 rear 위치를 유지하므로 rear에서 삽입, front에서 삭제가 원소 이동 없이 상수 시간에 이루어진다.
- 크기를 미리 정해야 한다: 연결리스트로 구현하면 크기를 미리 정하지 않아도 된다.
- 같은 끝에서 삽입·삭제: 큐는 한쪽(rear)에서 삽입, 반대쪽(front)에서 삭제한다. 같은 끝을 쓰는 것은 스택이다.
- LIFO 순서: 큐는 먼저 들어온 자료가 먼저 나가는 FIFO 구조이며, LIFO는 스택이다.

는 정점 1, 2만 중간 정점으로 허용해 갱신한 행렬로, 4행이 (2, 5, -5, 0, -2)이고 1→4가 4, 3→4가 5, 3→5가 11인 행렬이다.
정점 1 경유: 1로 들어오는 간선은 4→1(2)뿐이므로 4→2=2+3=5, 4→5=2+(-4)=-2로 갱신된다.
정점 2 경유: 1→4=3+1=4, 3→4=4+1=5, 3→5=4+7=11로 갱신되고, 4→5는 5+7=12보다 기존 -2가 작아 유지된다.
- 1→4, 4→2, 3→5 등이 아직 무한대인 행렬은 간선 가중치 그대로인 초기 행렬 이다.
- 4→2가 -1인 행렬은 4→3→2(-5+4) 경로를 반영한 것으로, 정점 3까지 경유를 허용해야 나오는 값이다.
- 모든 칸이 유한값으로 채워진 행렬은 정점 5까지 모두 경유를 허용한 최종 결과이다.