LeetCode - Coin Change(JAVA)

마이구미·2025년 6월 8일

알고리즘

목록 보기

2/4

이번에 풀어본 문제는 LeetCode의 Coin Change입니다.

문제 요약

정수 배열 coins와 amount를 받아서 coins에서 주어진 동전의 종류로 amount를 만들어 내는 최소의 동전 수를 찾는 것이 목표입니다. 동전의 수는 무한하고 현재 가진 조합으로 만들 수 없을 경우 -1을 반환합니다.

접근 방법

DP (dynamic programming)
큰 문제를 작은 문제로 나누어 풀고, 그 결과를 저장하여 반복 계산을 피하는 방법을 의미합니다.
1-1. amount+1의 크기를 가지는 dp 배열 만들기

1+2. dp 배열에 amount + 1의 값을 저장 (counter의 최대보다 높은 값)

1-3. 해당 값을 구하는데 드는 counter의 값을 dp 배열에 저장(ex. dp[0] = 0)

1-4. for문을 통해 각 코인을 순회하며 counter의 값을 파악하는데 현재 카운터의 값과 현재 내가 얻고자 하는 값에서 코인을 뺀 값의 counter에 1을 더한 값의 차이를 비교하여 값을 저장함

1-5. dp[amount]의 값을 확인후 amount + 1일 경우 -1을 그 외는 counter의 값을 반환

BFS(Breadth-First Search, 너비 우선 탐색)
그래프나 트리 구조에서 가장 가까운 노드부터 탐색해 나가는 알고리즘입니다
2-1. BFS 그래프를 그려보고 맨 위에 목표 값을 둔다. 이때 queue에는 (목표값, 거리)를 넣음
2-2. 해당 BFS 값에 대해서 각 코인을 넣었을 때의 값 (목표 값 - 코인 값)을 이웃 노드로 설정하고 탐색을 진행한다.
2-3. 해당 과정을 반복하면서 현재 탐색하는 노드의 값이 0이 되면 해당 노드를 최소의 동전 수를 보장하는 노드로 취급하고 (BFS 탐사이기에 순서대로 카운터를 늘려서 그 값이 최소이다.) 그 값을 반환한다.
2-4. 모든 값에서 0이하의 값이 나오면 탐사를 종료하며, -1을 반환한다. (0이하면 queue에 넣지 않음)

코드 구현

DP (dynamic programming)

class Solution {
   public int coinChange(int[] coins, int amount) {
       // dp[i]는 금액 i를 만들기 위한 최소 동전 개수
       int[] dp = new int[amount + 1];
       
       // dp[0]은 0 (0원을 만들기 위해 필요한 동전 개수는 0개)
       dp[0] = 0;

       // 나머지 값은 최대값으로 초기화 (임의의 큰 값: amount + 1)
       // 이렇게 해야 나중에 최소값 비교가 가능함
       for (int i = 1; i <= amount; i++) {
           dp[i] = amount + 1;
       }

       // 1부터 amount까지의 금액을 하나씩 계산
       for (int i = 1; i <= amount; i++) {
           // 사용 가능한 모든 동전에 대해 검사
           for (int coin : coins) {
               // 현재 금액 i에서 coin을 뺀 금액을 만들 수 있다면
               if (i >= coin) {
                   // 이전 금액의 동전 수 + 1 (현재 동전 하나 추가)
                   dp[i] = Math.min(dp[i], dp[i - coin] + 1);
               }
           }
       }

       // dp[amount]가 초기값이라면 만들 수 없는 경우 → -1 반환
       // 그렇지 않으면 최소 동전 개수 반환
       return dp[amount] > amount ? -1 : dp[amount];
   }
}
**BFS(Breadth-First Search, 너비 우선 탐색)**

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 금액이 0이면 동전이 필요 없으므로 0 반환
        if (amount == 0) return 0;

        // BFS 탐색을 위한 큐 선언 (int[] = [남은 금액, 사용한 동전 수])
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{amount, 0}); // 초기 상태: amount 남음, 동전 0개 사용

        // 이미 방문한 금액은 다시 방문하지 않도록 체크
        boolean[] visited = new boolean[amount + 1];
        visited[0] = true; // 금액 0은 이미 도달한 상태로 처리

        // BFS 탐색 시작
        while (!queue.isEmpty()) {
            int[] current = queue.poll(); // 현재 상태 가져오기
            int remaining = current[0];   // 남은 금액
            int count = current[1];       // 사용한 동전 수

            // 사용 가능한 모든 동전에 대해 시도
            for (int coin : coins) {
                int next = remaining - coin;

                // 정확히 0원이 되면 목표 달성 → 동전 개수 +1 반환
                if (next == 0) {
                    return count + 1;
                }

                // 음수가 아니고, 아직 방문하지 않은 경우 큐에 추가
                if (next > 0 && !visited[next]) {
                    queue.offer(new int[]{next, count + 1});
                    visited[next] = true; // 중복 탐색 방지
                }
            }
        }

        // 모든 경우를 탐색해도 0원을 만들 수 없으면 -1 반환
        return -1;
    }
}