Repository navigation
[위상정렬] 개념정리
#119
Replies: 0 comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
위상 정렬(Topological Sort)란?
위상 정렬 = "위상" + "정렬"
정렬은 어떤 데이터를 어떤 기준에 맞게 나열하는 것이었다.
Directed Acyclic Graph (DFG): 싸이클이 없는 방향성 그래프
차수(Degree)란?
정점의 차수는 정점에 연결된 간선의 개수였다. 이전에는 무방향 그래프만 다뤘었는데 이번엔 방향성 그래프로 차수를 Indegree와 Outdegree로 구별할 필요가 있따.
예를들어 5번 정점에서 Indegree는 5번 정점이 도착점인 것으로 2개, Outdegree는 반대로 5번 정점에서 나가는 간선이므로 2개이다.
그렇다면 위상정렬이란?
간선의 방향성을 조건으로 삼아서 정점들의 번호를 수열에 나열하는 행위를 위상정렬이라고 한다.
조건은 다음과 같은 형식으로 구성된다.
1번에서 4번으로 향하는 간선이 있으므로 정렬 조건에서 1번이 4번보다 먼저 나타나야 한다.
5에서 4번으로 향하는 간선이 있으므로 5번이 4번보다 먼저 나타나야 한다.
...
이런 식으로 간선 하나하나 마다 어떤 정점임 어떤 정점보다 먼저 와야 하는데 모든 정점이 이 조건을 만족하게 하는 것이 위상정렬이다.
만약 싸이클이 있는 그래프라면 이것이 가능할까? 분명 만족하지 않는 간선이 등장한다.
따라서 위상정렬은 Directed Acyclic Graph (DFG): 싸이클이 없는 방향성 그래프에서만 가능한 것이다.
위상정렬 아이디어
Q: "제일 먼저" 올 수 있는 정점은?
A: "들어오는 간선"이 없는 정점! (그림에서 1, 7, 9가 가능)
이를 통해 생각해볼 수 있는 점은 2가지이다.
이렇게 후보를 추출하면 D라는 자료구조를 사용해 그 후보들을 다 담아두고, 하나씩 위상 정렬 시켜버리면서 그래프에서 삭제해주자
1. 9번 정점 정렬
2. 1번 정점 정렬 + 3번 정점 후보로 추가
3. 7번 정점 정렬 + 5번 정점 후보로 추가
4. 3번 정점 정렬 + 8번 정점 후보로 추가
5. 5번 정점 정렬 + 6번 정점 후보로 추가
6. 8번 정점 정렬 + 2, 4번 정점 후보로 추가
7. 6, 2, 4번 정점 정렬
위상정렬 과정 정리
자료구조 D를 선정하는 기준은? 문제에서 요구하는 연산의 종류 생각하기
여러 자료구조들 중에서 원소를 넣고 빼는 두 연산을 "빠르게" 해주는 것은?
Queue, Stack, Linked List, etc... -> O(1)의 시간으로 가능하다.
이 중 Queue를 활용해보자
while문의 반복 횟수는 정점의 개수이기 때문에 O(V)의 시간이 걸린다.
그래프에서 제거하는 과정은 각 정점의 차수만큼 돌기 때문에 간선의 개수와 같다. 따라서 O(E)의 시간이 걸린다.
새롭게 후보를 추가하는 과정은 모든 정점을 다 확인하기 때문에 O(V)이다.
따라서 총 시간복잡도는 O(V^2)이 된다. 이러면 너무 오래걸린다. 따라서 다음과 같이 시간을 줄일 수 있다.
이런 구현이 가능한 이유를 생각해보자.
새롭게 정렬 가능한 점은 들어오는 간선의 수가 0이 되어야 한다. 그리고 y 정점이 indeg[y]가 0이 되는 순간이 단 한번뿐이어야 한다. 생각해보면 0이 되는 순간은 마지막으로 y에 들어오는 x가 삭제되는 순간이므로 당연히 한번만 해당 if문을 만족한다.
따라서 총 O(V + E)의 시간이 걸린다.
All reactions