반응형
250x250
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- 개인프로필스튜디오창업
- 계정계
- union
- 코어뱅킹
- 렌탈스튜디오창업
- 맥북환경설정
- DB
- 채널계
- 컴퓨터공학학사취득
- 프로그래머스
- Pass By Value
- 은행IT
- SQL
- fastapi
- jdk17
- it자격증
- jdk
- 인강빨리듣기
- oracleapex
- 디렉토리계층구조
- Homebrew
- python
- 학점은행제
- 코딩테스트
- 모놀리식
- 학점은행제무료강의
- 맥북
- 오라클
- MSA
- 맥북셋팅
Archives
- Today
- Total
개발머해니
[파이썬] 최소 동전으로 거슬러 주기 - 그리디 본문
728x90
반응형
실습 설명
최소 동전으로 돈을 거슬러 주는 함수를 Greedy Algorithm으로 구현해 보겠습니다.
우리가 작성할 함수 min_coin_count는 거슬러 줘야 하는 총액 value와 동전 리스트 coin_list를 파라미터로 받고, 거슬러 주기 위해 필요한 최소 동전 개수를 리턴합니다.
예를 들어 1170원을 거슬러 주기 위해서는 500원 2개, 100원 1개, 50원 1개, 10원 2개를 줄 수 있기 때문에 6을 리턴하면 되겠죠?
동전의 조합은 항상 500원, 100원, 50원, 10원이라고 가정합시다.
실습 결과
def min_coin_count(value, coin_list):
# 누적 동전 개수
count = 0
# coin_list의 값들을 큰 순서대로 본다
for coin in sorted(coin_list, reverse=True):
# 현재 동전으로 몇 개 거슬러 줄 수 있는지 확인한다
count += (value // coin)
# 잔액을 계산한다
value %= coin
return count
# 테스트 코드
default_coin_list = [100, 500, 10, 50]
print(min_coin_count(1440, default_coin_list))
print(min_coin_count(1700, default_coin_list))
print(min_coin_count(23520, default_coin_list))
print(min_coin_count(32590, default_coin_list))
10
5
49
70
오답
- 리스트의 정렬
coin_list.sort(reverse=True) #리스트가 내림차순으로 정렬
coin_list.sort() #리스트가 오름차순으로 정렬
- 리스트 정렬+반복문 = 한 번에 가능
for coin in sorted(coin_list, reverse=True):
728x90
반응형
'알고리즘' 카테고리의 다른 글
[파이썬] 지각 벌금 적게 내기 분석 - 그리디 (0) | 2023.09.30 |
---|---|
[파이썬] 최대 곱 구하기 - 그리디 (0) | 2023.09.24 |
[파이썬] 새꼼달꼼 장사 (2) Tabulation - 다이나믹 프로그래밍 ★ (0) | 2023.09.19 |
[파이썬] 새꼼달꼼 장사 (1) Memoization - 다이나믹 프로그래밍 ★ (0) | 2023.09.19 |
[파이썬] 피보나치 수열 (3) 공간 최적화 - 다이나믹 프로그래밍 ★ (0) | 2023.09.18 |