위상정렬(topology sort)은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘입니다. 기능 특징 시간 복잡도(V: 노드 수, E: 에지 수) 노드 간의 순서를 결정함. 사이클이 없어야 함. O(V+E) 위상 정렬에서는 항상 유일한 값으로 정렬되지 않습니다. 또 사이클이 존재하면 노드 간의 순서를 명확히 정의할 수 없어 위상정렬을 적용할 수 없습니다. 아래 구체적인 시나리오를 통해서 단계별로 알아봅시다. 위상 정렬의 원리 1. 그래프에서 진입차수(in-degree) 을 저장합니다. 진입차수는 자기 자신을 가리키는 에지의 개수입니다. 1 에서 2, 3 을 가리키고 있으므로 D[2], D[3] 을 각각 1을 증가하는 식으로 계산하면 진입 차수 배열 D[N] 을 구할 수 있습니다. 2. 진입 차..
