Greedy(탐욕) 알고리즘이다.
사실 이거를 공부할 때마다 드는 생각은 매 순간 가장 큰 이득을 가져다주는 것을 고르는 상황이 어떻게 알고리즘이지? 라는 생각이 든다.
def make_change_greedy(change, coins):
"""
문제 설명:
- 그리디(Greedy) 알고리즘으로 거스름돈을 계산합니다.
- 가장 큰 단위의 동전부터 사용하여 최소 개수로 거슬러줍니다.
그리디 알고리즘으로 거스름돈 계산
Args:
change: 거슬러줄 금액
coins: 동전 종류 리스트 (큰 순서)
Returns:
(총 개수, {동전: 개수} 딕셔너리)
"""
result = {}
total_coins = 0
for coin in coins:
if change == 0: break
result[coin] = 0
while coin <= change:
change -= coin
result[coin] += 1
total_coins += 1
if change == 0: break
del_list = []
for coin in result:
if result[coin] == 0:
del_list.append(coin)
for item in del_list:
del result[item]
return total_coins, result
# 테스트 케이스
if __name__ == "__main__":
# 테스트 케이스 1
change1 = 1260
coins1 = [500, 100, 50, 10]
total, details = make_change_greedy(change1, coins1)
print("=== 거스름돈 계산 ===")
print(f"거슬러줄 금액: {change1}원")
for coin, count in details.items():
print(f"{coin}원: {count}개")
print(f"총 {total}개")
print()
# 테스트 케이스 2
change2 = 4570
coins2 = [500, 100, 50, 10]
total, details = make_change_greedy(change2, coins2)
print("=== 거스름돈 계산 ===")
print(f"거슬러줄 금액: {change2}원")
for coin, count in details.items():
print(f"{coin}원: {count}개")
print(f"총 {total}개")
print()
# 테스트 케이스 3
change3 = 1000
coins3 = [500, 100, 50, 10]
total, details = make_change_greedy(change3, coins3)
print("=== 거스름돈 계산 ===")
print(f"거슬러줄 금액: {change3}원")
for coin, count in details.items():
print(f"{coin}원: {count}개")
print(f"총 {total}개")달성 목표
최소 개수의 동전을 사용하여 특정 목표 금액을 거슬러 줘야 한다.
동전의 개수와 금액은 반비례
사실 쉬운 문제이기 때문에 직관적으로 개수와 동전의 금액이 반비례 한다는 것이 직관적으로 드러난다.
그렇기에 500원 1개와 100원 5개가 있을 때 우리가 선택해야 하는 것이 무조건적으로 500원 1개이다.
지불 가능한 가장 큰 동전 고르기
이러한 식으로 개수를 기준으로 순간 최선의 선택은 지불 가능한 가장 큰 동전을 고르는 것이고 이러한 점을 그대로 구현하였다.
"""
[그리디 - 회의실 배정]
문제 설명:
- 하나의 회의실에 여러 회의를 배정합니다.
- 각 회의는 시작 시간과 종료 시간이 있습니다.
- 최대한 많은 회의를 배정하려고 합니다.
입력:
- meetings: [(시작, 종료), ...] 회의 리스트
출력:
- 배정된 회의 개수
예제:
입력: [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
출력: 4개
선택: [(1, 4), (5, 7), (8, 11), (12, 14)]
"""
def select_meetings(meetings):
"""
회의실 배정 (그리디)
Args:
meetings: [(시작, 종료)] 리스트
Returns:
(배정된 회의 개수, 선택된 회의 리스트)
"""
result = []
def check_meet(start, end):
if len(result) == 0:
result.append((start, end))
else:
if result[-1][1] <= start:
result.append((start, end))
asc = sorted(meetings, key=lambda x: x[1], reverse=False)
for meet in asc:
check_meet(meet[0], meet[1])
return len(result), result
if __name__ == "__main__":
meetings1 = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9)]
count1, selected1 = select_meetings(meetings1)
print("=== 테스트 케이스 1 ===")
print(f"전체 회의: {meetings1}")
print(f"배정된 회의 개수: {count1}개")
print(f"선택된 회의: {selected1}")
print()
meetings2 = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
count2, selected2 = select_meetings(meetings2)
print("=== 테스트 케이스 2 ===")
print(f"전체 회의: {len(meetings2)}개")
print(f"배정된 회의 개수: {count2}개")
print(f"선택된 회의: {selected2}")회의실을 가장 빨리 비워주는 선택
매번 회의 종료 시간이 이른 것이 좋은 선택이다. 이렇게 될 경우 뒤에 남은 회의 시간이 최대가 되며 많은 회의를 받을 수 있는 기회가 늘기 때문이다.
그렇기 때문에 회의 종료 시간을 기준으로 정렬을 하고 진행을 하였다
