94 lines
4.2 KiB
Markdown
94 lines
4.2 KiB
Markdown
deck:: Logseq/coding tip
|
||
|
||
- ## 1. 개념(Concept)
|
||
- **정의** :-> 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 거스르지 않도록 나열하는 알고리즘.
|
||
id:: 694a355c-b251-4b21-bcf0-1d19912a0150
|
||
- **대상** : {{cloze 사이클이 없는}} 방향그래프 에서만 사용 가능 #card
|
||
id:: 694a3575-2dc7-4567-ae8a-55f3b2f41c63
|
||
extra:: 사이클이 존재한다면 순서를 정할 수 없기 때문
|
||
- **특징**
|
||
- 정답결과가 {{cloze 하나가 아닐 수도 있음}} #card
|
||
extra:: 진입 차수가 0인 노드가 동시에 여러 개라면 선택 순서에 따라 결과가 달라짐
|
||
id:: 694a369e-6bc2-4e36-a9d3-cca9f3c2dc42
|
||
- 모든 원소를 방문하기 전에 큐가 빈다면 {{cloze 사이클}} 이 존재하는 것입니다.
|
||
id:: 694a36e1-53a9-4afa-be3d-a76239551547
|
||
- ## 2. 동작 원리 (Algorithm Flow)
|
||
- ### 1) 순서
|
||
- 위상 정렬은 주로 진입 차수(Indegree) 와 큐(Queue) 를 이용하여 동작함.
|
||
- **1단계 : 진입차수 계산**
|
||
- 그래프의 모든 노드에 대해, {{cloze **자신을 향하는 간선의 개수( indegree )**}} 를 미리 계산해 둡니다.
|
||
id:: 694a3899-c5bb-4f46-9a5f-80dd8316d7fe
|
||
- **2단계 : 초기 큐 설정**
|
||
- 진입 차수가 {{cloze **0**}} 인 모든 노드를 큐에 넣습니다. #card
|
||
extra:: 이 노드들이 바로 작업의 시작점이 됩니다.
|
||
id:: 694a389e-1f99-497e-9f2f-d4574f634d87
|
||
- **3단계 : 큐를 이용한 반복**
|
||
- 큐에서 노드를 하나 꺼내 결과 리스트에 추가.
|
||
- 꺼낸 노드에서 출발하는 모든 간선을 제거.
|
||
id:: 694a3884-ec0c-4308-9719-42ceea861a0d
|
||
(실제로는 {{cloze 연결된 노드들의 indegree 를 1씩 감소시킴}} )
|
||
- 이때 새롭게 indegree 가 0이 된 노드가 생기면, 즉시 큐에 추가합니다.
|
||
- **4단계 : 종료 및 사이클 확인**
|
||
- 큐가 비면 모든 과정이 끝.
|
||
- 만약 결과 리스트에 담긴 노드의 개수가 전체 노드 개수보다 적다면 ? #card
|
||
id:: 694a38d5-9470-4258-abc0-f7dcdebe0267
|
||
- 이는 사이클이 존재하여 모든 노드를 정렬할 수 없었음을 의미.
|
||
- ### 2) 코드(python 기준)
|
||
- 다음과 같이 초기화 되어 있을 때, topology_sort() 함수의 정의는 다음과 같다.
|
||
id:: 694a390d-a75a-4fb7-80c4-5933ab1ea454
|
||
```python
|
||
from collections import deque
|
||
|
||
# 노드 개수(v)와 간선 개수(e)
|
||
v, e = 7, 8 # 예시
|
||
|
||
# 진입 차수 배열 (모두 0으로 초기화)
|
||
indegree = [0] * (v + 1)
|
||
|
||
# 그래프 표현 (인접 리스트 방식)
|
||
graph = [[] for _ in range(v + 1)]
|
||
|
||
# 예시 간선 정보 (a -> b)
|
||
# 1->2, 1->5, 2->3, 3->4, 4->6, 5->6, 6->7, 7->4(X)
|
||
edges = [(1,2), (1,5), (2,3), (3,4), (4,6), (5,6), (6,7), (7,4)] # 7->4는 사이클 유발 가능성
|
||
|
||
for a, b in edges:
|
||
graph[a].append(b)
|
||
indegree[b] += 1
|
||
|
||
```
|
||
#card
|
||
- ```python
|
||
def topology_sort():
|
||
result = []
|
||
q = deque()
|
||
|
||
# 1. 진입 차수가 0인 노드를 큐에 삽입
|
||
for i in range(1, v + 1):
|
||
if indegree[i] == 0:
|
||
q.append(i)
|
||
|
||
# 2. 큐가 빌 때까지 반복
|
||
while q:
|
||
now = q.popleft()
|
||
result.append(now)
|
||
|
||
# 3. 연결된 노드들의 진입 차수 감소
|
||
for i in graph[now]:
|
||
indegree[i] -= 1
|
||
if indegree[i] == 0: # 새롭게 0이 되면 큐에 삽입
|
||
q.append(i)
|
||
|
||
# 결과 출력
|
||
print(*result)
|
||
|
||
```
|
||
- ## 3. 시간 복잡도
|
||
- 시간복잡도는 {{cloze $O(V + E)$}} (V: 노드 수, E: 간선 수) #card
|
||
extra:: 모든 노드를 한 번씩 큐에 넣고 확인하며($V$), 그 과정에서 모든 간선을 한 번씩 확인($E$)하여 진입 차수를 줄이기 때문.
|
||
id:: 694a39c0-ff89-4801-8cb2-8e1297d62ccb
|
||
- ## 4. 사용 예시
|
||
- 선수 과목(Prerequisite
|
||
- 특정 과목을 들어야 다음 과목을 들을 수 있을 때 들어야 하는 과목 순서를 정렬하는 작업.
|
||
- 프로젝트 일정 관리
|
||
- A 작업이 끝나야 B 작업을 시작할 수 있는 스케줄링. |