Computer Science/Algorithm
[Algorithm] Topology Sort (위상 정렬)
위상 정렬이란? 순서가 정해져있을 때 정렬을 해주는 알고리즘이다. 위상 정렬의 특징 사이클이 없는 방향 그래프에서만 수행된다. 사이클이 생기면 어떤 정점에서 시작해도 결국 그 정점으로 돌아오기 때문에 모든 방향성을 만족시킬 수가 없다. 위상 정렬의 예 과목 A, B, C, D가 있을 때, 아래와 같이 순서를 정해주었다면 위상 정렬을 사용한다. A는 B를 우선적으로 수강해야 수강 가능하다. B는 C를 우선적으로 수강해야 수강 가능하다. D는 B를 우선적으로 수강해야 수강 가능하다. C → B → A, D 가 될 것이다. 위상 정렬의 동작 과정 먼저, 설명하기 전에 주요 키워드를 알아야 한다. 진입 차수(indegree) : 노드로 들어오는 간선의 개수 진출 차수(outdegree) : 노드에서 나가는 간선..
