정의

• 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.
• 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다.
• 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다.
• 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다.
• 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다.
• 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환 유향 그래프(directed acyclic graph)여야 한다.

위상정렬 과정

1. 자기 자신을 가리키는 변이 없는 꼭짓점을 찾음.
2. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제
3. 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료시킨다.

• 나동빈 님의 알고리즘 강좌
  https://www.youtube.com/watch?v=qzfeVeajuyc&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98

질문

1. 위상정렬을 시간복잡도 키워드를 사용해서 설명해줄수있나요?
   : 위상정렬은 유향 그래프 (DAG, Directed Acyclic Graph) 에서 선후관계를 고려한 정렬 방식입니다. 즉, A -> B 의 관계가 있다고 했을때, 위상정렬을 하면 반드시 A 가 B 보다 먼저 출력되어야합니다. 이때 사용되는 기법이 DFS입니다. 모든 노드들을 탐색한뒤 각 노드들에 방문/방문종료 시점들을 기록해 둡니다. 이후 방문 종료시점의 내림차순을 정렬합니다.
   이에 계산복잡성은 DFS에 비례하게 되고 시간 복잡도는 E(각 정점에 대한 Incoming Edge 계산) + V(각 정점을 순회하며 출력),
   따라서 O(E+ V) 의 시간 복잡도를 가지게 됩니다..

2. Django 를 사용해 보신적이 있나요?
   : 졸업프로젝트 당시 DB를 어떤 것을 사용할까 하다가 제 팀의 주요 언어가 파이썬 이기도 하고 해서 사용하기 위해 튜토리얼을 진행해본적은 있습니다. 하지만 저희 프로젝트의 복잡성이나 사이즈에 비해서 너무 큰 프레임워크라고 판단되어서 대신 Flask를 사용해서 프로젝트를 마무리한 경험이 있습니다.
   - 있다면, Django에서 migration dependency를 해결하기 위해 사용하는 알고리즘에 대해 설명해 주실 수 있나요? (키워드 : cycleDependencyError, Topological Sorting)
   : Django는 각 마이그레이션의 파일 이름이 아니라 마이그레이션 클래스의《dependency》와 《run_before》라는 두 가지 속성을 사용하여 마이그레이션이 적용되어야 하는 순서를 결정합니다. 순서는 위상정렬을 통해서 확인해볼수있고 장고안에 유틸리티로서 위상정렬파이썬 파일이 있고 거기서 cycleDependencyError를 확인할수있는걸로 알고 있습니다
   

• https://gaemin.tistory.com/5
• https://medium.com/swlh/how-django-uses-topological-sorting-for-resolving-migration-dependencies-1a93b544037f
• https://github.com/django/django/blob/main/django/utils/topological_sort.py
  

3. 위상정렬을 사용하기 위한 그래프의 조건을 설명해주시고, 왜 그러한 조건의 그래프여야 하는지 말씀해주실수 있나요?
   : 위상정렬은 유향 그래프 (DAG, Directed Acyclic Graph) 에서 선후관계를 고려한 정렬 방식입니다. 즉, A -> B 의 관계가 있다고 했을때, 위상정렬을 하면 반드시 A 가 B 보다 먼저 출력되어야합니다.