탐욕 알고리즘 (Greedy Algorithm)

그리디(탐욕) 알고리즘

: 그리디 알고리즘은 동적 프로그래밍(Dynamic Programming) 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. 여러 경우 중 하나를 결정해야할 때마다 각 단계에서 가장 최선의 선택을 하는 기법으로 이 선택이 전체적으로도 최선이기를 바란다고 볼 수 있다.

! 항상 최적의 답을 구해주지는 않음 !

 

-> 그리디 알고리즘은 주로 정렬 알고리즘과 짝을 이뤄 출제되는데 "가장 큰 or 작은 순서대로"라는 기준을 제시해줌.

* 최단 경로를 빠르게 찾아야 하는 문제 = 플로이드 워셜 or 다익스트라 알고리즘

 

 

 

출처 : https://en.wikipedia.org/wiki/Greedy_algorithm

 

 

 

 

대표적인 그리디 문제

: 거스름돈 문제

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

 

문제 해결 방법 = "가장 큰 단위부터 거슬러 주는 것"

동전의 개수가 최소여야 거슬러주어야 할 횟수가 최소라는 뜻!!!

 

 

 

소스코드

N = int(input())
# 손님에게 거슬러주어야 할 돈 N원 입력받기

coin = [500, 10, 50, 100]
# 500원,100원,50원,10원 동전이 무한히 존재

coin.sort(reverse=True)
# 값이 가장 큰 동전부터 써서 거슬러주어야 최소 횟수를 구할 수 있으므로 내림차순 정렬

count = 0
# 거슬러주어야 할 동전의 개수(최소 횟수)를 카운트하기 위해 선언

for i in coin:  
    count += N // i
    # N원을 리스트 coin의 i번째 요소로 나눈 몫(=거슬러줄 때 필요한 동전의 개수)을 count에 누적해서 저장
    
    N %= i
    # N원을 i번째 요소로 나눈 나머지를 다시 N에 저장.
    # -> 이미 위에서 거슬러준 후 남은 값을 가지고 다시 위의 과정 반복

print(count)