[이코테] 3. 그리디 알고리즘 - 거스름 돈

 

 

 

그리디 알고리즘 - 거스름 돈

 

 

문제 설명

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

 

 

 

문제 해결 아이디어

" 가장 큰 화폐 단위 부터 " 돈을 거슬러 주면 됨. (최적의 해)

• N원 거슬러 줘야 할 때 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 줌.
  
  • 이후에 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줌.

 

 

 

정당성 분석

가장 큰 화폐 단위부터 거슬러 주는 것이 최적의 해가 되는 이유는?

 : 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로..!

 

만약 800원 거슬러 줘야하는데, 화폐 단위가 500, 400, 100이라면,

최적의 해는 400원 2개.

즉, 큰 단위가 항상 작은 단위의 배수가 아니므로 '그리디 알고리즘'으로 풀면 틀리는 문제임.

 

위 처럼, 그리디 알고리즘 문제에서는

1. 문제 풀이를 위한 최소한의 아이디어를 떠올리고
2. 이것이 정당한지 검토

할 수 있어야됨.

 

 

 

소스 코드

n = int(input())

# 큰 단위 화폐부터 차례대로 확인하기 위해서 리스트 순서 500부터.
coins = [500, 100, 50, 10]
count = 0

for i in coins:
    count += n // i # 몫을 구해서 동전 개수 구하기
    n %= i # 나머지를 구해서 남은 돈 최신화

print(count)

 

화폐의 종류가 K라고 할 때, 소스 코드의 시간 복잡도는 O(K)임.

이 알고리즘의 시간 복잡도는 거슬러 줘야 하는 금액과는 무관하며, 동전의 총 종류에만 영향을 받음.

 

 

 

 

 

 

 

이코테 2021 시리즈 씹어먹기 by 조랭이떡

시리즈 목차

1. 코딩테스트 출제 경향 및 알고리즘 성능 평가
2. 파이썬 문법 부수기
   1. 수, 리스트 자료형
   2. 문자열, 튜플, 사전, 집합 자료형
   3. 기본 입출력
   4. 조건문
   5. 반복문
   6. 함수와 람다 표현식
   7. 자주 사용되는 표준 라이브러리
3. 그리디
   1. 그리디 알고리즘이란?
   2. 거스름돈
   3. 1이 될 때 까지
   4. 곱하기 혹은 더하기
   5. 모험가 길드
4. 구현
5. DFS & BFS (추후링크)
6. 정렬 알고리즘 (추후링크)
7. 이진 탐색 (추후링크)
8. 다이나믹 프로그래밍 (추후링크)
9. 최단 경로 알고리즘 (추후링크)
10. 기타 그래프 이론 (추후링크)
11. 코딩 테스트에서 자주 출제되는 기타 알고리즘 (추후링크)
12. 개발형 코딩 테스트 (추후링크)