II-10 트리 조건·위상정렬·Heap·DFS cross edge — 완전 초보자 Masterclass
먼저 이 문제의 정체부터
한 문항에 서로 다른 네 주제가 섞였으므로 공통 느낌으로 풀면 안 됩니다. 각 선택지 옆에 graph theorem, algorithm termination, heap invariant, DFS edge class를 적어 독립 판정합니다.
한 시험지에 교통법·요리·수학·음악 문제가 섞인 셈이므로 과목별 규칙을 꺼내야 합니다.
이 문항의 풀이 목표는 정답 label 암기가 아니라 다음 절차를 재현하는 것입니다. 각 문장의 대상 invariant를 식별하고 작은 counterexample 또는 정리를 하나씩 적용합니다.
복기 시험지는 공식 답안지가 아니므로 문언과 selection rule이 충돌하면 그 사실을 표시하고 현재 강의 자료로 각 보기를 독립 검증합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 문제의 정체를 생활 언어로
한 문항에 서로 다른 네 주제가 섞였으므로 공통 느낌으로 풀면 안 됩니다. 각 선택지 옆에 graph theorem, algorithm termination, heap invariant, DFS edge class를 적어 독립 판정합니다.
이 문항에서 가장 먼저 붙잡을 문장은 '정점 n개와 간선 n−1개를 가진 연결된 무방향 그래프는 트리이다.'입니다. 용어를 외우기 전에 이 문장이 어떤 상황을 말하는지 작은 예를 만들어 확인합니다.
이 절에서 꼭 기억할 것
- 정점 n개와 간선 n−1개를 가진 연결된 무방향 그래프는 트리이다.
- 각 문장의 대상 invariant를 식별하고 작은 counterexample 또는 정리를 하나씩 적용합니다.
개념 2 · 반드시 알아야 하는 네 개의 뼈대
첫째, 정점 n개와 간선 n−1개를 가진 연결된 무방향 그래프는 트리이다. 둘째, cycle이 있는 directed graph에도 topological-sort 알고리즘은 종료하며 성공 순서를 만들지 못할 뿐이다.
셋째, min-heap traversal은 전체 sorted order를 보장하지 않는다. 넷째, directed DAG의 DFS에는 cross edge가 생길 수 있다. 이 네 문장을 서로 섞지 않고 별도 체크박스로 기억해야 합니다.
이 절에서 꼭 기억할 것
- 정점 n개와 간선 n−1개를 가진 연결된 무방향 그래프는 트리이다.
- cycle이 있는 directed graph에도 topological-sort 알고리즘은 종료하며 성공 순서를 만들지 못할 뿐이다.
- min-heap traversal은 전체 sorted order를 보장하지 않는다.
- directed DAG의 DFS에는 cross edge가 생길 수 있다.
개념 3 · 강의 정의를 초보자 언어로 해체
BFS는 물결처럼 가까운 층부터 퍼지고, DFS는 한 갈래를 끝까지 따라갔다 돌아온다. 위상 정렬(topological sorting)은 DAG에서 선후관계를 한 줄로 세우는 작업이다.
방향 그래프(directed graph)는 G=(V,E), E ⊆ V × V이다. 무방향 그래프(undirected graph)는 간선 관계가 대칭이다. BFS(Breitensuche)는 FIFO 큐를 사용하고, DFS(Tiefensuche)는 재귀·스택을 사용한다. DAG는 방향 비순환 그래프(directed acyclic graph)이다.
수식으로 정확히 쓰기
핵심 규칙인접 리스트에서 BFS·DFS·위상 정렬·Kosaraju는 \(O(|V|+|E|)\)O(|V|+|E|)이다. 위상 순서에서는 모든 간선 (u,v)에 대해 u가 v보다 앞에 와야 한다.
이 절에서 꼭 기억할 것
- 유한 집합(finite set)
- 순서쌍과 대칭 관계의 차이
- 큐와 스택
개념 4 · 성립 조건·불변식·경계 사례
BFS 큐는 감소하지 않는 거리(dist) 순서로 정점을 처리한다. DFS의 회색(GRAY) 정점은 재귀 스택에 있으며, 역방향 간선(back edge)은 방향 사이클의 존재를 뜻한다. 무방향 DFS에서는 강의 규약에 따라 트리 간선과 역방향 간선만 남는다.
유한 그래프에는 무한한 간선 집합이 있을 수 없다. \(E = V\)E = V × V는 완전 관계를 뜻한다. BFS의 최단 경로는 가중 최단 경로가 아니다. 사이클이 있는 방향 그래프에는 위상 순서가 없지만, 올바른 알고리즘은 그래도 종료하거나 실패를 보고한다.
이 절에서 꼭 기억할 것
- 전제조건을 생략하지 않는다.
- 존재 명제와 모든 경우 명제를 구분한다.
- 강한 단어는 작은 반례로 우선 검사한다.
개념 5 · 실행시간과 비용을 읽는 법
인접 행렬은 \(\Theta(|V|^2)\)Θ(|V|²) 공간을 사용하고 인접 리스트는 \(\Theta(|V|+|E|)\)Θ(|V|+|E|) 공간을 사용한다. 인접 리스트에서 BFS, DFS, DFS 기반 위상 정렬, Kosaraju는 \(O(|V|+|E|)\)O(|V|+|E|)에 실행된다.
O는 upper bound이고 Θ는 tight bound입니다. 자료구조 연산 비용은 ADT 이름만이 아니라 구현과 유지하는 보조 정보에 따라 달라질 수 있습니다.
이 절에서 꼭 기억할 것
- O와 Θ를 같은 뜻으로 읽지 않는다.
- 구현 의존성을 확인한다.
- 필요 없는 runtime 주장도 억지로 만들지 않는다.
개념 6 · 정확히 두 개 선택(exactly two) 판정법
선택지를 서로 비교해 '가장 그럴듯한 두 개'를 고르지 않습니다. A부터 D까지 각각 독립적인 참·거짓 명제로 바꾸고 근거 또는 반례를 붙인 뒤 참의 개수를 셉니다.
현재 복기 데이터에서 판정된 정답 표시는 A, D입니다. 정답 수와 섹션 규칙이 충돌하는 문항은 억지로 두 개를 만들지 않고 복기 문언 누락 가능성을 명시합니다.
수식으로 정확히 쓰기
핵심 규칙선택 규칙: 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
핵심 규칙검증된 선택지: A, D
이 절에서 꼭 기억할 것
- 위상 순서가 없다는 사실을 비종료와 혼동하지 말고, 힙의 국소 순서를 정렬된 순회와 혼동하지 마세요.
- 명제가 그래프 조건, 알고리즘 동작, 자료구조 불변식 중 무엇을 말하는지 먼저 구분하세요.
1. 시험장에서 따라 할 풀이 순서
선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
트리 조건·위상정렬·Heap·DFS cross edge
정점 n개와 간선 n−1개를 가진 연결된 무방향 그래프는 트리이다. | cycle이 있는 directed graph에도 topological-sort 알고리즘은 종료하며 성공 순서를 만들지 못할 뿐이다. | min-heap traversal은 전체 sorted order를 보장하지 않는다.
선택지 \(A =\)A =참
선택 규칙을 먼저 적는다
이 문항의 규칙은 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))입니다. 마지막에 참 개수를 반드시 재검산합니다.핵심 규칙선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))문장을 쉬운 한국어로 다시 쓴다
그래프 알고리즘 및 관련 자료구조 설명 중 정확히 두 개를 고르시오.
핵심 규칙트리 조건·위상정렬·Heap·DFS cross edge
핵심 도구를 종이에 꺼낸다
각 문장의 대상 invariant를 식별하고 작은 counterexample 또는 정리를 하나씩 적용합니다.
핵심 규칙정점 n개와 간선 n−1개를 가진 연결된 무방향 그래프는 트리이다. | cycle이 있는 directed graph에도 topological-sort 알고리즘은 종료하며 성공 순서를 만들지 못할 뿐이다. | min-heap traversal은 전체 sorted order를 보장하지 않는다.
선택지 A를 독립 판정한다
강의의 그래프 트리(graph tree) 정의와 표준 성질에 따르면, 연결된 무방향 그래프(connected undirected graph)에 간선이 n-1개 있으면 트리임이 보장됩니다.
\[선택지 A = 참\]선택지 A = 참선택지 B를 독립 판정한다
순환(cycle)이 있으면 위상 순서(topological order)는 존재하지 않지만 알고리즘이 무한히 실행되는 것은 아닙니다. DFS 기반 절차는 유한하게 끝나며 역방향 간선(back edge)을 검출할 수 있고, Kahn 방식은 진입차수 0인 정점이 없으면 실패를 보고합니다.
\[선택지 B = 거짓\]선택지 B = 거짓선택지 C를 독립 판정한다
힙 성질(heap property)은 부모·자식 사이의 국소 순서만 보장합니다. 서로 다른 부분 트리 사이의 전체 정렬 순서는 보장하지 않으며, 정렬하려면 최소·최댓값 반복 추출(extract-min/max) 같은 연산이 필요합니다.
\[선택지 C = 거짓\]선택지 C = 거짓선택지 D를 독립 판정한다
방향 비순환 그래프(DAG)가 금지하는 것은 방향 순환을 만드는 역방향 간선(back edge)입니다. 이미 탐색이 끝난 다른 가지로 가는 교차 간선(cross edge)은 DFS 순서에 따라 생길 수 있습니다.
\[선택지 D = 참\]선택지 D = 참정답 수와 애매성을 재검산한다
참으로 판정된 선택지는 A, D입니다. 복기 섹션 규칙과 수가 다르면 원문 누락 가능성을 기록하고 거짓을 참으로 조작하지 않습니다.
\[검증된 정답 = A, D\]검증된 정답 = A, D
2. 이 문제를 실제로 끝까지 풀기
한 문항에 서로 다른 네 주제가 섞였으므로 공통 느낌으로 풀면 안 됩니다. 각 선택지 옆에 graph theorem, algorithm termination, heap invariant, DFS edge class를 적어 독립 판정합니다.
풀이를 시작할 때 다음 네 사실을 먼저 적습니다. (1) 정점 n개와 간선 n−1개를 가진 연결된 무방향 그래프는 트리이다. (2) cycle이 있는 directed graph에도 topological-sort 알고리즘은 종료하며 성공 순서를 만들지 못할 뿐이다. (3) min-heap traversal은 전체 sorted order를 보장하지 않는다. (4) directed DAG의 DFS에는 cross edge가 생길 수 있다.
선택지 A는 참입니다. 강의의 그래프 트리(graph tree) 정의와 표준 성질에 따르면, 연결된 무방향 그래프(connected undirected graph)에 간선이 n-1개 있으면 트리임이 보장됩니다.
선택지 B는 거짓입니다. 순환(cycle)이 있으면 위상 순서(topological order)는 존재하지 않지만 알고리즘이 무한히 실행되는 것은 아닙니다. DFS 기반 절차는 유한하게 끝나며 역방향 간선(back edge)을 검출할 수 있고, Kahn 방식은 진입차수 0인 정점이 없으면 실패를 보고합니다. 가장 작은 확인 예는 \(u\to v\)u→v와 \(v\to u\)v→u가 함께 있으면 위상 순서는 없지만 DFS는 종료하며 역방향 간선을 감지합니다.
선택지 C는 거짓입니다. 힙 성질(heap property)은 부모·자식 사이의 국소 순서만 보장합니다. 서로 다른 부분 트리 사이의 전체 정렬 순서는 보장하지 않으며, 정렬하려면 최소·최댓값 반복 추출(extract-min/max) 같은 연산이 필요합니다. 가장 작은 확인 예는 루트가 1이고 자식이 2와 3이며 2 아래에 4와 5가 있는 최소 힙의 전위 순회는 1,2,4,5,3입니다.
선택지 D는 참입니다. 방향 비순환 그래프(DAG)가 금지하는 것은 방향 순환을 만드는 역방향 간선(back edge)입니다. 이미 탐색이 끝난 다른 가지로 가는 교차 간선(cross edge)은 DFS 순서에 따라 생길 수 있습니다.
따라서 현재 문언에서 참으로 검증된 선택지는 A, D입니다. 선택지는 서로 상대평가하지 않고 각 문장을 정의·전제·반례로 독립 검증했습니다.
시험장에서 쓸 압축 절차는 다음과 같습니다. 각 문장의 대상 invariant를 식별하고 작은 counterexample 또는 정리를 하나씩 적용합니다. 시간이 부족해도 '항상(always)', '오직(only)', '모든(every)' 같은 강한 단어와 전제조건, O와 Θ를 먼저 확인하면 대표 함정을 피할 수 있습니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A참 — 정답 후보
강의의 그래프 트리(graph tree) 정의와 표준 성질에 따르면, 연결된 무방향 그래프(connected undirected graph)에 간선이 n-1개 있으면 트리임이 보장됩니다.
빠른 확인법: 연결된 무방향 그래프가 n개의 정점과 n-1개의 간선을 가지면 트리(Baum)다.
-
B거짓
순환(cycle)이 있으면 위상 순서(topological order)는 존재하지 않지만 알고리즘이 무한히 실행되는 것은 아닙니다. DFS 기반 절차는 유한하게 끝나며 역방향 간선(back edge)을 검출할 수 있고, Kahn 방식은 진입차수 0인 정점이 없으면 실패를 보고합니다.
빠른 확인법: \(u\to v\)
u→v와 \(v\to u\)v→u가 함께 있으면 위상 순서는 없지만 DFS는 종료하며 역방향 간선을 감지합니다. -
C거짓
힙 성질(heap property)은 부모·자식 사이의 국소 순서만 보장합니다. 서로 다른 부분 트리 사이의 전체 정렬 순서는 보장하지 않으며, 정렬하려면 최소·최댓값 반복 추출(extract-min/max) 같은 연산이 필요합니다.
빠른 확인법: 루트가 1이고 자식이 2와 3이며 2 아래에 4와 5가 있는 최소 힙의 전위 순회는 1,2,4,5,3입니다.
-
D참 — 정답 후보
방향 비순환 그래프(DAG)가 금지하는 것은 방향 순환을 만드는 역방향 간선(back edge)입니다. 이미 탐색이 끝난 다른 가지로 가는 교차 간선(cross edge)은 DFS 순서에 따라 생길 수 있습니다.
빠른 확인법: DAG에서 DFS를 수행할 때 Kreuzkanten(cross edges)이 생길 수 있다.
4. 초보자가 가장 자주 틀리는 이유
- 위상 순서가 없다는 사실을 비종료와 혼동하지 말고, 힙의 국소 순서를 정렬된 순회와 혼동하지 마세요.
- exactly-two라는 이유만으로 근거 없이 두 선택지를 맞다고 만든다.
- 선택지의 절반만 맞는데 결합 문장 전체를 참으로 판정한다.
- always, only, every 같은 강한 단어를 놓친다.
- 정의와 구현, 전제조건과 결론, upper bound와 tight bound를 섞는다.
- 작은 예 하나로 거짓은 깰 수 있지만 참인 보편 명제를 증명했다고 착각한다.
- 복기 시험지가 공식 원문·공식 답안이라는 전제로 애매성을 숨긴다.
- 용어를 암기한 소리만 따라가고 실제 상태나 한 단계 실행을 그리지 않는다.
5. 시험 답안 템플릿
각 문장의 대상 invariant를 식별하고 작은 counterexample 또는 정리를 하나씩 적용합니다. 각 선택지를 정의와 전제에 따라 독립 판정하면 참인 label은 A, D이다. 핵심 근거: 정점 n개와 간선 n−1개를 가진 연결된 무방향 그래프는 트리이다. cycle이 있는 directed graph에도 topological-sort 알고리즘은 종료하며 성공 순서를 만들지 못할 뿐이다. min-heap traversal은 전체 sorted order를 보장하지 않는다. directed DAG의 DFS에는 cross edge가 생길 수 있다.
6. 스스로 이해했는지 확인
II-10의 주제를 한 문장으로 설명하면?
정답: 한 문항에 서로 다른 네 주제가 섞였으므로 공통 느낌으로 풀면 안 됩니다. 각 선택지 옆에 graph theorem, algorithm termination, heap invariant, DFS edge class를 적어 독립 판정합니다.
이 문제에서 가장 먼저 꺼낼 판정법은?
정답: 각 문장의 대상 invariant를 식별하고 작은 counterexample 또는 정리를 하나씩 적용합니다.
핵심 사실 네 가지 중 첫 번째는?
정답: 정점 n개와 간선 n−1개를 가진 연결된 무방향 그래프는 트리이다.
핵심 사실 네 가지 중 두 번째는?
정답: cycle이 있는 directed graph에도 topological-sort 알고리즘은 종료하며 성공 순서를 만들지 못할 뿐이다.
가장 위험한 함정은?
정답: 위상 순서가 없다는 사실을 비종료와 혼동하지 말고, 힙의 국소 순서를 정렬된 순회와 혼동하지 마세요.
정답 label은?
정답: A, D
방향 그래프(directed graph)와 무방향 그래프(undirected graph)의 E 조건을 각각 말하라.
정답: 방향 그래프는 E ⊆ V × V이고 대칭성이 필요 없다. 무방향 그래프는 E ⊆ V × V에 대칭성을 더한다.
BFS에서 흰색(WHITE), 회색(GRAY), 검은색(BLACK), dist, pred, Q의 의미를 말하라.
정답: WHITE는 미발견, GRAY는 발견되어 큐에 있음, BLACK은 처리 완료 상태다. dist는 간선 수 거리(edge-count distance), pred는 처음 발견시킨 이전 정점(predecessor), Q는 FIFO 큐다.
근거 자료
AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice II-10
복기된 문언과 선택지; 공식 답안지가 아님AuD Gedächtnisprotokoll SoSe 2025.md· MC section II, questions 9-11
2025년 여름학기 복기 문구와 배점, 그리고 정확히 두 개 선택 규칙.Vorlesung\06GraphAlgorithms.pdf· pp. 3-6
유한 방향·무방향 그래프의 정의, E ⊆ V × V, 무방향 대칭성, 경로와 연결성.Vorlesung\06GraphAlgorithms__moodle_2026-06-16.pdf· pp. 3-6
Moodle 미러가 현재 강의의 동일한 그래프 정의 관례를 확인해 줍니다.Vorlesung\06GraphAlgorithms.pdf· pp. 9, 14
인접 행렬·인접 리스트 표현과 각각의 공간 비용.