Greedy Algorithm - Theory

※"이것이 코딩 테스트다"의 저자인 나동빈 님의 유튜브 강의를 보고 학습을 위해 정리한 글입니다.

 

개요

• 그리디 알고리즘을 쉽게 생각해보면 현재 상황에서 가장 좋은 것만 고르는 방법을 뜻한다.
• 그리디 알고리즘의 정의는 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식이다.

일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다고 한다.  그렇지만 코딩 테스트에서의 대부분의 그리디 문제는 그리디 알고리즘으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제된다고 한다. - 동빈 나-

예제

그리디 알고리즘의 대표적인 예시로는 거스름돈 예제가 있다. 

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

풀이

• 가장 큰 단위의 화폐를 줄 수 있는 만큼 주고, 화폐의 단위를 낮춰가면서 거스름돈을 준비하면 최소 개수의 동전을 줄 수 있다.
• 위와 같은 이유는 동전의 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문입니다.
  • 예를 들어 화폐 단위가 [500, 400, 100]이라면 800을 거슬러 주어야 할 때 위와 같은 해법으로 접근한다면 500원짜리 1개, 100원짜리 3개로 최소 개수인 400원 두 개 보다 더 거슬러 주기 때문이다.

이처럼 그리디 알고리즘 문제는 문제풀이를 위한 최소한의 아이디어를 통해 정상성 여부를 확인해야 한다.

코드

파이썬을 이용한 풀이법이다.

n = ~~ // 돈
Count = 0 // 몇 개의 동전을 주었나 확인하는 변수

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

    for coin in Change:
        Count += value //개수 확인
        x %= coin

print(Count)