스위프트 코딩테스트 강좌, 동전 개수의 최솟값 구하기

문제 정의

주어진 동전의 종류와 금액이 있을 때, 해당 금액을 만들기 위해 필요한 동전의 개수를 최소화하는
알고리즘 문제를 다루겠습니다. 예를 들어, 동전의 종류가
[1, 5, 10, 25]이고 금액이 7일 때,
필요한 동전의 개수는 3개입니다(5 + 1 + 1).

입력

• 동전의 종류를 담고 있는 배열 coins (int[] 형태).
• 목표 금액 amount (int 형태).

출력

최소 동전 개수를 리턴합니다. 불가능할 경우 -1을 리턴합니다.

문제 접근 방식

이 문제는 동적 프로그래밍(Dynamic Programming)이라는 접근 방식을 사용할 수 있습니다.
목표는 주어진 금액을 만들기 위해 동전을 반복적으로 사용하여 최소한의 수를 찾는 것입니다.
동적 프로그래밍을 사용하여 최적 부분구조와 중복 하위 문제의 성질을 활용합니다.

단계1: DP 테이블 초기화

먼저, 배열 dp를 생성하여 각 인덱스 i에 대해 최소 동전 개수를 저장합니다.
dp[0]은 0으로 초기화하고, 나머지는 무한으로 초기화합니다.

단계2: DP 테이블 갱신

각 동전에 대해 반복문을 돌며, 해당 동전으로 만들 수 있는 금액을 업데이트합니다.
각 금액 i는 이전 금액 i - coin에서
+1을 해 주어 동전 개수를 갱신합니다.

스위프트 코드 구현

            func minCoins(coins: [Int], amount: Int) -> Int {
                // DP 테이블 초기화
                var dp = Array(repeating: Int.max, count: amount + 1)
                dp[0] = 0

                // DP 테이블 갱신
                for coin in coins {
                    for i in coin...(amount) {
                        if dp[i - coin] != Int.max {
                            dp[i] = min(dp[i], dp[i - coin] + 1)
                        }
                    }
                }

                return dp[amount] == Int.max ? -1 : dp[amount]
            }

            // 사용 예시
            let coins = [1, 5, 10, 25]
            let amount = 7
            let result = minCoins(coins: coins, amount: amount)
            print("최소 동전 개수: \(result)")
        

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(m * n)입니다.
여기서 m은 동전의 종류 수, n은 목표 금액입니다.
외부 루프가 동전의 종류를 순회하고, 내부 루프가 목표 금액을 순회하게 되므로
두 개의 루프가 중첩되기 때문입니다.

추가 문제와 변형

이 문제를 변형하여 다양한 요구사항을 추가할 수 있습니다.
예를 들어, 특정 동전만 사용해야 하거나, 동전을 여러 번 사용할 수 없는 경우 등의 변형이 있을 수 있습니다.
이러한 변형에 대해서도 관심을 가져볼 필요가 있습니다.