python - 그리디(Greedy)

그리디

Greedy의 사전적 의미는 '탐욕스러운'이라는 뜻입니다. 그리디 알고리즘은 그 이름에 알맞게 탐욕적인 알고리즘입니다.

그리디 알고리즘은 현제 상황에서 가장 최적의 해를 찾습니다.

위 그림에서 돈을 가장 많이 얻을 수 있는 루트는 천원 먹고 100만 원 먹는 거지만 그리디 알고리즘은 현제 상황에서의 최적의 해를 찾기 때문에 만원과 천원중 만원을 고르고 10만 원과 20만 원 중 20만 원을 골라 21만 원을 얻습니다. 즉 그리디 알고리즘은 다음 상황은 생각하지 않는 거죠.

 

그리디 알고리즘 예시로 간단한 문제 하나를 풀어보겠습니다.

동전으로 거스름돈을 줄 때 동전을 최소의 개수로 주려면 몇 개의 동전을 줘야 하는지 물어보는 문제입니다.

print("거슬러줄 돈을 입력하세요.")
money = int(input())
coin = 0
coinlist = [500, 100, 50, 10]
for i in coinlist:
    if money >= i:
        coin = coin + money // i
        money = money % i
print(coin)

변수 및 리스트 설명

money : 거슬러줄 돈

coin : 줄 동전 개수

coinlist : 동전 종류

 

코드 설명

for 문에 coinlist를 넣어서 동전의 종류 개수만큼 반복

첫 번째 반복에서는 i가 500 if money >= i 거슬러줄 돈이 500(i) 보다 크면 if문 안에 있는 코드 실행

coin 에는 coin + money // i를 대입한다. 기존 코인 개수 + money를 i로 나눈 몫(a // b a를 b로 나눈 몫을 뜻한다.)

money 에는 money % i 를 대입한다. money 를 i로 나눈 나머지를 대입하는 것이다.

다음 반복에는 i 가 100이 되고 똑같이 반복하여 최종적으로 총 동 전수인 coin을 print 한다.