JavaScript로 해결하는 동전 교환 문제 (Coin Change Algorithm)

동전 교환 문제란?

"동전 교환 문제"는 주어진 동전의 종류와 금액이 있을 때, 해당 금액을 만들기 위한 최소 동전 개수를 구하는 대표적인 "동적 계획법(DP) 문제"입니다. 이 문제는 실생활에서도 다양한 곳에서 활용됩니다. 예를 들어 자동 결제 시스템, POS 단말기, 게임 내 재화 계산 등에서 최적의 동전 개수를 계산해야 할 때 사용됩니다.

---

문제 조건

• 동전의 종류: 정수 배열 형태 (예: [1, 2, 5])
• 목표 금액: 양의 정수 (예: 11)
• 목적: 해당 금액을 만들기 위한 "최소 동전 개수" 구하기

불가능한 경우에는 -1을 반환합니다.

---

자바스크립트로 구현하는 DP 기반 풀이

function coinChange(coins, amount) {
  // "DP 배열"을 amount + 1 크기로 초기화 (모든 값은 무한대, 단 dp[0] = 0)
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  // 각 금액을 만들 수 있는 최소 동전 개수를 계산
  for (let i = 1; i <= amount; i++) {
    for (let coin of coins) {
      if (i - coin >= 0) {
        // 현재 금액에서 coin을 뺀 위치의 최소값 + 1
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  // 최종 결과 반환 (불가능한 경우 -1 처리)
  return dp[amount] === Infinity ? -1 : dp[amount];
}

// 예시 실행
console.log(coinChange([1, 2, 5], 11)); // 출력: 3 (5+5+1)
console.log(coinChange([2], 3));        // 출력: -1

---

코드 흐름 설명

1. 초기에는 "모든 값"을 무한대로 설정해 어떤 조합도 불가능하다고 가정합니다.
2. dp[0]은 금액이 0일 때 필요한 동전 수는 0이므로 0으로 초기화합니다.
3. 금액 1부터 목표 금액까지 차례로 탐색하며,
   • 각 금액 i에 대해 사용 가능한 동전 coin을 시도해
   • i - coin 위치의 최적값 + 1을 비교하여 "최소 동전 개수"를 갱신합니다.
4. dp[amount]에 값이 무한대가 남아 있다면 해당 금액을 만들 수 없다는 의미로 -1을 반환합니다.

---

DP 배열 변화 과정 시각화

아래는 coins = [1, 2, 5], amount = 11인 경우에 대해 DP 배열이 갱신되는 과정을 시각적으로 표현한 표입니다. 각 셀은 해당 금액을 만들기 위한 최소 동전 개수를 나타냅니다.

이 표를 참고하면 각 단계별 계산 과정을 직관적으로 이해할 수 있습니다.

---

시간 복잡도 분석

• 시간 복잡도: O(amount * coins.length)
• 공간 복잡도: O(amount)

동전의 개수가 적고, 목표 금액이 클 경우에도 선형적으로 탐색이 가능하여 효율적인 풀이로 간주됩니다.

---

활용 팁 및 주의사항

• "DP 배열" 초기화 시 Infinity를 사용하는 것이 핵심입니다.
• 동전 종류가 중복되거나 정렬되지 않아도 무방합니다.
• 문제에 따라 "동전 순서"나 "중복 사용 여부"가 달라질 수 있으므로 조건을 명확히 확인해야 합니다.

---

마무리 및 추천 자료

"동전 교환 문제"는 "최적화 문제"의 대표 예시로, 다양한 알고리즘 풀이 방식과 접근 전략을 연습하기에 적합한 주제입니다. 특히 "동적 계획법(Dynamic Programming)"을 처음 접하는 학습자에게 매우 유용한 연습 문제가 될 수 있습니다.

다음 리소스를 통해 추가 학습을 추천합니다:

• LeetCode Coin Change
• freeCodeCamp - DP 소개 강의
• replit JS 실습 플랫폼