코딩 테스트 대비! 파이썬으로 탐욕 알고리즘(Greedy) 기법 구현하기

파이썬으로 탐욕 알고리즘(Greedy) 기법 구현하기


문제 설명

주어진 동전들을 이용하여 특정 금액을 최소 동전 개수로 거슬러 주는 문제를 탐욕 알고리즘으로 해결하세요.


예시 입출력

입력: 금액 = 23, 동전 종류 = [1, 5, 10]
출력: 5 (동전 개수)

솔루션 코드

def min_coins(amount, coins):
    coins.sort(reverse=True)
    count = 0

    for coin in coins:
        count += amount // coin
        amount %= coin

    return count

# 테스트 케이스
print("최소 동전 개수:", min_coins(23, [1, 5, 10]))
print("최소 동전 개수:", min_coins(92, [1, 5, 10, 25]))

코드 설명

이 포스팅에서는 탐욕 알고리즘(Greedy Algorithm) 기법을 활용하여 최소 동전 개수 문제를 해결했습니다. 탐욕 알고리즘은 매 단계에서 가장 좋아 보이는 선택을 하며 전체 문제를 해결하는 기법입니다. 코딩 테스트와 실무에서 자주 사용되므로 반드시 학습해야 합니다.

최소 동전 개수 문제는 주어진 금액을 동전들의 합으로 표현할 때, 최소 동전 개수를 찾는 문제입니다. 이 문제를 탐욕 알고리즘으로 해결할 수 있습니다.

1. 동전들을 내림차순으로 정렬합니다.
2. 가장 큰 동전부터 시작하여 현재 금액에서 최대한 많이 거슬러 줄 수 있는 동전의 개수를 계산합니다.
3. 거슬러 준 동전의 가치를 금액에서 제거합니다.
4. 2, 3 과정을 반복하여 금액이 0이 될 때까지 진행합니다.

코드에서는 `min_coins` 함수에서 탐욕 알고리즘을 구현했습니다. 먼저 동전들을 내림차순으로 정렬합니다. 그리고 각 동전에 대해 현재 금액에서 최대한 많이 거슬러 줄 수 있는 개수를 계산하고, 그 동전의 가치를 금액에서 제거합니다. 이 과정을 반복하면 최소 동전 개수로 금액을 거슬러 줄 수 있습니다.

탐욕 알고리즘은 매 단계에서 가장 좋아 보이는 선택을 하므로, 전체 문제를 최적으로 해결할 수 있다는 보장은 없습니다. 하지만 일부 문제에서는 탐욕 알고리즘이 최적의 해를 구할 수 있습니다. 이러한 경우, 일반적으로 시간 복잡도가 낮아 효율적인 알고리즘을 설계할 수 있습니다.

탐욕 알고리즘은 활동 선택 문제, 프래그 압축, 최단 경로 찾기 등 다양한 분야에서 활용됩니다. 따라서 이 기법을 잘 익히면 복잡한 문제도 효과적으로 해결할 수 있습니다. 또한 코딩 테스트에서 자주 출제되므로 반드시 학습해야 할 주제입니다.