그리디 알고리즘

1.그리디(Greedy) 알고리즘 

*근시안적인 선택 : 데이터 간의 관계를 고려하지 않고 수행과정에서 욕심내어

최소값 또는 최대값을 가진 데이터를 선택함 

 

-최적화 문제에 적합

-일단 선택하면 전대로 번복하지 않음 

-제한적인 문제들만 그리디 알고리즘으로 해결 가능함 

 

2.크루스칼(Kruskal) 알고리즘 

*최소 신장 트리 (Minimum Spanning Tree) 주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리 

 

-크루스칼(Kruskal)알고리즘 가중치가 가장 작은 선분이 사이클을 만들지 않을 때에만 그 선분을 추가시켜

최소 신장 트리를 구성함 

-프림(Prim) 알고리즘 주어진 가중치 그래프에서 임의의 점 하나를 선택한 후, 선분을 하나씩 추가시켜 트리를 만듦

 

3.프림(Prim)알고리즘

*주어진 가중치 그래프에서 임의의 점 하나를 선택한 후, 선분을 하나씩 추가시켜 트리를 만듦

4.다익스트라(Dijkstra)알고리즘

최단 경로(Shortest Path) 찾기 문제 주어진 가중치 그래프에서 어느 한 출발점에서

또 다른 도착점까지의 최단 경로를 찾는 문제 

시간복잡도 O(n²)