II-14 Dijkstra의 0 가중치와 구현별 실행시간 — 완전 초보자 Masterclass
먼저 이 문제의 정체부터
nonnegative는 positive와 다릅니다. 0은 허용되고 음수만 금지됩니다. 실행시간은 priority queue 구현과 graph 표현을 포함한 강의 모델을 그대로 확인해야 합니다.
통행료가 무료인 도로는 허용되지만 지나갈수록 돈을 돌려주는 음수 도로는 greedy 확정을 깨뜨립니다.
이 문항의 풀이 목표는 정답 label 암기가 아니라 다음 절차를 재현하는 것입니다. precondition과 runtime을 분리하고 runtime 식에서 |E| 항이 빠졌는지 확인합니다.
복기 시험지는 공식 답안지가 아니므로 문언과 selection rule이 충돌하면 그 사실을 표시하고 현재 강의 자료로 각 보기를 독립 검증합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 문제의 정체를 생활 언어로
nonnegative는 positive와 다릅니다. 0은 허용되고 음수만 금지됩니다. 실행시간은 priority queue 구현과 graph 표현을 포함한 강의 모델을 그대로 확인해야 합니다.
이 문항에서 가장 먼저 붙잡을 문장은 '가중치 0은 허용된다. 즉 nonnegative는 positive와 다르다.'입니다. 용어를 외우기 전에 이 문장이 어떤 상황을 말하는지 작은 예를 만들어 확인합니다.
이 절에서 꼭 기억할 것
- 가중치 0은 허용된다. 즉 nonnegative는 positive와 다르다.
- precondition과 runtime을 분리하고 runtime 식에서 |E| 항이 빠졌는지 확인합니다.
개념 2 · 반드시 알아야 하는 네 개의 뼈대
첫째, 가중치 0은 허용된다. 즉 nonnegative는 positive와 다르다. 둘째, cycle 발견은 Dijkstra의 중단 조건이 아니다.
셋째, 강의의 heap 구현 bound에는 |V|log|V|뿐 아니라 edge relaxations |E|가 들어간다. 넷째, 복기 판정은 \(\Theta(|V|\log|V|+|E|)\)Θ(|V|log|V|+|E|)라는 강의 모델을 따른다. 이 네 문장을 서로 섞지 않고 별도 체크박스로 기억해야 합니다.
이 절에서 꼭 기억할 것
- 가중치 0은 허용된다. 즉 nonnegative는 positive와 다르다.
- cycle 발견은 Dijkstra의 중단 조건이 아니다.
- 강의의 heap 구현 bound에는 |V|log|V|뿐 아니라 edge relaxations |E|가 들어간다.
- 복기 판정은 \(\Theta(|V|\log|V|+|E|)\)
Θ(|V|log|V|+|E|)라는 강의 모델을 따른다.
개념 3 · 강의 정의를 초보자 언어로 해체
최단 경로 문제는 출발점 s에서 각 정점까지의 현재 최선 후보 거리 dist를 계속 줄여 가는 문제다. Dijkstra는 '가장 가까워 보이는 정점은 이제 확정해도 된다'는 빠른 그리디(greedy) 판단을 사용하지만, 이는 뒤에서 음수 간선이 나타나 dist를 더 줄일 수 없다는 비음수 조건에 의존한다. Bellman-Ford는 그리디하게 확정하지 않고 모든 간선을 여러 번 훑으므로 음수 간선도 처리한다.
단일 출발점 최단 경로(SSSP, single-source shortest paths)는 출발점 s에서 도달 가능한 모든 정점 v까지의 shortest(s,v)를 구하는 문제다. 완화(Relaxation, Lockerung)는 간선 (u,v)에 대해 \(v.\text{dist} > u.\text{dist} + w(u,v)\)v.dist > u.dist + w(u,v)이면 v.dist := u.dist + w(u,v), v.pred := u로 갱신하는 연산이다. Dijkstra 알고리즘은 Q에서 dist가 가장 작은 정점 u를 꺼내고(EXTRACT-MIN) u에서 나가는 간선을 완화한다. Bellman-Ford 알고리즘은 |V|-1회 동안 모든 간선을 완화하고, 추가 검사에서도 완화 가능한 간선이 있으면 출발점에서 도달 가능한 음수 사이클을 보고한다.
수식으로 정확히 쓰기
핵심 규칙Dijkstra는 \(w(u,v) \ge 0\)w(u,v) ≥ 0을 요구하며, 강의의 Fibonacci 힙 구현에서 실행시간은 \(\Theta(|V| \log |V| + |E|)\)Θ(|V| log |V| + |E|)이다. Bellman-Ford는 \(\Theta(|V|\cdot |E|)\)Θ(|V|·|E|)이며 음수 간선을 허용한다. 도달 가능한 음수 사이클이 있으면 유한한 최단 경로 답이 없다.
이 절에서 꼭 기억할 것
- 그래프 방향이 중요하다. 방향 간선 (u,v)과 무방향 간선 {u,v}는 다르게 처리한다.
- 강의의 Dijkstra에서는 모든 간선이 \(w(u,v) \ge 0\)
w(u,v) ≥ 0을 만족해야 하며 0도 포함된다. - Bellman-Ford는 음수 간선을 허용하지만, 도달 가능한 음수 사이클이 있으면 유한한 최단 거리가 정의되지 않는다.
개념 4 · 성립 조건·불변식·경계 사례
Dijkstra의 핵심 불변식은 비음수 가중치 아래에서 u가 Q에서 추출될 때 \(u.\text{dist} = \text{shortest}(s,u)\)u.dist = shortest(s,u)가 된다는 것이다. Bellman-Ford는 충분히 반복하면 간선이 최대 |V|-1개인 모든 최단 단순 경로의 정보가 완화를 통해 전파된다. 출발점에서 도달 가능한 사이클의 총가중치가 음수이면 반복할수록 경로 비용을 끝없이 줄일 수 있으므로, 영향을 받는 정점에는 유한한 최단 경로 값이 없다.
가중치 0인 간선은 음이 아니므로 Dijkstra에서 허용된다. 양수 사이클이나 가중치 0인 사이클이 있다고 Dijkstra가 중단하지는 않으며 Q가 빌 때까지 정점을 처리한다. 도달 가능한 음수 사이클이 없는 음수 간선은 Bellman-Ford가 처리할 수 있다. 반면 무방향 그래프의 음수 간선은 양방향 표현에서 음수 2-사이클을 만들므로 Bellman-Ford는 음수 사이클을 검출하고 Dijkstra는 적용할 수 없다. 음수 가중치가 있는 DAG에는 위상 순서 기반 SSSP도 있지만 Dijkstra 자체가 DAG에만 제한되는 것은 아니다.
이 절에서 꼭 기억할 것
- 전제조건을 생략하지 않는다.
- 존재 명제와 모든 경우 명제를 구분한다.
- 강한 단어는 작은 반례로 우선 검사한다.
개념 5 · 실행시간과 비용을 읽는 법
강의의 Fibonacci 힙 기반 Dijkstra 실행시간은 \(\Theta(|V| \log |V| + |E|)\)Θ(|V| log |V| + |E|)이다. 구현에 따라 이진 힙은 흔히 \(O((|V|+|E|) \log |V|)\)O((|V|+|E|) log |V|), 행렬·배열 방식은 \(O(|V|^2)\)O(|V|²)이 될 수 있다. Bellman-Ford의 실행시간은 \(\Theta(|V|\cdot |E|)\)Θ(|V|·|E|)이다. 두 알고리즘 모두 정점마다 dist와 pred를 저장하므로 그래프 표현 외에 \(O(|V|)\)O(|V|)의 추가 정점 상태 메모리를 사용한다.
O는 upper bound이고 Θ는 tight bound입니다. 자료구조 연산 비용은 ADT 이름만이 아니라 구현과 유지하는 보조 정보에 따라 달라질 수 있습니다.
이 절에서 꼭 기억할 것
- O와 Θ를 같은 뜻으로 읽지 않는다.
- 구현 의존성을 확인한다.
- 필요 없는 runtime 주장도 억지로 만들지 않는다.
개념 6 · 정확히 두 개 선택(exactly two) 판정법
선택지를 서로 비교해 '가장 그럴듯한 두 개'를 고르지 않습니다. A부터 D까지 각각 독립적인 참·거짓 명제로 바꾸고 근거 또는 반례를 붙인 뒤 참의 개수를 셉니다.
현재 복기 데이터에서 판정된 정답 표시는 B, D입니다. 정답 수와 섹션 규칙이 충돌하는 문항은 억지로 두 개를 만들지 않고 복기 문언 누락 가능성을 명시합니다.
수식으로 정확히 쓰기
핵심 규칙선택 규칙: 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
핵심 규칙검증된 선택지: B, D
이 절에서 꼭 기억할 것
- Dijkstra의 전제조건과 실행시간은 구현에 민감합니다. 가중치 0은 허용하지만 음수는 허용하지 않으며, 일반적으로 |E| 항이 필요합니다.
- \(w\ge 0\)
w≥0은 0을 허용합니다. 강의 실행 시간은 \(\Theta(V \log V+E)\)Θ(V log V+E)입니다. 순환에서 중단하거나 \(O(V \log V)\)O(V log V)만 제시하는 선지는 위험 신호입니다.
1. 시험장에서 따라 할 풀이 순서
선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
Dijkstra의 0 가중치와 구현별 실행시간
가중치 0은 허용된다. 즉 nonnegative는 positive와 다르다. | cycle 발견은 Dijkstra의 중단 조건이 아니다. | 강의의 heap 구현 bound에는 |V|log|V|뿐 아니라 edge relaxations |E|가 들어간다.
선택지 \(A =\)A =거짓
선택 규칙을 먼저 적는다
이 문항의 규칙은 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))입니다. 마지막에 참 개수를 반드시 재검산합니다.핵심 규칙선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))문장을 쉬운 한국어로 다시 쓴다
Dijkstra 알고리즘에 대한 다음 설명 중 정확히 두 개를 고르시오.
핵심 규칙Dijkstra의 0 가중치와 구현별 실행시간
핵심 도구를 종이에 꺼낸다
precondition과 runtime을 분리하고 runtime 식에서 |E| 항이 빠졌는지 확인합니다.
핵심 규칙가중치 0은 허용된다. 즉 nonnegative는 positive와 다르다. | cycle 발견은 Dijkstra의 중단 조건이 아니다. | 강의의 heap 구현 bound에는 |V|log|V|뿐 아니라 edge relaxations |E|가 들어간다.
선택지 A를 독립 판정한다
Dijkstra는 순환 검출 알고리즘이 아닙니다. 강의 의사코드의 반복 조건은 Q가 비어 있지 않은 동안이며, 각 단계에서 최소값 추출(EXTRACT-MIN) 뒤 나가는 간선을 완화(relax)합니다. 음수가 아닌 순환이 있어도 순환 때문에 중단하지 않습니다.
\[선택지 A = 거짓\]선택지 A = 거짓선택지 B를 독립 판정한다
강의 전제는 \(w(u,v) \ge 0\)
w(u,v) ≥ 0입니다. '크거나 같다'에는 0이 포함되므로 가중치 0인 간선은 Dijkstra의 강의 전제를 어기지 않습니다. 함정은 비음수(nonnegative)를 양수(positive)로 잘못 읽는 것입니다.\[선택지 B = 참\]선택지 B = 참선택지 C를 독립 판정한다
강의는 Fibonacci 힙 구현에서 \(\Theta(|V| \log |V| + |E|)\)
Θ(|V| log |V| + |E|)를 제시합니다. 관련된 모든 나가는 간선을 완화해야 하므로 일반 그래프에서는 |E| 항을 없앨 수 없습니다. 밀집 그래프(dense graph)에서는 |E|가 |V| log |V|보다 훨씬 커질 수 있습니다.\[선택지 C = 거짓\]선택지 C = 거짓선택지 D를 독립 판정한다
강의 슬라이드가 Dijkstra 의사코드와 함께 이 실행시간을 명시합니다. |V| log |V| 항은 우선순위 큐 연산, |E| 항은 간선 완화 처리에 해당합니다. 다른 구현에서는 상한이 달라질 수 있으므로 이 선택지는 강의 관례에 맞추어 읽어야 합니다.
\[선택지 D = 참\]선택지 D = 참정답 수와 애매성을 재검산한다
참으로 판정된 선택지는 B, D입니다. 복기 섹션 규칙과 수가 다르면 원문 누락 가능성을 기록하고 거짓을 참으로 조작하지 않습니다.
\[검증된 정답 = B, D\]검증된 정답 = B, D
2. 이 문제를 실제로 끝까지 풀기
nonnegative는 positive와 다릅니다. 0은 허용되고 음수만 금지됩니다. 실행시간은 priority queue 구현과 graph 표현을 포함한 강의 모델을 그대로 확인해야 합니다.
풀이를 시작할 때 다음 네 사실을 먼저 적습니다. (1) 가중치 0은 허용된다. 즉 nonnegative는 positive와 다르다. (2) cycle 발견은 Dijkstra의 중단 조건이 아니다. (3) 강의의 heap 구현 bound에는 |V|log|V|뿐 아니라 edge relaxations |E|가 들어간다. (4) 복기 판정은 \(\Theta(|V|\log|V|+|E|)\)Θ(|V|log|V|+|E|)라는 강의 모델을 따른다.
선택지 A는 거짓입니다. Dijkstra는 순환 검출 알고리즘이 아닙니다. 강의 의사코드의 반복 조건은 Q가 비어 있지 않은 동안이며, 각 단계에서 최소값 추출(EXTRACT-MIN) 뒤 나가는 간선을 완화(relax)합니다. 음수가 아닌 순환이 있어도 순환 때문에 중단하지 않습니다. 가장 작은 확인 예는 \(s\to a\)s→a와 \(a\to s\)a→s의 가중치가 각각 1인 방향 순환은 Dijkstra를 중단시키지 않으며, 알고리즘은 dist 순서로 정점을 확정합니다.
선택지 B는 참입니다. 강의 전제는 \(w(u,v) \ge 0\)w(u,v) ≥ 0입니다. '크거나 같다'에는 0이 포함되므로 가중치 0인 간선은 Dijkstra의 강의 전제를 어기지 않습니다. 함정은 비음수(nonnegative)를 양수(positive)로 잘못 읽는 것입니다.
선택지 C는 거짓입니다. 강의는 Fibonacci 힙 구현에서 \(\Theta(|V| \log |V| + |E|)\)Θ(|V| log |V| + |E|)를 제시합니다. 관련된 모든 나가는 간선을 완화해야 하므로 일반 그래프에서는 |E| 항을 없앨 수 없습니다. 밀집 그래프(dense graph)에서는 |E|가 |V| log |V|보다 훨씬 커질 수 있습니다. 가장 작은 확인 예는 |\(E|=\Theta(|V|²)\)E|=Θ(|V|²)인 완전 방향 그래프에서 Dijkstra는 간선을 확인·완화해야 하므로 \(O(|V| \log |V|)\)O(|V| log |V|)만으로는 너무 작습니다.
선택지 D는 참입니다. 강의 슬라이드가 Dijkstra 의사코드와 함께 이 실행시간을 명시합니다. |V| log |V| 항은 우선순위 큐 연산, |E| 항은 간선 완화 처리에 해당합니다. 다른 구현에서는 상한이 달라질 수 있으므로 이 선택지는 강의 관례에 맞추어 읽어야 합니다.
따라서 현재 문언에서 참으로 검증된 선택지는 B, D입니다. 선택지는 서로 상대평가하지 않고 각 문장을 정의·전제·반례로 독립 검증했습니다.
시험장에서 쓸 압축 절차는 다음과 같습니다. precondition과 runtime을 분리하고 runtime 식에서 |E| 항이 빠졌는지 확인합니다. 시간이 부족해도 '항상(always)', '오직(only)', '모든(every)' 같은 강한 단어와 전제조건, O와 Θ를 먼저 확인하면 대표 함정을 피할 수 있습니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A거짓
Dijkstra는 순환 검출 알고리즘이 아닙니다. 강의 의사코드의 반복 조건은 Q가 비어 있지 않은 동안이며, 각 단계에서 최소값 추출(EXTRACT-MIN) 뒤 나가는 간선을 완화(relax)합니다. 음수가 아닌 순환이 있어도 순환 때문에 중단하지 않습니다.
빠른 확인법: \(s\to a\)
s→a와 \(a\to s\)a→s의 가중치가 각각 1인 방향 순환은 Dijkstra를 중단시키지 않으며, 알고리즘은 dist 순서로 정점을 확정합니다. -
B참 — 정답 후보
강의 전제는 \(w(u,v) \ge 0\)
w(u,v) ≥ 0입니다. '크거나 같다'에는 0이 포함되므로 가중치 0인 간선은 Dijkstra의 강의 전제를 어기지 않습니다. 함정은 비음수(nonnegative)를 양수(positive)로 잘못 읽는 것입니다.빠른 확인법: 간선 가중치는 0이어도 된다.
-
C거짓
강의는 Fibonacci 힙 구현에서 \(\Theta(|V| \log |V| + |E|)\)
Θ(|V| log |V| + |E|)를 제시합니다. 관련된 모든 나가는 간선을 완화해야 하므로 일반 그래프에서는 |E| 항을 없앨 수 없습니다. 밀집 그래프(dense graph)에서는 |E|가 |V| log |V|보다 훨씬 커질 수 있습니다.빠른 확인법: |\(E|=\Theta(|V|²)\)
E|=Θ(|V|²)인 완전 방향 그래프에서 Dijkstra는 간선을 확인·완화해야 하므로 \(O(|V| \log |V|)\)O(|V| log |V|)만으로는 너무 작습니다. -
D참 — 정답 후보
강의 슬라이드가 Dijkstra 의사코드와 함께 이 실행시간을 명시합니다. |V| log |V| 항은 우선순위 큐 연산, |E| 항은 간선 완화 처리에 해당합니다. 다른 구현에서는 상한이 달라질 수 있으므로 이 선택지는 강의 관례에 맞추어 읽어야 합니다.
빠른 확인법: Dijkstra의 실행시간은 \(\Theta(|V| \log |V| + |E|)\)
Θ(|V| log |V| + |E|)이다.
4. 초보자가 가장 자주 틀리는 이유
- Dijkstra의 전제조건과 실행시간은 구현에 민감합니다. 가중치 0은 허용하지만 음수는 허용하지 않으며, 일반적으로 |E| 항이 필요합니다.
- exactly-two라는 이유만으로 근거 없이 두 선택지를 맞다고 만든다.
- 선택지의 절반만 맞는데 결합 문장 전체를 참으로 판정한다.
- always, only, every 같은 강한 단어를 놓친다.
- 정의와 구현, 전제조건과 결론, upper bound와 tight bound를 섞는다.
- 작은 예 하나로 거짓은 깰 수 있지만 참인 보편 명제를 증명했다고 착각한다.
- 복기 시험지가 공식 원문·공식 답안이라는 전제로 애매성을 숨긴다.
- 용어를 암기한 소리만 따라가고 실제 상태나 한 단계 실행을 그리지 않는다.
5. 시험 답안 템플릿
precondition과 runtime을 분리하고 runtime 식에서 |E| 항이 빠졌는지 확인합니다. 각 선택지를 정의와 전제에 따라 독립 판정하면 참인 label은 B, D이다. 핵심 근거: 가중치 0은 허용된다. 즉 nonnegative는 positive와 다르다. cycle 발견은 Dijkstra의 중단 조건이 아니다. 강의의 heap 구현 bound에는 |V|log|V|뿐 아니라 edge relaxations |E|가 들어간다. 복기 판정은 \(\Theta(|V|\log|V|+|E|)\)Θ(|V|log|V|+|E|)라는 강의 모델을 따른다.
6. 스스로 이해했는지 확인
II-14의 주제를 한 문장으로 설명하면?
정답: nonnegative는 positive와 다릅니다. 0은 허용되고 음수만 금지됩니다. 실행시간은 priority queue 구현과 graph 표현을 포함한 강의 모델을 그대로 확인해야 합니다.
이 문제에서 가장 먼저 꺼낼 판정법은?
정답: precondition과 runtime을 분리하고 runtime 식에서 |E| 항이 빠졌는지 확인합니다.
핵심 사실 네 가지 중 첫 번째는?
정답: 가중치 0은 허용된다. 즉 nonnegative는 positive와 다르다.
핵심 사실 네 가지 중 두 번째는?
정답: cycle 발견은 Dijkstra의 중단 조건이 아니다.
가장 위험한 함정은?
정답: Dijkstra의 전제조건과 실행시간은 구현에 민감합니다. 가중치 0은 허용하지만 음수는 허용하지 않으며, 일반적으로 |E| 항이 필요합니다.
정답 label은?
정답: B, D
Dijkstra의 정확성 불변식(invariant)을 한 문장으로 말하라.
정답: 모든 간선 가중치가 음이 아닐 때 Q에서 EXTRACT-MIN된 정점 u는 그 순간 \(u.\text{dist} = \text{shortest}(s,u)\)u.dist = shortest(s,u)가 되어 최종 확정된다.
Bellman-Ford가 |V|-1회 반복하는 이유는 무엇인가?
정답: 도달 가능한 음수 사이클이 없으면 최단 단순 경로는 정점을 반복할 필요가 없어 간선 수가 최대 |V|-1개이고, 각 반복이 경로의 다음 간선 효과를 전파할 수 있기 때문이다.
근거 자료
AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice II-14
복기된 문언과 선택지; 공식 답안지가 아님AuD Gedächtnisprotokoll SoSe 2025.md· MC section lines 136-146
정확히 두 개 선택 규칙을 포함한 2025년 여름학기 II-13·II-14 복기 문구.Vorlesung\06GraphAlgorithms.pdf· pp. 127-130
최단 부분 경로 성질, 단일 출발점 최단 경로 알고리즘 개요, 완화 규칙, Bellman-Ford 실행 시간과 음수 순환 검사.Vorlesung\06GraphAlgorithms.pdf· pp. 130-141
Bellman-Ford는 모든 간선을 |V|-1회 완화한 뒤 도달 가능한 음수 순환을 감지하며, 실행 시간은 \(\Theta(|V||E|)\)Θ(|V||E|)입니다.Vorlesung\06GraphAlgorithms__moodle_2026-06-16.pdf· pp. 152-174
현재 Moodle 자료는 Dijkstra의 전제 \(w(u,v) \ge 0, \text{Fibonacci}\)w(u,v) ≥ 0, Fibonacci힙을 사용할 때의 실행 시간 \(\Theta(|V| \log |V|+|E|)\)Θ(|V| log |V|+|E|), 정확성 불변식, 음수 간선 반례와 무방향 그래프 관례를 제시합니다.