[알고리즘 유형 / Python] 그리디 이론

그리디(Greedy) 알고리즘은 지금 이 순간, 지금 당장, 최적의 답을 찾는 방법이라고 한다.

지금 당장에서는 최적의 방법이지만 나중과 종합적으로 봤을 때는 최적이 아닐 수 있다.

욕심쟁이 알고리즘, 탐욕법 등의 이름으로 불린다.

 

그리디 알고리즘으로 풀어야하는 대표적인 문제 유형으로는

• 거스름돈
• 활동 선택 문제
• 최소 신장 트리

등등의 유형들이 있다.

 

거스름돈

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

거스름돈 유형에서는 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 포인트다.

거슬러 줘야 할 N원은 제일 먼저 500원, 그다음으로 100원, 50원, 10원 차례대로 거슬러 주면 최소의 동전 개수로 거슬러 줄 수 있다.

n = 1260
count = 0

coin_type = [500, 100, 50, 10]

for coin in coin_type:
    count += n // coin
    n %= coin
print(count)

1260원을 거슬러 줘야 할 때를 예시로 들었다.

count는 동전의 개수를 나타낸다.

coin_type에는 동전의 단위가 큰 500원부터 순차적으로 들어있다.

for문으로 coin_type 차례대로 500원부터 coin이라는 변수로 사용한다.

 

첫 번째 루프에서 1260원을 500원으로 나눈 몫(500원 짜리 동전의 개수)을 count에 대입한다.

그리고 1260원을 500원으로 나눈 나머지(500원 짜리를 거슬러 주고 남은 돈)를 다시 n에 대입한다.

 

이렇게 coin_type에 있는 모든 동전 단위를 차례대로 계산하여 최소의 동전 개수를 구하는 문제 유형이다.

 

그리디 알고리즘의 정당성

대부분의 알고리즘 문제는 그리디 알고리즘의 방법을 이용했을 때 최적의 답을 찾을 수 없는 경우가 많다.

거스름돈 유형의 경우 가장 큰 단위부터라는 매우 직관적이고 단순한 접근이 가능할 땐 그리디 알고리즘의 방법이 효과적이라고 할 수 있다.

 

그리디 알고리즘으로 답을 찾을 때는 그 방법이 정당한지에 대한 확실한 점검이 필요하다.

 

 

출처

http://www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24