그리디 알고리즘

• 그리디(Greedy) 알고리즘은 단순하지만 강력한 알고리즘이다. 현재 상황에서 가장 좋은 방법을 취하는 것'을 의미한다. 그리디 알고리즘을 이용하면 그 순간 '가장 좋은 것'만을 선택하여 적용하고, 그 이후의 상황은 고려하지 않는 것이다.

그리디 알고리즘 문제 유형

• 그리디 알고리즘의 문제 유형은 사전에 외우고 있지 않아도 풀 수 있을 가능이 높다.
• 문제 유형을 암기한다고 해서 항상 잘 풀 수 있는 알고리즘 유형이 아니다!
• 창의력, 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
• 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이 출제된다!

대표적인 그리디 알고리 예제: 거스름돈 문제

거스름돈이 500원, 100원, 50원, 10원 짜리 동전이 무한히 존재한 가정 할때 손님에게 거슬러 줘야 할 돈이 n원일때 거슬러 줘야 할 동전의 최소 개수를 구하자. (단 n은 항상 10의 배수)

ex) n을 1260을 거슬러 줘야한다고 생각해보자!

500원 2개, 100원 2개, 50원 1개, 10원 1로 총 6개의 동전을 거슬러 줘야한다.

즉 가장 큰 화 단위부터 돈을 거슬러 주는 것 이다!

n = int(input())
coin = [500,100,50,10]
count = 0 #거스름돈의 갯수

for i in coin: #500원 짜리 동전부터 계산
		count += (n//i) #사용한 동전 갯수 만큼 더해준다.
		n %= i #연산 후 남은 금액

print(count)

이 문제는 큰 단위의 화폐가 작은 단위의 배수 형태 이므로 가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하여 거슬러 주는 작업만을 수행하면 되므로 이 아이디어는 정당하다!