토픽 89 / 92·비교표
경로 탐색과 네트워크 플로우
A* vs Dijkstra vs Greedy
| 항목 | A* | Dijkstra | Greedy Best-First |
|---|
| 평가 | f = g + h (실제+추정) | g만 (실제 비용) | h만 (추정 비용) |
| 최적 보장 | O (admissible h) | O | X |
| 속도 | 빠름 (방향성 탐색) | 느림 (균등 탐색) | 가장 빠름 |
| 적용 | 게임 경로, 네비게이션 | 최단 경로 (범용) | 빠른 근사 |
이분 매칭 vs 일반 매칭
| 항목 | 이분 매칭 | 일반 매칭 |
|---|
| 그래프 | 이분 그래프 | 일반 그래프 |
| 알고리즘 | 증가 경로 (Hopcroft-Karp) | Blossom (Edmonds) |
| 시간 | O(E * sqrt(V)) | O(V^3) |
| 적용 | 작업 할당 | 일반 매칭 문제 |
Ford-Fulkerson vs Edmonds-Karp vs Dinic (최대 유량)
| 구분 | Ford-Fulkerson | Edmonds-Karp | Dinic |
|---|
| 경로 탐색 | DFS | BFS | BFS+DFS |
| 시간 복잡도 | O(E × max_flow) | O(VE²) | O(V²E) |
| 핵심 기법 | 증가 경로 | 최단 증가 경로 | 레벨 그래프+차단 유량 |
| 종료 보장 | 정수만 | 항상 | 항상 |
| 실용 성능 | 보통 | 좋음 | 매우 좋음 |
Tarjan vs Kosaraju (SCC)
| 항목 | Tarjan | Kosaraju |
|---|
| 순회 횟수 | 1회 | 2회 |
| 시간 | O(V+E) | O(V+E) |
| 구현 | 복잡 (lowlink) | 단순 (역그래프) |
| 적용 | 실무 최적 | 교육/이해 용이 |