그리디 알고리즘(Greedy algorithm)이란?

Goal

1. 그리디 알고리즘에 대해 알아보기
2. 예시 문제 풀어보기

 

그리디 알고리즘이란?

그리디(Greedy)란 단어는 탐욕이란 뜻을 가지고 있다.

 

그래서 그냥 쉽게 생각해서 코딩 문제를 풀 때 욕심쟁이처럼 지금 현재 가장 좋은 선택, 가장 최적의 선택만 하면 된다! 나중에 어떻게 되든간에 일단은 제일 최선의 선택을 계속 해나가면서 전체적으로도 그냥 최적의 선택이었기를 바라는 것이다.

그리디한 다람쥐

 

예제 문제 (백준 5585번)

잔돈을 주는데 거스름돈 개수가 가장 적에 만들어보는 문제이다. 잔돈으로는 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 무한개가 있다고 생각하면 된다.

 

Hint

1. 개수가 가장 적으려면 금액이 큰거부터 주면 될까 작은거부터 주면 될까?

 

해결

# 문제에서 준 입력값은 내야할 금액이므로 1000엔 지폐를 한장 줬을 때 받을 잔돈부터 계산해야 한다.
change = 1000 - int(input())

en = [500, 100, 50, 10, 5, 1]
count = 0
# 큰 금액부터 채워나가면 된다.
for coin in en:
    if coin > change:
        continue
    
    count += change // coin     # 코인 개수 구하기
    change %= coin              # 코인 주고 남은 나머지 금액 구하기

    # 더이상 낼 금액이 없으면 멈춰!
    if change == 0:
        break

# 잔돈 개수 반환
print(count)

 

그리디 알고리즘을 적용해 큰 금액부터 우선적으로 채워나가다보면 가장 적은 개수의 잔돈을 구할 수 있다.