[코딩테스트/Python]Greedy (탐욕법) 알고리즘

Greedy 알고리즘 개념 

• 단어 그대로 "탐욕법"으로 번역하여 소개되곤 함
• 탐욕적이라는 말의 의미: 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 다른 유형에 비해 개념과 코드를 암기해야하는 유형은 아님
• 코딩테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력(문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력) 요구
• 유형 파악 Tip: 단순히 현재 상황에서 가장 좋아보이는 것만을 선택해도 문제를 풀 수 있는지 확인 
• EX) 가장 큰 순서대로, 가장 작은 순서대로  
• 정렬 문제와 짝을 이뤄 출제되는 경우 많음

Greedy 알고리즘 예제: 거스름돈

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

 

책 풀이 없이 풀어보기 

import time
def change(n):
    start= time.time()
    cnt = 0
    li =[500,100,50,10]
    for i in li:
        cnt += n // i #몫: 동전 개수
        n %=  i 
    end=time.time()
    print("time:", end-start)
    return cnt

print(change(1260))

output

• 거스름돈 종류를 list에 담아두고 큰 동전부터 반복문 돌리기 
• // : 몫 반환 , %: 나머지 반환
• 몫은 동전 개수이므로 횟수에 더해주기 
• 앞에서 남은 돈은 다시 돌려주기

책에서 제시한 코드

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인하기
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin

print(count)

 

문제 풀이를 위한 최소한의 아이디어 떠올리기 -> 정당한지 검토하자

 

+) 백준 5585번도 거의 똑같은 문제다 

n = int(input())
li = [500,100,50,10,5,1]
cnt =0 
money = 1000-n
for i in li:
    cnt += money // i
    money %=  i 
print(cnt)

[reference]

도서 "이것이 코딩 테스트다" (https://github.com/ndb796/python-for-coding-test)