개요

문제해결 전략에서 가장 많이 등장하는 알고리즘 패턴인 그리디에 대해서 정리한다.

그리디 알고리즘 정리

그리디 알고리즘이란

그리디 알고리즘은 문제를 해결할 때,

현재 상황에서 가장 최선의 선택을 반복하여 전체적으로 최적의 결과를 도출하려는 방법이다.

한 번 선택이 이후 선택에 영향을 주지만,

그 순간 가장 이득이 되는 선택만 고려한다.

전형적인 그리디 알고리즘은 다음과 같은 형식을 가졌다.

do{
	가장 좋아 보이는 선택;
}until 해 구성 완료

그리디 알고리즘 예제

예를 들어, 동전 거스름돈 문제가 있다.

거스름돈을 줄 때, 가장 적은 수의 동전으로 줄 수 있는 조합을 구하라

이 경우

거스름돈이 1300원이라고 해보자.

일단 가장 큰 단위인 500원을 최대한 선택하고

그다음으로 큰 단위인 100원을 최대한 선택한다.

그러면 500원 2개, 100원 3개로 최소한의 동전 수가 된다.