[그리디] 당장 좋은 것만 선택하는 그리디 - 거스름돈 예제

그리디 알고리즘이란,

현재 상황에서 지금 당장 좋은 것만 고르는 방법. 

매순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

 

최단경로문제는, 플로이드 워셜 혹은 다익스트라 알고리즘 과 같은 알고리즘을 미리 알고 있어야 가능하다.

 

*플로이드 워셜(Floyd Warshall)

 : 변의 가중치가 음이거나 양인 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이을 찾는다

*다익스트라(Dijkstra) 알고리즘

: 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘

위 알고리즘에 대해서는 추후 더 공부해보겠다.

 

보통 코딩테스트에서 출제되는 그리디 알고리즘 유형의 문제는

창의력,

즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

 

- 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장큰 순서대로' '가장 작은 순서대로' 등 기준을 알게모르게 제시해준다.

* 대체로 정렬 알고리즘과 짝을 이뤄 출제된다.

 

예제 3-1 거스름돈

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

 

[해설]

• 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐의 단위부터 돈을 거슬러 주면 됩니다.

[소스코드]

# 거스름돈이 1260원이라면
n =1260 

# 거슬러 줄 동전의 개수
count  = 0 

# 화폐의 종류
array = [500,100,50,10]

# 큰 화폐부터 줄 수 있는 만큼 주고 나머지는 다음 큰 화폐로 반복
for coin in array:
    count += n / coin
    n %= coin 

print(count)

 

그리디 알고리즘의 정당성

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

 

대부분의 그리디 알고리즘 문제는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출 할 수 있다. 

처음에 문제를 만났을때에는 다양한 아이디어를 생각해보고, 문제점을 인식하게되면 또다른 풀이 방법을 생각해보며

최적의 해를 구하기 위한 방법에 도달 할 때까지 방법을 떠올려야한다.