알고리즘 - 그리디(greedy)

*참고저서 - 나동빈 <이것이 취업을 위한 코딩 테스트다>

 

그리디는 한국어로 바꾸면 말 그대로 '탐욕스러운'이라는 뜻이다.

이름과 같이 이후 상황을 고려하지 않고 현재 상황에서 가장 좋은 것만 고르는 방법이다.

 

그리디의 경우 dfs/bfs/mst 문제들처럼 코드의 원형이 따로 없으며 아이디어의 형태로 존재한다.

해당 문제가 그리디로 해결 가능한지 판별하고 정답을 제공하는 접근법을 떠올리기까지가

그리디 문제의 핵심이라 할 수 있다.

 

여기서 보통 '~~한 순서로' 와 같은 접근법이 나오기에, 정렬에 대한 이해도 조금은 필요하다.

 

그리디 문제를 설명하는 대표 예제는 거스름돈 문제이다.

거슬러 줘야 할 돈 N원이 주어졌을 때, 500,100,50,10원 짜리 동전들을 이용해 거슬러 준다 하자.

이 때 동전의 최소 개수를 구하라.

 

가장 쉬운 예제답게 접근법 역시 간단하게 생각할 수 있다. 가장 큰 화폐부터 돈을 거슬러 주는 것이다.

500원 짜리를 최대한 사용한 경우의 동전 개수가 500원짜리를 덜 사용한 동전 개수보다 클 리가 없으니

이 접근방법은 항상 정답을 제공한다.

 

예제 코드는 다음과 같다.

 

n = int(input())

count = 0

coins = [500,100,50,10,]

for coin in coins:

  count += n // coin

  n %= coin


print(count)

 

그리디 알고리즘의 형태에 대한 대략적인 틀은 다음과 같이 일반화할 수 있다