안녕

문제)

Prin's Algorithm은 Minimum Spanning Tree를 찾는 가장 기초적인 알고리즘입니다. 1. Minimum Spanning Tree란? 우선, Minimum Spanning Tree를 알아보겠습니다. G(graph)에 대한 Spanning Tree는 G의 모든 vertex를 포함하고, 트리인 connected 된 그래프입니다. 만약 G = (V, E)로 이루어져 있다면, Spanning Tree인 T = (V, F)가 되어야 합니다. 이때 F는 V-1과 같습니다. 만약 F가 V-1보다 크다면 cycle이 생겨서 Tree가 되지 않습니다. 아무튼 우리가 찾아야 하는 (V, F)는 Edge의 weight의 합이 최소가 되는 집합을 찾아야 합니다. edge의 weight가 최소가 되는 S..

1. 탐욕 알고리즘이란? 탐욕 알고리즘이란 각 순환마다 '가장 좋은' 선택을 합니다. 탐욕 알고리즘은 DP와 마찬가지로 최적화 문제를 푸는데 주로 사용됩니다. 또한 상대적으로 DP보다 알고리즘을 설계하기 더 쉽습니다. DP는 재귀 관계식을 세워서 큰 instance를 작은 instance로 분할해서 문제를 풉니다. 하지만 탐욕법은 instance를 분할하지 않습니다. 단지 순서대로 가장 좋아 보이는 답을 선택해서 모읍니다. 즉, 어떤 선택이든지 선택할 당시에는 최적입니다. (locally optimal) 하지만 이게 곧 전체에서 최적인 해 (globally optimal)를 구한다는 보장은 없습니다. 따라서 탐욕법은 해당 알고리즘이 최적의 해답을 얻는지 확인하는 절차를 반드시 거쳐야 합니다. DP는 최적..