스위프트 코딩테스트 강좌, 그리디 알고리즘

문제: 동전 거스름돈

상점에서 제공하는 동전의 종류가 주어졌을 때, 주어진 금액을 거슬러 주기 위한 최소한의 동전 개수를 구하는 문제입니다.

문제 설명:

• 입력: 동전의 종류와 거슬러 줄 금액이 주어진다.
• 출력: 최소한의 동전 개수

입력 예시:

동전의 종류: 1, 3, 4
금액: 6

출력 예시:

2 (3 + 3)

문제 해결 과정

1. 문제 분석

거슬러 줄 금액을 동전의 종류에 따라 최소한의 동전 개수로 표현하는 것이 이 문제의 핵심입니다. 가장 큰 동전부터 선택하는 방법이 효율적입니다.

2. 접근 방법

해결을 위해 사용할 기본적인 접근 방법은 다음과 같습니다.

1. 주어진 동전의 종류를 오름차순으로 정렬한다.
2. 가장 큰 동전부터 사용할 수 있는 만큼 사용한다.
3. 남은 금액에 대해 다시 위 과정을 반복한다.
4. 거슬러 주어야 할 금액이 0이 될 때까지 이 과정을 계속한다.

3. 알고리즘 구현 (Swift)

func minCoins(coins: [Int], amount: Int) -> Int {
    var remainingAmount = amount
    var coinCount = 0
    var sortedCoins = coins.sorted(by: { $0 > $1 }) // 내림차순 정렬
    
    for coin in sortedCoins {
        while remainingAmount >= coin {
            remainingAmount -= coin
            coinCount += 1
        }
    }
    return remainingAmount == 0 ? coinCount : -1 // 정확히 거슬러 주지 못할 경우 -1 반환
}

// 사용 예시
let coins = [1, 3, 4]
let amount = 6
let result = minCoins(coins: coins, amount: amount)
print("최소 동전 개수: \(result)")
            

위의 코드에서는 주어진 동전의 종류를 오름차순으로 정렬한 뒤, 가장 큰 동전부터 가능한 만큼 금액에서 차감하여 동전 개수를 세는 방식으로 문제를 해결합니다.

결과 분석

이 알고리즘의 시간 복잡도는 O(n log n)입니다. (n은 동전의 종류 개수) 이 문제는 그리디 알고리즘의 전형적인 예시로, 동전의 종류가 단조 증가하거나, 특정한 규칙성이 있을 경우 최적의 해를 보장합니다.

하지만, 모든 상황에서 그리디 알고리즘이 최적의 해를 보장하지는 않으므로 약간의 주의가 필요합니다. 특징적인 예로, 동전의 종류가 {1, 3, 4}일 때는 최적의 해를 찾을 수 있지만, {1, 3, 4, 6} 같이 동전의 종류가 추가되면 결과가 달라질 수 있습니다.