[200, 192, 63, 72, 185, 60, 62, 16, 52, 37, 22, 11, 5, 38]
세 차례 삭제 후 앞 11칸은 [72, 52, 63, 16, 38, 60, 62, 11, 5, 37, 22]이다.
삭제는 루트를 꺼내고 마지막 원소를 루트로 올린 뒤 더 큰 자식과 교환하며 내려보내는 하향 재정렬로 진행한다.
첫 삭제(200 제거): 38이 192·185와 교환 → [192, 185, 63, 72, 38, 60, 62, 16, 52, 37, 22, 11, 5]
둘째 삭제(192 제거): 5가 185·72·52와 교환 → [185, 72, 63, 52, 38, 60, 62, 16, 5, 37, 22, 11]
셋째 삭제(185 제거): 11이 72·52·16과 교환 → [72, 52, 63, 16, 38, 60, 62, 11, 5, 37, 22]
- [72, 63, 62, 60, …]처럼 내림차순으로 정렬된 나열: 힙은 부모가 자식보다 크기만 하면 되며, 삭제 연산이 전체를 정렬하지는 않는다.
- [72, 52, 63, 38, 16, …]으로 시작하는 나열: 38은 첫 삭제에서 다섯째 칸에 자리 잡은 뒤 움직이지 않고, 넷째 칸은 셋째 삭제에서 16이 채운다.
- 끝이 5, 11, 37, 22인 나열: 11은 두 자식 16과 5 중 큰 16과 교환되어 여덟째 칸에 놓이고, 5는 아홉째 칸에 그대로 남는다.
void search( vertex v )
{
visited[v] = 1 ;
for each vertex w adjacent to v
if ( !visited[w] ) search( w ) ;
}
필요한 자료구조는 스택, 시간복잡도는 O(|V| + |E|)이다.
주어진 알고리즘은 방문하지 않은 인접 정점으로 재귀 호출을 이어 가는 깊이우선탐색이므로, 반복형으로 바꾸면 재귀 호출 스택을 명시적 스택으로 대신한다. 인접리스트에서는 각 정점을 한 번 방문하고 각 간선을 상수 번 검사하므로 정점 수와 간선 수의 합에 비례한다.
- 큐와 O(|E|)의 조합: 큐는 너비우선탐색에 쓰는 자료구조이며, 정점 방문 비용인 |V| 항도 빠져 있다.
- 스택과 의 조합: 자료구조는 맞지만 제곱 시간은 인접행렬로 표현했을 때의 수행시간이다.
- 큐와 의 조합: 자료구조와 시간복잡도 모두 인접행렬 기반 너비우선탐색에 해당한다.
간선 가중치가 모두 다를 때 가장 작은 간선은 항상 최소비용 신장트리에 포함된다.
최소 간선 e를 뺀 최소비용 신장트리가 있다고 하면, e를 추가해 생긴 사이클에서 e보다 무거운 간선 하나를 빼면 비용이 더 작은 신장트리가 되어 모순이다. 크루스칼 알고리즘이 가장 먼저 선택하는 간선도 이 간선이다.
- 사이클의 최소 간선이 항상 포함된다는 설명: 사이클 성질은 사이클의 가장 무거운 간선이 제외됨을 보장할 뿐이며, 최소 간선이라도 두 끝점을 더 가벼운 간선들로만 이루어진 다른 경로가 잇고 있으면 빠진다.
- Dijkstra 결과가 최소비용 신장트리라는 설명: Dijkstra는 시작점에서 각 정점까지의 거리를 최소화하는 최단경로 트리를 만들 뿐, 간선 가중치의 총합을 최소화하지 않는다.
- 최소비용 신장트리가 항상 두 개 이상이라는 설명: 간선 가중치가 모두 다르면 최소비용 신장트리는 유일하다.
ㄴ. 무방향 그래프에서 모든 정점의 차수(degree)의 합은 간선의 수와 같다.
ㄷ. 정점이 v개인 무방향 완전그래프의 간선의 수는 개이다.
ㄹ. 정점이 v개, 간선이 e개인 그래프를 인접행렬로 표현하면 필요한 메모리는 O(v + e)이다.
ㅁ. 인접행렬로 표현된 정점이 v개, 간선이 e개인 무방향 그래프에서 너비우선탐색의 수행시간은 O()이다.
옳은 문장은 ㄱ, ㅁ의 두 개이다.
무방향 그래프는 간선 (i, j)와 (j, i)가 같으므로 인접행렬이 대칭이다. 인접행렬 기반 너비우선탐색은 정점마다 행 하나(v칸)를 모두 훑으므로 이다.
- 차수의 합: 간선 하나가 양 끝 정점의 차수를 하나씩 올리므로 간선 수의 2배()이다.
- 완전그래프의 간선 수: 서로 다른 두 정점 쌍의 수인 개이다.
- 인접행렬의 메모리: 간선 수와 무관하게 행렬이 필요하므로 이며, O(v + e)는 인접리스트의 공간이다.
ㄴ. 해시함수는 서로 다른 자료는 항상 서로 다른 버켓(bucket)에 사상(mapping)시킨다.
ㄷ. 탐색 성능은 적재 밀도(loading density)가 높을수록 좋아진다.
ㄹ. 최대값을 갖는 자료를 찾는데 걸리는 시간은 O(n)이다.
ㅁ. 해시함수값은 충돌이 적어야하고, 해시테이블 주소에 고르게 분포하는 것이 좋다.
옳은 것은 ㄹ, ㅁ이다.
해싱은 키의 대소 순서를 보존하지 않으므로 최대값을 찾으려면 모든 자료를 확인해야 해 O(n)이 걸린다. 좋은 해시함수는 충돌이 적고 주소에 고르게 분포해야 한다.
- 탐색 시간 O(log n): 해싱의 평균 탐색 시간은 O(1)이며, O(log n)은 이진탐색이나 균형 탐색트리의 성능이다.
- 서로 다른 자료가 항상 다른 버켓으로 간다는 설명: 키 공간이 주소 공간보다 커서 서로 다른 키가 같은 주소로 가는 충돌이 생긴다.
- 적재 밀도가 높을수록 성능이 좋다는 설명: 적재 밀도가 높을수록 충돌이 늘어 탐색 성능이 나빠진다.
옳지 않은 것은 연결리스트가 배열보다 삽입·삭제가 느리고 메모리 낭비가 많다는 설명이다.
연결리스트는 위치만 알면 링크만 바꿔 삽입·삭제하므로 원소를 밀고 당겨야 하는 배열보다 빠르다. 또 필요할 때마다 노드를 할당하므로 크기를 미리 크게 잡는 배열보다 빈 공간 낭비가 적다.
- 우선순위 큐: 삽입 순서와 무관하게 우선순위가 가장 높은(최대 또는 최소) 원소부터 삭제되며 주로 힙으로 구현한다.
- 스택: 후입선출 구조라 함수 호출과 후위식 계산에 쓰이며, 배열과 연결리스트 모두로 구현할 수 있다.
- 큐: 선입선출 구조라 먼저 들어온 작업을 먼저 처리하는 작업 스케줄링에 쓰인다.
A − B 의 값은 이다.
최대 노드 수는 모든 레벨이 꽉 찬 포화 이진트리일 때로, 레벨 i에 개씩 있으므로 이다.
최소 노드 수는 레벨마다 노드가 하나뿐인 편향 이진트리일 때로 이다.
- : 깊이 1이면 노드가 하나뿐이라 A − B 는 0이어야 하는데 3이 된다.
- : 깊이 1에서 1이 되어 0이 아니므로 맞지 않는다.
- : 깊이 1에서 2가 되어 상수항 부호가 틀렸다.
높이가 가장 낮은 것은 4, 2, 5, 6, 1, 3 순서의 삽입이다.
루트 4의 왼쪽에 2, 오른쪽에 5가 오고, 1과 3은 2의 양쪽 자식, 6은 5의 오른쪽 자식이 되어 높이 3(레벨 수 기준)이다. 이는 노드 6개인 이진트리가 가질 수 있는 최소 높이이다.
- 1, 2, 3, 5, 4, 6: 1→2→3→5로 오른쪽으로만 이어지고 4가 5의 왼쪽에 붙어 높이 5이다.
- 3, 1, 4, 2, 6, 5: 3→4→6→5 경로가 생겨 높이 4이다.
- 2, 1, 3, 4, 6, 5: 2→3→4→6→5 경로가 생겨 높이 5이다.





JAN 삽입 후 LR 회전이 일어나 MAR가 새 루트가 되고, 왼쪽에 AUG(자식 APR, JAN), 오른쪽에 MAY(오른쪽 자식 NOV)가 오는 트리가 옳다.
JAN은 MAY보다 작고 AUG보다 크며 MAR보다 작으므로 MAR의 왼쪽 자식으로 들어간다. 이때 MAY의 왼쪽 높이는 3, 오른쪽 높이는 1이 되어 균형인수가 +2가 되고, 삽입 위치가 왼쪽 자식(AUG)의 오른쪽 서브트리이므로 LR 불균형이다.
LR 회전은 AUG를 중심으로 왼쪽 회전한 뒤 MAY를 중심으로 오른쪽 회전하는 것으로, 중간값인 MAR가 위로 올라가고 MAR의 왼쪽 자식 JAN은 AUG의 오른쪽 자식으로 옮겨진다.
- MAR의 왼쪽에 JAN만 붙이고 루트를 MAY로 둔 트리: 이진 탐색 순서는 맞지만 MAY의 균형인수가 +2로 AVL 조건을 위반한다.
- JAN을 NOV의 왼쪽 자식으로 둔 트리: JAN은 MAY보다 작으므로 오른쪽 서브트리에 올 수 없어 탐색 순서가 깨진다.
- JAN을 APR의 오른쪽 자식으로 둔 트리: JAN은 AUG보다 크므로 AUG의 왼쪽 서브트리에 올 수 없고, 균형도 깨진다.

두 순회 결과를 나란히 비교하면 같은 자리에서 일치하는 노드는 B, E, I, G로 4회이다.
전위순회(루트→왼쪽→오른쪽)는 A, B, D, E, H, C, F, I, J, G 순이고, 중위순회(왼쪽→루트→오른쪽)는 D, B, H, E, A, F, J, I, C, G 순이다.
2번째 B, 4번째 E, 8번째 I, 10번째 G가 같고 나머지 자리는 모두 다르다.
- 3회: 네 자리 중 하나(예: 마지막 G)를 빠뜨렸을 때 나오는 값이다.
- 5회: 실제 일치 수보다 많아, 순회 순서를 잘못 구했을 때 나오는 값이다.
- 6회: H를 E의 오른쪽 자식으로 보는 등 트리 구조를 잘못 읽었을 때 나올 수 있는 값으로, 실제 일치는 4회뿐이다.
옳지 않은 것은 이다.
빅오의 곱은 각 함수를 곱하므로 이 된다. 은 보다 빠르게 증가하므로 로 줄일 수 없다. 반면 덧셈은 가장 빠르게 증가하는 항만 남는다.
- O(n) + O(n) = O(n): 상수배 차이는 무시되므로 성립한다.
- : 이 보다 느리게 증가하므로 성립한다.
- : 차수가 큰 항만 남으므로 성립한다.
procedure BINARYSEARCH(A, n, x, j)
lower ← 1 ; upper ← n ;
while lower ≤ upper do
mid ← the middle element;
case
: x > A(mid): ㉠ ;
: x < A(mid): ㉡ ;
: else : j ← mid ; return;
end
end
j ← 0 ;
end
㉠은 lower ← mid + 1, ㉡은 upper ← mid - 1이다.
x가 A(mid)보다 크면 찾는 값은 mid 오른쪽에 있으므로 하한을 mid 다음으로 올리고, 작으면 왼쪽에 있으므로 상한을 mid 앞으로 내린다. mid는 이미 비교했으므로 ±1로 제외해야 구간이 줄어 반복이 끝난다.
- upper ← mid + 1 / lower ← mid - 1: x가 클 때 상한을 건드려 왼쪽 구간을 남기므로 찾는 값을 놓친다.
- lower ← mid - 1 / upper ← mid + 1: 갱신할 변수는 맞지만 ±1 방향이 반대라 mid가 구간에 다시 포함되므로, lower와 upper가 같아진 뒤에도 구간이 줄지 않아 반복이 끝나지 않을 수 있다.
- upper ← mid - 1 / lower ← mid + 1: x가 클 때 오른쪽이 아닌 왼쪽 구간을 남겨 찾는 값을 놓친다.
| [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
|---|---|---|---|---|---|---|---|---|---|
| 8 | 1 | 4 | 9 | 6 | 3 | 5 | 2 | 7 | 0 |
(보기의 인덱스: [0] [1] [2] [3] [4] [5] [6] [7] [8] [9])
1단계 분할 결과는 7 1 4 0 6 3 5 2 8 9이다.
피봇 8을 두고 왼쪽 포인터 i는 8보다 큰 값, 오른쪽 포인터 j는 8보다 작은 값을 찾아 교환한다.
i는 9([3]), j는 0([9])에서 멈춰 교환 → 8 1 4 0 6 3 5 2 7 9
다시 i는 9([9]), j는 7([8])에서 멈추고 두 포인터가 엇갈린다.
마지막으로 피봇과 j 위치의 7을 교환 → 7 1 4 0 6 3 5 2 8 9
- 7 1 4 6 3 5 2 0 8 9: 9와 0의 교환이 반영되지 않아 0이 [3]에 오지 않았다.
- 2 1 4 0 6 3 5 7 8 9: 피봇은 j 위치의 7과 교환되므로 [0]에는 7, [7]에는 2가 그대로 있어야 한다.
- 0 1 4 2 6 3 5 7 8 9: [0]에는 7, [3]에는 0, [7]에는 2가 와야 하므로 교환 결과와 맞지 않는다.
아홉째로 저장되는 요소는 K(2, 2, 1)이다.
행 우선순서에서는 마지막 첨자가 가장 빨리 변한다. 첫째 첨자 하나당 3 × 2 = 6개, 둘째 첨자 하나당 2개가 묶인다.
- K(1, 2, 2): 로 넷째이다.
- K(1, 3, 2): 으로 여섯째이다.
- K(2, 3, 2): 로 마지막 열두째이다.
A[100][100]에 저장된 상삼각행렬을 기억 공간을 절약하기 위해서 0이 아닌 데이터만 일차원 배열 B[5050]에 저장하고자 한다. A[0][0]은 B[0]에 저장하고, 0이 아닌 A의 데이터들을 행 우선 순서로 B에 저장할 때, A[90][93]은 B의 어느 위치에 저장되는가?

A[90][93]은 B[4998]에 저장된다.
상삼각행렬을 행 우선으로 저장하면 i행에는 열 i부터 99까지 100−i개의 원소가 있으므로, A[i][j]의 위치는 앞선 0~(i−1)행의 원소 수 합에 (j−i)를 더한 값이다.
- B[4999]: 위치를 1부터 센 것처럼 하나를 더한 값이다.
- B[5000]: 행 내부 오프셋 (j−i)=3 대신 다른 값을 더하는 등 위치 계산을 잘못한 값이다.
- B[5001]: 앞선 행들의 원소 수 합 4995에 오프셋을 잘못 더한 값으로, 실제 위치보다 3칸 뒤이다.
후위식의 넷째 연산자는 + 연산자이다.
전위식을 연산자와 두 피연산자 단위로 묶으면 ((A − B) + (C / D) * E) − F 구조이다. 이를 후위식으로 바꾸면 A B − C D / E * + F −이고, 연산자 순서는 −, /, *, +, − 이다.
- * 연산자: 셋째로 나온다.
- − 연산자: 첫째와 다섯째에 나오며 넷째가 아니다.
- / 연산자: 둘째로 나온다.
void push(int *top, int data) { // 스택에 data를 추가
if ( *top >= 99) { stack_full() ; return ; }
㉠;
}int pop(int *top) { // 스택에서 데이터를 삭제 후 반환
if ( *top == -1) { return stack_empty() ; }
㉡;
}㉠은 stack[++*top](top을 먼저 올린 뒤 저장), ㉡은 return stack[*top--](현재 top 값을 반환한 뒤 내림)이다.
top은 마지막 원소의 위치를 가리키고 빈 스택에서 −1이므로, push는 top을 하나 올린 칸에 저장해야 stack[0]부터 채워진다. pop은 지금 top 칸의 값을 꺼낸 뒤 top을 내려야 한다. 엄밀한 C 문법에서는 후위 --가 *보다 먼저 결합하므로 의도대로 동작하려면 stack[(*top)--]처럼 괄호를 써야 한다.
- stack[*top++] / return stack[--*top]: push가 올리기 전 위치(빈 스택이면 −1)에 저장해 범위를 벗어나고, pop은 꼭대기 아래 칸의 값을 반환한다.
- stack[*top++] / return stack[*top--]: pop은 맞지만 push가 올리기 전 위치에 저장한다.
- stack[++*top] / return stack[--*top]: push는 맞지만 pop이 꼭대기가 아닌 그 아래 칸의 값을 반환한다.
struct list_node {
char data ;
struct list_node *link;
}
typedef struct list_node *list_pointer;
int CListLength(list_pointer ptr){
list_pointer temp ;
int count = 0 ;
if ( ㉠ ) {
temp = ptr ;
do { count + + ;
} while ( ㉡ ) ;
}
return count;
}㉠은 ptr, ㉡은 temp=temp->link, temp != ptr이다.
리스트가 비어 있지 않을 때(ptr가 NULL이 아닐 때)만 세기 시작하고, do-while 안에서 개수를 센 뒤 temp를 다음 노드로 옮겨 시작 노드로 돌아오면 멈춘다. 쉼표 연산자는 앞의 이동을 수행한 뒤 뒤의 비교 결과를 조건으로 쓴다.
- !ptr / temp->link != ptr: 빈 리스트일 때만 세려 해 NULL 접근이 생기고, temp도 이동하지 않는다.
- !ptr / temp=temp->link, temp == ptr: 시작 조건이 반대이고, 시작 노드로 돌아왔을 때 오히려 반복을 계속하는 반대 조건이다.
- ptr / temp->link == ptr: temp를 옮기지 않아 노드 수를 셀 수 없다(노드가 하나면 무한 반복, 여럿이면 1을 반환).
시간 복잡도가 가장 낮은 연산은 포인터가 가리키는 노드의 다음 노드 삭제로 O(1)이다.
가리키는 노드의 링크를 다음 노드의 링크로 바꾸기만 하면 되므로 탐색이 필요 없다. 나머지 연산은 단순 연결리스트에서 리스트를 처음부터 따라가야 해 O(n)이다.
- 리스트 길이 출력: 길이를 따로 저장하지 않으면 모든 노드를 세어야 한다.
- 주어진 노드 앞에 새 노드 추가: 단순 연결리스트에는 앞 노드로 가는 링크가 없어 선행 노드를 처음부터 찾아야 한다.
- 마지막 노드의 데이터 출력: 꼬리 포인터가 없으면 끝까지 따라가야 한다.
| 메모리주소 | data | link |
|---|---|---|
| 2000 | A | 2020 |
| 2010 | B | 2030 |
| 2020 | C | 2010 |
| 2030 | D | 0 |
B를 삭제하면 C의 link가 2030으로 바뀐다.
link를 따라가면 A(2000) → C(2020) → B(2010) → D(2030) 순서이므로 B의 선행 노드는 C이다. C의 link를 B의 다음 노드 주소인 2030으로 바꾸면 B가 리스트에서 빠진다.
- A의 link → 2030: B뿐 아니라 C까지 리스트에서 빠진다.
- B의 link → 2010: 삭제할 노드의 링크를 바꾸는 것은 의미가 없고, C가 여전히 B를 가리킨다.
- B의 link → 2020: C가 여전히 B를 가리키며 C와 B 사이에 순환이 생긴다.