크루스칼2 [Algorithm] 최소 신장 트리(MST), Kruskal & Prim algorithm 신장 트리(Spanning Tree) 그래프 내의 모든 정점을 포함한 최소 연결 부분 그래프이며 Tree이기 때문에 사이클이 존재할 수 없다. 최소비용 신장 트리 (Minimum Spanning Tree : MST) 신장 트리 중 간선의 가중치 합이 최소인 트리이다. 가중치가 존재하는 무방향 Graph에서 Spanning Tree(이하 신장 트리)를 무작위로 만들어 었을 경우 cost는 다양하게 나옵니다. 하지만 그중에서 최소 비용으로 만드는 신장 트리를 Minimum Spanning Tree(이하 최소비용 신장 트리)라고 한다 사진을 보면 Graph에서 Cost(가중치합)을 고려 안한 신장 트리를 제작을 했을 경우 Cost가 13이 나오게 됩니다. 여기서 Cost를 최소한으로 줄여본 신장 트리는 Cos.. 2024. 4. 7. [Algorithm] Greedy Algorithm 목차 1. Greedy Algorithm? 2. 대표적인 Greedy 3. 코드모음 _링크_ Greedy Algorithm이란? Greedy Algorithm(이하 Greedy) 말 그대로 탐욕스럽게 현재 '가장 좋아 보이는' 답(최선의 선택)을 선택하는 알고리즘 Greedy는 DP(동적프로그래밍)을 간단한 문제 해결에도 지나치게 많은 일을 하는 문제점을 해결하고자 고안되었다. 최선의 선택은 선택할 당시에 가장 좋은 것을 선택하는 것을 의미합니다 간단하게 예시를 들면 눈앞에 12만원과 18만원이 있다면 18만원을 선택하는 것과 동일합니다. 뒤에 뭐가 있든 최선을 선택하는 것은 좋은 결과물을 보장해줄까요? 한번 예시를 들어보죠 거스름돈 예시입니다. 기존 화폐단위에서 10만원을 큰 화폐부터 거슬러 줘서 적은.. 2024. 4. 7. 이전 1 다음
