[자료구조 및 알고리즘] CH11. Greedy algorithm

 

Greedy algorithm이란?

• 매 의사결정마다 정해둔 조건에 따라 가장 좋아보이는 답을 선택하는 것

Greedy algorithm(탐욕알고리즘)은 어디에 쓰이나?

• 주로 특정 제한조건(Constraints)을 만족해야 하는 상황에서의 최적화 문제에 사용
• 예) machine scheduling, bin packing, minimum spanning tree(MST)

MST란?

• Spanning tree란 그래프의 모든 노드를 포함하는 트리이다. 이 때, MST란 edge의 가중치 합의 최소인 spannig tree이다.

Shortest path problem(추후 자세히 포스팅)

• 다익스트라 알고리즘(Single source all destination)

MST(각 방법별로 추후 자세히 포스팅)

• Kruscal's algorithm
• Prim's algorithm
• Sollin's algorithm