Chapter 10 다양한 알고리즘

복습) 여러개의 도시가 연결되어 있다 == 그래프 알고리즘

그래프 알고리즘 중 트리 자료구조 -> '다익스트라 최단 경로 알고리즘', 우선순위 큐, 최대힙[크기가 작은 자료구조로서 트리 자료구조]

 

노드의 개수가 많은 경우, 인접행렬[플로이드 워셜 알고리즘] == 시간복잡도 O(V의 제곱)

노드의 개수가 적은 경우, 입접 리스트[다익스트라 최단 경로 알고리즘] ==  시간복잡도 O(E)

---

서로소 집합 : 공통 원소가 없는 두 집합

서로소 집합 자료구조 :  트리 자료구조

 

 

서로소 집합 알고리즘의 시간 복잡도

 

서로소 집합을 활용한 사이클 판별

---

크루스칼 알고리즘

---

위상 정렬

위상정렬 시간 복잡도

---

실전 2. 팀 결정

실전 3. 도시 분할 계획

실전 4. 커리큘럼