그리디 알고리즘

그리디 알고리즘은 욕심 알고리즘이라고 하며 왜 욕심 알고리즘인지, 그리디 알고리즘의 예시를 들어 설명드리겠습니다.

그리디 알고리즘의 대표적인 예로는 동전 거스름돈 문제가 있습니다. 이 문제는 거스름 동전의 갯수가 최소가 되는 해를 찾는 문제입니다.

 

동전이 500원, 100원, 50원, 10원짜리가 있을 때 거스름돈이 560원이라면,

먼저, 560-500 = 60로 거스름돈이 60원 남게 되고 거스름 동전은 500원짜리 동전 1개입니다.

60-100은 불가능하기 때문에 넘어가고, 60-50 = 10로 거스름돈이 10원 남게 되고 500원짜리 동전 1개, 50원짜리 동전 1개로 총 2개 입니다.

마지막으로 10-10 = 0이므로 거스름돈이 0원이 되고 500원, 50원, 10원 동전 각각 1개씩 총 거스름돈의 동전 개수는 3개가 됩니다. 

 

그리디 알고리즘을 사용하면 이처럼 최소한의 동전을 거슬러 받을 수 있을 것처럼 보이지만 사실 그리디 알고리즘이 무조건 최적의 해를 찾는 것는 아닙니다. 왜냐하면 그리디 알고리즘은 무조건 큰 수(금액이 큰 동전)부터 차감하기 때문인데, 참고한 책*에 나와있는 예시를 들어보겠습니다.

 

만약 200원을 거슬러줘야하고, 160원, 100원, 10원짜리의 동전이 있다고 가정하면 그리디 알고리즘은 160원 동전 1개, 10원 동전 4개를 거슬러줄것입니다. 하지만 직관적으로 100원짜리 동전 2개가 최소 동전 개수가 된다는 것을 알 수 있습니다.

 

 

* 참고한 책 : 4장 | 알기 쉬운 알고리즘 | 양성봉 | 생능출판사

** 알고리즘은 위의 책에 있는 알고리즘을 사용했기 때문에 책이 있으시면 더 쉽게 이해할 수 있습니다.