Greedy (탐욕법)

모든 경우의 수를 고려해서 최고의 결과를 찾는 방법에 Dvide & Conquer와 DP가 있다면
Greedy Method는 현재 상태에서 선택 가능한 최선의 선택을 통해 정답을 찾는다.

• 순간 순간의 선택은 local에서 최선이다.
• local의 최선의 선택으로 최종적인 정답(global)을 찾아도, 그 정답이 최적해라고 보장할 수 없다.
• 탐욕적 방식으로 문제를 해결할 때는 탐욕적인 방법이 항상 최적해를 제공하는지 검증해야함

Greedy의 대표 예제들

거스름돈 문제

동전의 개수를 최소가 되도록 거스름 돈을 주는 문제
탐욕적 알고리즘으로 거스름돈 문제를 해결할 때는 가치가 높은 동전부터 거스름돈을 초과하지 않도록 내려준다.

백준 14916 거스름돈

거스름돈 문제가 최적해를 제공하지 않는 경우

ex) 120원짜리 동전이 생겼을 때, 160원을 거슬러 주는 경우

Greedy의 경우 120 x 1 + 10 x 4 = 160 (5개)의 해를 제출하지만
실제로는 100 x 1 + 50 x 1 + 10 x 1 = 160 (3개)가 정확한 해답이 된다.

최소비용 신장트리(Minimun cost Spanning Tree) 탐색

신장 트리란?

서로 연결된 비방향성 그래프(Undirected Graph)에서 순환 경로를 제거하면 정점이 서로 연결된 상태의 부분 그래프를 신장 트리(Spannning Tree)라고 한다.
보통 DFS, BFS에서 나오는 순환하지않는 그래프를 신장트리 상태라고한다.

Prim Algorithm

N개의 정점(Vertex, Node) 중 임의의 정점를 선택한 후 현재 방문하지 않은 정점들과 연결된 간선(Edge, Weight)중 가장 비용이 적은 간선을 연결을 반복하는 알고리즘
BFS와 유사

Kruskal Algorithm

모든 간선의 비용을 알고 있는 상태에서 가장 비용이 적은 간선들 중 순환이 일어나지 않는 정점을 서로 연결하는 알고리즘
Union-find 방식을 사용

MST탐색 알고리즘 성능

성능의 차이는 거의 없지만 개인적인 경험으로 union-find 방식을 구현하는 것 보다 bfs를 구현하는 것이 더 익숙하므로 코딩 테스트에선 프림 알고리즘을 추천한다.
다만 카카오 코테에서 union-find 방식의 문제가 나온 경우가 있으니 한 번쯤은 구현을 해보고 문제풀이를 통해 아이디어를 얻는 것도 좋을 것이라 생각한다.