Chapter 4. 그리디 알고리즘
✔️ 그리디 알고리즘
: 최적화 문제를 해결하는 알고리즘
-
최적화 문제
-> 가능한 해들 중에서 가장 좋은(최대 or 최소) 해를 찾는 문제 -
근시안적인 선택으로 부분적인 최적해를 찾고, 이들을 모아서 문제의 최적해를 얻음
-
한번 선택하면 절대로 번복하지 않음 ->선택 데이터를 버리고 다른 것을 취하지 않음
4.1 동전 거스름돈 문제
1) 동전 거스름돈 문제를 해결하는 가장 간단하고 효율적인 방법
2) 동전 거스름돈 문제의 최소 동전 수를 찾는 그리디 알고리즘
4.2 최소 신장 트리
:주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 간선들의 가중치 합이 최소인 트리
-
트리(tree) :conntected acyclic graph
-
크러스컬(Kruskal) 알고리즘
:가중치가 가장 작은 간선이 사이클을 만들지 않을 때에만 그 간선을 추가
KruskalMST(G)
//Line1: 간선 정렬하는데 O(mlogm) 시간
m: 입력 그래프에 있는 간선의 수
Line2: T를 초기화하는 것이므로 O(1) 시간
Line3~8
* while 루프는 최대 m번 수행
그래프의 모든 간선이 while 루프 내에서 처리되는 경우
* while 루프 내에서는 L로부터 가져온 간선 e가 사이클을 만드는지 검사하는데 거의 O(1) 시간
=> Kruskal 알고리즘의 시간복잡도: O(mlogm)
cf) 연습문제 28번 ⏰ 크러스컬 알고리즘의 시간 복잡도
O(mlogm)
- 프림(Prim) 알고리즘
:임의의 점 하나를 선택한 후, (n-1)개의 간선을 하나씩 추가
PrimeMST(G)
///⏰ 프림 알고리즘의 시간 복잡도
(n-1) x O(n) = O(n^2)
✔️ Kruskal과 Prim 알고리즘의 수행 비교
