해나의 컴공생존기

1. Kruskal Algorithm 크루스칼 알고리즘의 기본 아이디어는 가장 작은 weight의 edge부터 하나씩 추가하는것이다. 단 사이클이 생기면 버리고 다음 weight의 edge를 확인한다. 위으 그림으로 예를 들어보겠다. 가장 작은 비용을 가진 edge는 1노드와 6노드를 잇는 10짜리 노드이다. 이것을 선택한다. 그 뒤로도 작은 순서대로 선택한다. 10, 12, 14, 16 이 다음으로 비용이 적은건 18이지만 18을 선택하면 사이클이 생기기에 그 다음인 22를 선택한다. 위와같이 사이클이 생기지 않게 작은 것들만 골라 spanning tree가 만들어지게 하면 된다. 증명 (proof by induction) 증명하기 전에 몇가지 가정을 이해해야한다. Tmst는 많은 정답 Edge set..

1. greedy Algorithm greedy 알고리즘은 선택을 반복하는 알고리즘들 중 비교적 간단하게 선택하고 선택한 것은 바꾸지 않는 알고리즘이다. 2. Minimum Spanning Tree (MST) Spanning Tree는 그래프의 모든 정점과 간선의 부분집합으로 구성된 부분 그래프이다. MST는 주어진 그래프의 연결 그래프들 중 엣지들의 비용이 최소가 되도록 하는 그래프이다. (단, 사이클을 생성X) 사이클이 있으면 안되는 이유는 사이클이 없어도 되기 때문이다. 사이클이 중 하나를 없애도 연결그래프는 유지가 된다. 게다가 비용까지 감소가 된다. 우리는 '최소'를 찾고 있으므로 사이클이 있을필요가 없다. 아니, 있으면 안된다. 3. Prim Algorithm 프림 알고리즘의 아이디어는 먼저 ..