[그리디 알고리즘] 문제 - 거스름돈

해당 내용은 아래의 유투브를 보고 참고했음을 밝힙니다~

https://youtu.be/2zjoKjt97vQ?si=fGChNeo644FV1sFd

 

<문제> 거스름돈

출처: 동빈나 youtube

• 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유?
  • 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문
• 만약 800원을 거슬러줘야 하는데 화폐 단위가 500, 400, 100원이라면?
  • 문제 풀이를 위한 최소한의 아이디어를 떠올리고 정당한지 검토해야 함. 

# <문제> 거스름돈
#%%
n = 1260
count = 0
# 큰 단위부터 차례로
array = [500, 100, 50, 10]

for coin in array:
    count += n // coin  # 해당 화폐로 거슬러줄 수 있는 동전 개수
    n %= coin

print(count)  # 전체 동전의 개수
#%% md
* 동빈나님 유투브에 풀어주신 코드
* 좀 더 직관적인 코드를 위해서 chatgpt로 리팩토링을 시행했다.
#%%
amount = 1260
coins = [500, 100, 50, 10]
total = 0 
count = 0

for coin in coins:
    count, amount = divmod(amount, coin)
    total += count

print(total)

#%% md
* 이런 식으로 divmod를 사용할 수는 있는데 어차피 total 코드를 불러와야 하는 거면 비슷해보이긴 한다. 
* 그래도 8ms -> 4ms로 초가 줄었으니 조금은 더 나은 코드일지도?
* divmod라는 함수 예전에 배운 것 같은데 한 번 더 알아간다..
#%% md

<문제> 거스름돈: 시간복잡도 분석

• 화폐의 종류가 K라고 할 때, 소스코드의 시간 복잡도는 O(K)
• 이 알고리즘의 시간 복잡도는 거슬러줘야 하는 금액과 무관하며, 동전의 총 종류에만 영향을 받음.