0. 최소 신장 트리(MST)신장 트리n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리최소 신장 트리 (MST, Minimum Spanning Tree)무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 최소 신장 트리를 구하는 대표적인 알고리즘인 Kruskal과 Prim에 대해 알아보자.1. Kruskal 알고리즘크루스칼 알고리즘은 간선 중심 그래프이며, 그리디 알고리즘이다.1-1. 알고리즘간선을 하나씩 선택해서 MST를 찾는 알고리즘모든 간선을 가중치에 따라 오름차순으로 정렬가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴사이클이 발생하면 MST에 포함시키지 않음사이클이 발생하지 않는 경우 MST에 포함n-1개의 간선이 선..

0. 탐욕 알고리즘이란?탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법이다.일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다.각 선택 시점에서 이루어지는 결정은 그 순간에는 최적이지만, 그 선택이 모인 최종적인 해답이 최적이라는 보장은 없다.1. 배낭 짐싸기(Knapsack)배낭에 담을 수 있는 물건의 총 무게(W)가 정해져 있다.이 때, 배낭이 수용할 수 있는 무게를 초과하지 않으면서, 값이 최대가 되는 물건을 담는 경우, 그리디 알고리즘을  생각해볼 수 있다.1-1. 0-1 Knapsak배낭에 물건을 통째로 담아야 하는 문제 ➡ 물건을 쪼갤 수 없는 경우이 방식은 그리디 알고리즘을 적용하기 어렵다. 아래에는 총무게가 30kg인 배낭에 0-1Knaps..