문제 풀이/알고리즘, 자료구조
-
Greedy Algorithm문제 풀이/알고리즘, 자료구조 2020. 12. 23. 16:26
Greedy Algorithm greedy 탐욕스러운, 말 그대로 현재 시점에서 가장 이익되는 것을 쫓아간다. 필자가 학교에서 경로를 선택하는 매 순간마다 가장 짧은 경로를 찾아서 집을 간다고 가정하자. 버스와 지하철 노선 혹은 보행도로 등 무수한 경로에서 가장 짧은 경로를 찾아서 집으로 다가갈 것이다. 집으로 가는 길을 너무 나도 많고, 현재 가고 있는 길이 집까지 가는 가장 빠른 경로라는 것을 보장할 수 없다. 그리디 알고리즘은 결과적으로 가장 빠른 경로를 찾는 것이 아닌, 현재 시점에서 가장 빠른 경로를 찾는 방법이기 때문이다. 눈 앞의 이익만 우선 추구하는 알고리즘을 총칭한다. 그리디 알고리즘은 최적화 문제를 대상으로 한다. 그렇기 때문에 최적해를 보장하지 못한다. 그리디 알고리즘의 목표는 최적해..