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 작업을 시작할 수 있는 스케줄링.