코딩테스트 - 그리드 알고리즘(Grid)

Grid = 탐욕적인 즉, 그리드 알고리즘은 탐욕적인 알고리즘이다.

 

탐욕적인 알고리즘은 "현재 주어진 상황에서 당장 좋은 혹은 도움되는 것만 고르는 방법"을 의미한다.

 

Grid알고리즘의 대표적인 문제로는 "거스름돈 문제"로 예를 들 수 있는데

 

<문제>

'거스름돈 문제'

 

카운터에 거스름돈이 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원 일때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

 

여기서,

 

그리드 알고리즘으로 위의 문제를 해결할 수 있다. 즉,

"현재 주어진 상황에서 당장 좋은 혹은 도움되는 것만 고르는 방법" = "가장 큰 화폐 단위부터 거슬러 주는 것"이라는 생각을 해야한다.

 

 

자, 받은 돈이 1260원 이라고 하자

 

step01

처음 가장 큰 단위인 500원으로 거슬러 줄 수 있는 동전의 개수는 1000원이다.

점원 = 260원

손님 = 1000원(500원 2개)

 

step02

점원 = 60원

손님 = 1200원(500원 2개, 100원 2개)

 

steop03

점원 = 10원

손님 = 1250원(500원 2개, 100원 2개, 50원 1개)

 

step04

점원 = 0원

손님 = 1260원(500원 2개, 100원 2개, 50원 1개, 10원 1개)

 

이렇게 최소 동전의 개수는 6개가 된다.

 

 

위에서 언급한 과정을 파이썬으로 구현해보면

 

 

n = 1260

coin_types = [500, 100, 50, 10]

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

다음과 같이 구형할 수 있다.

 

 

여기서 거스름 돈 문제를 그리디 알고리즘으로 해결 할 수 있는 이유는

가지고 있는 동전중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.