[알고리즘/Algorithm]그리디(Greedy)

Seok_IN 2021. 8. 22. 14:35

🔷 그리디(Greedy Algorithm)

그리디(Greedy) 알고리즘은 단어 그대로 '욕심쟁이(탐욕)' 이라는 말이다. 이 알고리즘은 '현재 상황에서 지금 당장 좋은 것만 고르는 방''을 의미한다. 다른 알고리즘을 이용한 문제들과 비교했을때 '사전에 외우지 않더라도 풀 가능성이 높은 유형' 이라는 특성이 있다. 반대로 얘기하면 문제를 풀 때 어느정도의 창의력, 문제를 해결하는 능력이 요구 되어진다.

"이것이 코딩테스트다 with 파이썬"에 나온 예제를 통하여 알아보자.

🔷 예제(Example)

◼ 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정하고, 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하여라.

(단, N은 항상 10의 배수이다.)

◼ 해설

이 문제는 그리디 알고리즘을 이용하여 푸는 가장 대표적인 문제이다. 우선적으로 고려할 기준을 먼저 생각했을 때 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것을 먼저 떠올릴 수 있다.

◼ 참고

이것이 취업을 위한 코딩 테스트다 with 파이썬