IT/Algorithm (1) 썸네일형 리스트형 위상 정렬(Topological sort) 위상정렬이란? 위상정렬은 작업의 순서를 정해주는 알고리즘입니다. 어떤 일을 진행시키기 위해 순서가 정해져 있는 경우에 사용할 수 있습니다. 예를들어, 선수과목을 생각해보면 이해하기 쉬운것 같습니다. 순서가 있다는 말은 그 관계에서 방향성이 있다는 것 입니다. 위상정렬은 DAG(Directed Acyclic Graph)로써 사이클이 발생하지 않는 방향 그래프의 성질을 가지고 있습니다. 사이클이 발생하는 경우 위상 정렬을 수행할 수 없습니다. 구현 방법 queue를 이용한 구현 방법이 일반적이라고 합니다. Queue를 이용한 구현 1. in degree가 0인 노드를 queue에 삽입 2. queue에 있는 관련 노드의 간선 삭제 3. in degree 업데이트 (1~3 반복) 4. 종료 후 모든 노드 탐색.. 이전 1 다음