Iridescent Seraphim

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

접근 방법: 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제이다. 먼저 가장 큰 화폐 단위부터 돈을 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다. 예를 들어 1470원인 경우, 500원짜리 2개, 100원짜리 4개, 50원짜리 1개, 10원짜리 2개로 총 9개의 동전을 이용해 거슬러 줄 수 있다. 이를 파이썬으로 정리하면 아래와 같다.

n = 1470
count = 0
# 큰 단위 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]
for coin in coin_types:
  count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
  n %= coin
print(count)

그리디 알고리즘은 모든 알고리즘 문제에 적용되지 않으며, 대부분의 경우 최적의 답을 찾지 못할 수 있다. 그러나 거스름돈 문제와 같이 탐욕적으로 접근할 때 정확한 답을 찾을 수 있는 경우에는 매우 효과적이다. 예를 들어, 800원을 거슬러 줄 때 500원, 400원, 100원이 있다면 그리디 알고리즘은 500원 1개와 100원 3개를 제시하지만, 사실 400원 2개로 더 적은 동전으로도 답을 낼 수 있다.

∴ 따라서, 문제를 풀 때, 다양한 아이디어를 고려해보고, 바로 유형을 파악하기 어려울 땐 그리디 알고리즘을 의심한 뒤, 문제를 해결할 수 있는지 고민해보자. 이 과정에서 여러 가지 접근방식을 시도해보고, 각 접근이 가진 장단점을 분석하는 것이 중요하다. 그리고도 해결이 안되면 다이나믹 프로그래밍이나 그래프 알고리즘 등으로도 해결이 가능하다. 이러한 알고리즘들은 보다 복잡한 문제를 다루는데 효과적이며, 각 방법의 시간 복잡도와 공간 복잡도를 고려해야 최적의 솔루션을 찾을 수 있다. 문제를 해결하는 과정에서 다양한 방법을 실험하는 것이 결국 더 나은 이해를 돕고, 다음 문제를 맞닥뜨릴 때 더 효과적으로 접근할 수 있는 능력을 키울 것이다.