공부하자

위상 정렬 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 순서를 결정해주는 알고리즘 DAG(Directed Acyclic Graph)그래프여야 함. 방향성이 있고, 사이클이 없는 그래프 위상 정렬의 시간 복잡도는 O(V + E)로 문제를 해결할 수 있음. 힙 자료구조와 함께 적용하면 쉽게 문제를 풀 수 있음. 위상정렬 알고리즘 순서 1) 진입 차수(Indegree, 자기 자신으로 오는 간선을 의미)가 0인 정점을 큐에 삽입한다. 2) 큐에 원소를 꺼내 해당 원소와 간선을 제거한다. 3) 제거 이후에 진입 차수가 0이 된 정점을 큐에 삽입한다. 4) 큐가 빌 때까지 2) ~ 3) 과정을 반복한다. * 사이클이 존재하면 진입차수가 0인 정점을 찾을 수 없기때문에 위상 정렬 적용 불가. 모든..