초보 기술블로그

 '그리디(greedy) 알고리즘'은 '현재 상황에서 가장 좋은 것을 고르는' 알고리즘이다.

문제에서 '가장 큰 순서대로', '가장 작은 순서대로'라는 말이 나오면 그리디 알고리즘을 고민해 볼 필요가 있다.

가장 대표적인 문제로는 '거스름돈' 문제를 들 수 있다.

'거스름돈' 문제는 간략하게

      무한히 많은 개수의 500원, 100원, 50원, 10원짜리 동전이 존재할 때 최소한의 동전 개수로 거스름돈을 주는 문제이다.

이를 그리디 알고리즘으로 접근하면 다음 코드처럼 작성할 수 있다.

n = int(input("총 금액은 얼마인가요"))
count = 0
coint_types=[500,100,50,10]
for coin in coin_types:
    count += n // coin    #현재 동전은 몇 개를 줄 수 있는지 카운트에 저장
    n%=coin                  #원래 금액에서 동전을 준 만큼은 빼고 금액을 저장
print(count)

 위 코드는 가장 큰 화폐 단위인 500원부터 가장 작은 화폐 단위인 10원까지 순차적으로 접근하는 방식으로 앞서 말했던 것처럼 '가장 큰 순서대로' 문제를 접근한 방식이다. 

다만, 문제를 조금 변형하여 500원, 100원, 50원, 10원이 아니라 500원, 400원, 100원인 경우를 생각해 보자.

이 경우는 800원을 거스름돈으로 주어야 할 때 그리디 알고리즘으로는 500+100+100+100으로 4개의 결괏값이 나오지만

사실 400원을 2개 주는 것이 최적값이라고 할 수 있다. 기존 문제를 그리디 알고리즘으로 풀 수 있었던 것은 

'큰 단위의 화폐가 항상 작은 단위의 배수 형태' 이므로 가능했다.

어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 만약 해답을 찾을 수 없다면 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지 고민해 볼 필요가 있다.