[작성자:] root

문제 정의

주어진 동전의 종류와 금액이 있을 때, 해당 금액을 만들기 위해 필요한 동전의 개수를 최소화하는
알고리즘 문제를 다루겠습니다. 예를 들어, 동전의 종류가
[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은 목표 금액입니다.
외부 루프가 동전의 종류를 순회하고, 내부 루프가 목표 금액을 순회하게 되므로
두 개의 루프가 중첩되기 때문입니다.

추가 문제와 변형

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

동적 계획법의 기초

동적 계획법은 주어진 문제를 최적 부분 구조에 따라 나누어 해결하는 방식입니다.
기본적으로 두 가지 주요 요소가 있습니다: 메모이제이션(Memoization)과 타뷸레이션(Tabulation).
메모이제이션은 재귀적으로 풀어진 문제의 결과를 저장하여 중복 계산을 피하는 방법이고,
타뷸레이션은 하위 문제의 결과를 테이블에 저장하여 바텀 업 방식으로 문제를 해결하는 것입니다.

문제 소개: 피보나치 수열

피보나치 수열은 자연수의 수열로, 처음 두 개의 항이 0과 1이며,
그 이후의 항은 바로 앞의 두 항을 더한 값으로 정의됩니다.
즉, F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n >= 2)입니다.

피보나치 수열을 계산하는 효율적인 방법을 구현하면서 동적 계획법의 개념을 이해해봅시다.

문제 풀이 과정

1. 문제 파악하기

피보나치 수열의 n번째 항을 구하는 문제입니다.
간단한 정의는 있지만, 재귀적 방법으로 구현할 경우 중복 계산이 발생하여 비효율적입니다.

2. 동적 계획법 적용

동적 계획법을 사용하면 중복 계산을 피할 수 있습니다.
특히 하위 문제에서 이미 계산된 결과를 저장하고 재사용함으로써 시간 복잡도를 줄일 수 있습니다.
여기서는 메모이제이션 방식을 사용하여 문제를 해결하겠습니다.

3. 메모이제이션 구현

메모이제이션은 재귀 함수에 추가적인 변수를 사용하여 이전에 계산한 결과를 저장하는 방식입니다.
스위프트로 코드를 작성해 보겠습니다.

            
                func fibonacci(_ n: Int, _ memo: inout [Int?]) -> Int {
                    if let value = memo[n] {
                        return value
                    }
                    if n <= 1 {
                        memo[n] = n
                        return n
                    }
                    memo[n] = fibonacci(n - 1, &memo) + fibonacci(n - 2, &memo)
                    return memo[n]!
                }
                
                func fibonacciWrapper(n: Int) -> Int {
                    var memo = Array(repeating: nil, count: n + 1)
                    return fibonacci(n, &memo)
                }
                
                // 호출 예
                let result = fibonacciWrapper(n: 10)
                print(result) // 출력: 55
            
        

4. 시간 복잡도 분석

메모이제이션을 사용한 피보나치 수열의 시간 복잡도는 O(n)입니다.
각 n에 대해 한 번만 계산하고 결과를 저장하므로 효율적인 성능을 보여줍니다.
공간 복잡도 역시 O(n)입니다.

5. 타뷸레이션 방법으로 구현하기

이번에는 타뷸레이션 방법을 사용하여 동일한 문제를 해결해보겠습니다.
이 방법은 하위 문제의 결과를 테이블에 저장하여 바텀업 방식으로 접근합니다.
스위프트로 코드를 작성해 보겠습니다.

            
                func fibonacciTabulation(_ n: Int) -> Int {
                    if n <= 1 { return n }
                    var dp = Array(repeating: 0, count: n + 1)
                    dp[0] = 0
                    dp[1] = 1
                    
                    for i in 2...n {
                        dp[i] = dp[i - 1] + dp[i - 2]
                    }
                    return dp[n]
                }
                
                // 호출 예
                let resultTabulation = fibonacciTabulation(n: 10)
                print(resultTabulation) // 출력: 55
            
        

6. 결론

이번 글에서는 스위프트를 사용하여 동적 계획법의 기본 개념을 배우고,
피보나치 수열 문제를 통해 메모이제이션과 타뷸레이션 기법을 실습해 보았습니다.
동적 계획법은 다양한 알고리즘 문제에서 활용될 수 있는 강력한 도구이며,
이론을 잘 이해하고 활용하는 것이 코딩 테스트에서도 큰 도움이 될 것입니다.