이번 포스트에서는 위상정렬 알고리즘에 대해 살펴보자. 위상정렬 알고리즘이란? 위상정렬(位相整列: Topological Sorting)이란 노드 서로간의 위치(선-후관계)에 따라 모든 정점들을 배열하는 작업을 말한다. 주로 업무의 일정을 일이 진행되어야 할 순서에 따라 배치하기 위해 사용되는 알고리즘이다. 대표적으로 과목들간의 선수관계에 따른 수강 계획을 작성한다든가 게임에서 어떤 빌딩을 생성하기 위한 테크트리를 떠올리면 쉽다. 그래프 요소들이 정렬되기 위해서는 당연히 명확한 순서가 있어야 한다. 따라서 위상 정렬은 DAG(directed acyclic grapy: 비순환의 유향 그래프)에서만 의미가 있다. 즉 닭이 먼저인지, 달걀이 먼저인지 인것 처럼 선행 요소를 알 수 없는 경우는 사용할 수 없다. 과..
[위상정렬] 1. 알고리즘 이해
이번 포스트에서는 위상정렬 알고리즘에 대해 살펴보자. 위상정렬 알고리즘이란? 위상정렬(位相整列: Topological Sorting)이란 노드 서로간의 위치(선-후관계)에 따라 모든 정점들을 배열하는 작업을 말한다. 주로 업무의 일정을 일이 진행되어야 할 순서에 따라 배치하기 위해 사용되는 알고리즘이다. 대표적으로 과목들간의 선수관계에 따른 수강 계획을 작성한다든가 게임에서 어떤 빌딩을 생성하기 위한 테크트리를 떠올리면 쉽다. 그래프 요소들이 정렬되기 위해서는 당연히 명확한 순서가 있어야 한다. 따라서 위상 정렬은 DAG(directed acyclic grapy: 비순환의 유향 그래프)에서만 의미가 있다. 즉 닭이 먼저인지, 달걀이 먼저인지 인것 처럼 선행 요소를 알 수 없는 경우는 사용할 수 없다. 과..
2022.08.29