[python] 탐욕 알고리즘의 예시
탐욕 알고리즘(Greedy Algorithm)은 최적해를 구하기 위해 각 단계에서 가장 최적인 선택을 하는 알고리즘입니다. 이러한 알고리즘은 현재의 선택이 전체적인 해답에 대한 최적해가 되도록 합니다.
다음은 탐욕 알고리즘의 예시인 “동전 거스름돈 문제”를 파이썬 코드로 구현한 것입니다.
def give_change(amount, coins):
change = []
coins.sort(reverse=True) # 동전들을 내림차순으로 정렬
for coin in coins:
while coin <= amount: # 현재 동전이 거스름돈으로 사용될 수 있는 경우
change.append(coin) # 해당 동전을 거스름돈에 추가
amount -= coin # 사용된 동전만큼 거스름돈에서 차감
return change
amount = 1260 # 거스름돈으로 주어진 금액
coins = [500, 100, 50, 10] # 동전의 종류
result = give_change(amount, coins)
print(result) # 출력 결과: [500, 500, 100, 100, 50, 10]
위 코드는 1260원의 동전 거스름돈을 주어진 500원, 100원, 50원, 10원 동전으로 줄일 수 있는 최소 동전 개수를 구하는 예시입니다. 탐욕 알고리즘을 사용하여 현재까지 가장 큰 동전부터 순서대로 사용하면서 거스름돈을 줄여갑니다.
이번 예시에서는 동전의 종류와 금액이 고정되어 있지만, 탐욕 알고리즘은 다양한 문제에 적용될 수 있습니다.
참고자료: