파이썬 코딩테스트 강좌, 그리디 알고리즘

문제 설명

오늘 다룰 문제는 동전 거스름돈 문제입니다. 이 문제는 우리가 현실에서 자주 접하는 다양한 동전을 이용해 특정 금액을 만들 때, 가장 적은 수의 동전을 사용하는 방법을 찾는 것입니다.

문제 정의

다음과 같은 조건을 만족하는 함수 min_coins(coins, amount)를 작성하시오:

• coins: 사용 가능한 동전의 목록 (예: [1, 5, 10, 25])
• amount: 만들고자 하는 금액

이 함수는 주어진 금액을 만들기 위해 필요한 최소 동전의 수를 반환해야 합니다. 동전을 사용할 수 없는 경우에는 -1을 반환합니다.

문제 이해하기

문제를 좀 더 깊이 있게 이해하기 위해 몇 가지 예제를 살펴보겠습니다.

접근 방법

이 문제를 해결하기 위해 그리디 알고리즘을 사용하겠습니다. 그리디 알고리즘은 현재 상황에서 가장 최적인 선택을 하는 방식으로 동작합니다. 따라서, 우리는 가장 큰 동전부터 차례대로 사용하여 목표 금액을 만드는 방법을 모색하려 합니다.

해당 알고리즘의 구체적인 단계는 다음과 같습니다:

1. 사용 가능한 동전들을 내림차순으로 정렬합니다.
2. 현재 금액을 동전과 비교하여 가능한 한 많은 동전을 사용합니다.
3. 남은 금액이 0이 될 때까지 이 과정을 반복합니다.
4. 남은 금액이 0이 되었을 경우 동전의 개수를 반환하고, 그렇지 않을 경우 -1을 반환합니다.

코드 구현

그럼 이 접근 방법을 바탕으로 코드를 작성해보겠습니다:

def min_coins(coins, amount):
    # 동전을 내림차순으로 정렬
    coins.sort(reverse=True)
    
    count = 0  # 사용한 동전의 수
    
    for coin in coins:
        # 현재 동전이 amount보다 큰 경우 무시
        while amount >= coin:
            amount -= coin  # 동전의 가치를 amount에서 빼기
            count += 1  # 동전 개수 증가
            
    # 최종적으로 amount가 0인지 확인
    return count if amount == 0 else -1
    

테스트

이제 작성한 함수를 테스트해보겠습니다.

# 테스트 케이스
print(min_coins([1, 5, 10, 25], 63))  # 6
print(min_coins([2, 4], 5))             # -1
print(min_coins([5, 2, 1], 11))         # 3 (5 + 5 + 1)
    

결론

이러한 방식으로 그리디 알고리즘을 사용하여 동전 거스름돈 문제를 해결할 수 있었습니다. 이 문제를 통해 그리디 알고리즘의 기초적인 접근 방식을 익히고, 코딩 테스트에서 흔히 나오는 문제 유형을 공부했습니다.

앞으로 더 많은 문제를 연습하며 그리디 알고리즘에 대한 이해를 깊이게 쌓아가길 바랍니다. 위의 문제와 같이, 데이터를 어떻게 정렬하고, 반복문을 활용하여 해결책을 찾아나가는지에 대한 연습이 필요합니다. 그리디 알고리즘은 다양한 문제 해결에 유용한 도구가 될 수 있습니다.

감사합니다!