[알고리즘] 그리디(Greedy), 탐욕 알고리즘 | 거스름돈 문제

그리디(Greedy) 알고리즘이란? 그리디 알고리즘은 "매 선택에서 그 순간 당장 최적인 답을 선택" 하여 적합한 결과를 도출하는 알고리즘 설계 기법이다. 그리디 알고리즘은 최적 부분 구조(optimal substructure)를 가진 문제를 해결하는데 강점이 있다. 최적 부분구조란 매 순간의 최적해의 합이 문제에 대한 최적해여야 한다는 의미이다. 예를 들어 누군가 A도시에서 B도시를 거쳐 C도시로 간다고 하자. A도시에서 B도시를 갈 때 가장 짧은 거리인 150km 경로를 선택하고, B도시에서 C도시로 갈 때 가장 짧은 거리인 140km 경로를 선택하면, 전체적으로도 최적의 경로가 된다. 매 순간 최적 경로의 합이 전체 경로의 최적 경로가 되었다. 이러한 최적 부분 구조를 가진 문제는 그리디 알고리즘으..

원문링크 : [알고리즘] 그리디(Greedy), 탐욕 알고리즘 | 거스름돈 문제