칸의 알고리즘으로 위상 정렬
다른 작업에 의존하는 작업의 순서를 정합니다
칸의 알고리즘으로 위상 정렬은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
위상 순서란
위상 순서는 방향 그래프의 모든 정점을 나열하되, 각 간선이 앞쪽 정점에서 뒤쪽 정점으로 향하도록 만든 순서입니다. 어떤 작업을 먼저 해야 그 작업이 필요한 다음 작업을 할 수 있는지 생각해 보십시오.
DAG만 가능합니다
이 방법은 방향 비순환 그래프인 DAG에서만 작동합니다. 사이클이 하나라도 있으면 모든 의존성을 만족하는 유효한 순서를 만들 수 없습니다.
진입 차수의 개념
칸 알고리즘은 진입 차수, 즉 한 정점으로 들어오는 간선의 수를 이용합니다. 진입 차수가 0인 정점에는 아직 충족하지 못한 의존성이 없습니다.
모든 진입 차수 세기
첫 번째 단계에서는 모든 간선을 살펴보며 각 정점이 도착점이 되는 횟수를 셉니다. 그러면 각 정점의 진입 차수를 얻을 수 있습니다.
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1준비된 큐 초기화
진입 차수가 0인 모든 정점은 바로 처리할 수 있으므로, 시작할 때 모두 큐에 넣습니다.
from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)정점 하나 처리하기
처리할 수 있는 정점을 하나 `pop`하고 순서에 append합니다. 그 정점에는 아직 충족하지 못한 선행 조건이 없으므로 이제 안전하게 처리할 수 있습니다.
u = q.popleft()
order.append(u)인접 정점 해제하기
각 인접 정점의 진입 차수를 1씩 줄입니다. 인접 정점의 값이 0이 되는 순간 처리할 수 있는 상태가 되어 큐에 들어갑니다.
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)큐가 빌 때까지 반복하기
큐가 빌 때까지 계속 `pop`하고 다음 정점들을 처리할 수 있게 하십시오. 모든 정점이 배치될 때까지 안전한 정점이 하나씩 순서에 추가됩니다.
자연스럽게 사이클 감지하기
최종 순서에 n개보다 적은 정점이 있다면, 사이클이 나머지 정점들을 가로막고 있는 것입니다. 칸 알고리즘은 추가 비용 없이 사이클도 감지합니다.
if len(order) < n:
print('cycle exists')실행 시간
각 정점과 간선을 한 번씩만 확인하므로 칸 알고리즘의 실행 시간은 O(V + E)입니다. 간선이 수백만 개인 그래프에도 적용할 수 있습니다.
여러 가지 유효한 순서
여러 정점을 동시에 처리할 수 있다면 그중 어느 정점을 다음에 선택해도 됩니다. 따라서 DAG에는 유효한 위상 순서가 하나가 아니라 여러 개일 수 있습니다.
빠른 확인
칸 알고리즘을 끝냈지만 순서에 n개보다 적은 정점만 있습니다. 이것은 무엇을 의미합니까?
복습: 칸 알고리즘
진입 차수를 세고, 0인 정점을 큐에 넣고, 정점을 `pop`한 뒤, 인접 정점의 차수를 줄이는 과정을 반복합니다. 이것이 O(V+E)에 수행하는 깔끔한 위상 정렬입니다. 🚀
자주 묻는 질문
“칸의 알고리즘으로 위상 정렬” 강의는 무료인가요?
네 — “칸의 알고리즘으로 위상 정렬” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“칸의 알고리즘으로 위상 정렬”에서 뭘 배우나요?
다른 작업에 의존하는 작업의 순서를 정합니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“칸의 알고리즘으로 위상 정렬” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 칸의 알고리즘으로 위상 정렬
- 유향 그래프에서 사이클 감지하기
- 강한 연결 요소
- 브리지와 단절점