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

많은 개발자들이 코딩 테스트를 준비하면서 다양한 알고리즘 문제를 접하게 됩니다. 그 중에서도 ‘동전 개수의 최솟값 구하기’ 문제는 자주 등장하는 문제 중 하나입니다. 오늘은 이 문제를 해결하기 위해 필요한 이론, 알고리즘, 그리고 Java로 구현하는 방법까지 자세히 살펴보겠습니다.

문제 설명

주어진 동전의 종류와 목표 금액이 있을 때, 목표 금액을 만들기 위해 필요한 동전의 개수를 최소화하는 문제입니다. 특정 금액을 만들기 위해 각 동전의 개수를 최소화하는 방법을 찾아내야 합니다.

예를 들어, 다음과 같은 상황을 가정해보겠습니다:

동전의 종류: {1, 5, 10, 25}
목표 금액: 63

이 경우, 25원 동전 2개, 10원 동전 1개, 5원 동전 1개, 1원 동전 3개를 사용하여 총 4개의 동전으로 63원을 만들 수 있습니다.

입력 및 출력

입력:

n: 동전의 종류 수
coins[n]: 동전의 목록
amount: 목표 금액

출력: 목표 금액을 만들기 위한 동전의 최소 개수

동전을 이용해 목표 금액을 만들 수 없는 경우, -1을 반환합니다.

문제 해결 접근법

이 문제는 전형적인 동적 프로그래밍(Dynamic Programming) 문제로, 각 금액에 대해 최소 동전 개수를 계산하여 그것을 바탕으로 다음 단계의 금액을 계산해나가는 과정을 거칩니다.

단계별 접근법

초기화: 결과를 저장할 배열을 준비하고 초기 값으로 설정합니다.
바텀업 방식으로 동전의 종류를 반복문을 통해 처리합니다.
각 동전을 바탕으로 금액을 구성할 때, 그 금액을 설정할 수 있는 최소 동전 개수를 계산합니다.
결과 배열에서 목표 금액에 대한 최솟값을 반환합니다.

자바 코드 구현

그럼 이제 위에서 설명한 접근법을 바탕으로 Java 코드를 작성해 보겠습니다.


import java.util.Arrays;

public class CoinChange {
    public static int minCoins(int[] coins, int amount) {
        // 최소 동전 수를 저장할 배열 초기화
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0; // 0원을 만들기 위해 필요한 동전 개수는 0개
        
        // 동전 종류 반복
        for (int coin : coins) {
            for (int x = coin; x <= amount; x++) {
                dp[x] = Math.min(dp[x], dp[x - coin] + 1);
            }
        }
        
        // 가능한 경우를 판단하여 결과 반환
        return dp[amount] > amount ? -1 : dp[amount];
    }
    
    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 25};
        int amount = 63;
        int result = minCoins(coins, amount);
        if (result != -1) {
            System.out.println("목표 금액 " + amount + "원을 만들기 위한 최소 동전 개수: " + result);
        } else {
            System.out.println("목표 금액을 만들 수 없습니다.");
        }
    }
}

알고리즘 분석

위의 코드는 동적 프로그래밍을 사용하여 목표 금액을 만들기 위한 최소 동전 개수를 구하고 있습니다. 이 코드는 다음과 같은 특성을 가집니다:

시간 복잡도: O(n * m)이며, 여기서 n은 동전의 종류 수, m은 목표 금액입니다.
공간 복잡도: O(m)으로, 동전 수를 저장하기 위한 배열에 사용되는 공간입니다.

마무리

이렇듯 동전의 최솟값을 구하는 문제는 동적 프로그래밍 접근을 통해 효율적으로 해결할 수 있습니다. 실전 코딩 테스트에서는 주어진 입력 종류와 예외 상황을 우선 정확하게 이해하고 구현하는 것이 중요합니다. 코드를 작성하는 과정에서 명확한 주석을 달고, 각 함수의 역할을 명확히 하여 가독성을 높이는 것도 빼놓을 수 없는 점입니다.

이번 강좌를 통해 동전 개수의 최솟값 구하기 문제를 해결하는 방법에 대해 자세히 알아보았습니다. 앞으로 다양한 알고리즘 문제를 풀어보며 코딩 테스트를 준비하는 데 도움이 되었으면 좋겠습니다.