그리디 알고리즘이란?
Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다.
탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다. 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.
그리디 알고리즘 예시
그리디 알고리즘의 예시를 알아보고 문제를 통해 이해하자.
동전 거스름돈
그리디 알고리즘의 가장 대표적인 예시 동전들에 배수관계가 성립할때만 한정. 대부분의 화폐는 10, 50, 100, 500 등 딱 떨어지는 수치를 가지고 있기 때문에 그리디로 해결된다.
당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원 동전이 무한개 존재합니다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러주어야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
이 문제에서 우리가 생각할 수 있는 것은 ‘가장 큰 단위의 돈부터 생각하자’ 입니다. 만약 2240원이라는 돈을 거슬러 줘야 한다고 가정해봅시다.
이 돈을 거슬러 줄 수 있는 방법은 매우 많습니다. 10원만 사용해서 거슬러 줄 수도 있고, 다양한 동전을 사용하여 거슬러 줄 수 있지만, 조건에서는 ‘최소 개수’를 구하는 문제이므로 가장 큰 단위부터 거슬러주고 나머지를 그 다음 단위의 화폐로 거슬러 주는 것 이라는 해결 방법을 떠올릴 수 있습니다.
최소 신장 트리
test
최단 경로
test
문제 예시