위상
-
위상정렬 Topological SortAlgorithm/Theory 2020. 6. 7. 13:21
목표 - 위상정렬 (Topological Sort)를 이해하고 설명할 수 있다. - 위상정렬의 조건을 알고 언제 어떻게 사용하는지 이해한다. 위상정렬? \ 특정한 순서를 가진 조건에서 사용한다. DAG(방향성 비순환 그래프) 에서만 사용할 수 있다. \ "위상" 이라는 사전적 정의에서 알 수 있듯이, 위상정렬이란 어떤 순서를 가지고 있는 경우에 사용할 수 있는 정렬 방법입니다. 게임을 하는데 어떤 스킬을 익히기 위해 반드시 먼저 배워야 하는 사전스킬이 있죠? 이런 식으로 어떤 순서를 가지고 있을 때 사용합니다. 이 말인즉 위상정렬은 방향성을 가지고 있어야 합니다. 그리고 이 의미를 잘 생각해보면 사이클이 생기면 안된다는 것을 알 수 있습니다. A -> B -> C 순서를 가지고 있어야 하는데 여기서 C ..