오뚝이개발자

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(각 방법별로 추후 자세히 포스팅) Krusc..