software

Greedy vs. DP: 동전 교환 문제에 대한 30초 테스트

발행: (2025년 12월 19일 오전 05:26 GMT+9)
8 min read
원문: Dev.to

Source: Dev.to

원래는 LeetCopilot Blog에 게시되었습니다

TL;DR

  • Topic: 동전 교환 변형에 대해 탐욕법과 DP 중 어느 것을 사용할지 결정하기.
  • Why it matters: 잘못된 전략을 선택하면 시간이 낭비되고 면접관을 혼란스럽게 한다.
  • Core steps: 동전 체계의 특성을 확인하고, 반례를 테스트하며, 최적 부분 구조가 명확하지 않을 때 DP로 전환한다.
  • Key insight: 정규(표준) 동전 체계는 예외이며, 일반적인 경우는 아니다.
  • You’ll learn: 빠른 휴리스틱, TypeScript DP 코드 조각, 그리고 연습 문제.

Beginner‑Friendly Explanations

When Greedy Works

Greedy is safe when the coin system is canonical—each larger coin is a multiple or a structured combination of smaller ones.
Example: USD coins (1, 5, 10, 25) are canonical for making change with the fewest coins.

When Greedy Fails

If a larger coin is not composed of smaller ones, greedy can pick a locally good coin that ruins the global optimum.
Example: Coins [1, 3, 4], target 6. Greedy picks 4 + 1 + 1 (3 coins) instead of 3 + 3 (2 coins).

Why DP Rescues You

DP explores all sub‑targets. Bottom‑up tabulation guarantees the minimum number of coins if you define a recurrence like

dp[x] = min(dp[x - c]) + 1   for every coin c

Visual Concept

Imagine two columns: Greedy path (choose biggest, subtract, repeat) versus DP table (fill from 0 to target). The DP column never forgets a better sub‑solution.

단계별 학습 가이드

1) 반례 테스트 실행

코딩하기 전에 머리 속으로 작은 반례를 시험해 보세요: 동전 [1,3,4] 로 6을 만들어 보는 것입니다. 탐욕 알고리즘이 실패하면 DP를 사용해야 합니다. 이 빠른 검증은 여러분이 논리를 명확히 설명하는 데 도움이 되며, greedy algorithm counterexamples for coding interviews 에서 소개된 접근법과 유사합니다.

2) 상태와 전이 결정

최소 동전 개수를 구할 때 상태는 목표 금액입니다. 전이는 각 동전을 검사하면서 수행됩니다:

dp[x] = Math.min(dp[x], dp[x - coin] + 1)   // when x - coin >= 0

3) 불가능한 상태 처리

dp[0] = 0을 제외한 모든 항목을 Infinity 로 초기화합니다. 만약 dp[target]이 여전히 Infinity이면 -1을 반환합니다.

4) 복잡도 설명

바텀‑업 접근법의 시간 복잡도는 O(n × amount), 공간 복잡도는 O(amount) 라는 점을 언급하세요. 면접관은 여러분이 트레이드‑오프를 이해하고 있다는 점을 듣는 것을 좋아합니다.

5) 두 목표값으로 연습

동전 집합 [1,3,4]와 [1,5,10,25]를 사용해 각각 6과 27을 해결해 보세요. 탐욕 알고리즘과 DP 결과를 비교하면서 휴리스틱을 확고히 할 수 있습니다.

시각화 가능한 예시: TypeScript로 구현한 Bottom‑Up 동전 교환

function minCoins(coins: number[], amount: number): number {
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let total = 1; total = 0) {
        dp[total] = Math.min(dp[total], dp[total - coin] + 1);
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

각 total은 최적의 부분 목표 해를 재사용하므로, 탐욕 알고리즘이 놓칠 수 있는 경우를 포착합니다.

실전 준비 전략

나만의 결정표 만들기

두 열 시트를 만들세요: 탐욕법이 작동하는 동전 집합과 실패하는 동전 집합. 각각에 짧은 메모를 추가합니다. 패턴 인식을 강화하기 위해 동적 프로그래밍이 필요할 때를 아는 방법과 함께 검토하세요.

타이머를 이용한 연습

5분을 정해 무작위 동전 시스템 3개를 분류하고 해결해 보세요. 압박감이 휴리스틱을 고착시킵니다.

가벼운 가이드 활용

LeetCopilot 같은 도우미가 코딩을 시작하기 전에 반례를 제시하도록 유도하여, 동적 프로그래밍을 직접 알려주지 않으면서도 체계적인 사고를 강화합니다.

다른 패턴과 연결하기

이것이 슬라이딩 윈도우 결정과 어떻게 유사한지 살펴보세요: 단조성 속성이 유지될 때만 탐욕법을 선택합니다. 슬라이딩 윈도우 시각화 도구는 불변성을 관찰하는 직감을 훈련시킵니다.

피해야 할 일반적인 실수

USD 규칙이 모든 곳에 적용된다고 가정하기

외국 또는 사용자 정의 동전 시스템은 탐욕 알고리즘 가정을 깨뜨리는 경우가 많다.

초기화 누락

dp를 기본값 0으로 두면 불가능한 상태를 잘못 선호하게 된다.

음수 또는 0인 동전 무시하기

입력을 검증하라; 동전은 양수여야 하며, 그렇지 않으면 루프가 영원히 돌 수 있다.

불가능한 목표에 대해 -1 반환하지 않기

면접관은 조합이 존재하지 않을 때 명확한 신호를 기대한다.

FAQ

그리디가 유효한지 어떻게 알 수 있나요?
작은 반례를 시도해 보세요. 그리디가 대안보다 더 많은 동전을 사용한다면 DP로 전환하세요.

동전 교환 문제를 풀기 전에 무엇을 연습해야 하나요?
기본 루프, 배열 초기화, 그리고 부분 문제를 생각하는 연습을 하세요. 그런 다음 점화식을 설명하는 방법을 배우세요.

이 주제가 면접에서 중요합니까?
네. 코딩 능력뿐 아니라 패턴 선택을 평가합니다.

DP를 더 최적화할 수 있나요?
네—예시와 같이 1차원 배열을 사용하고, 목표보다 큰 동전은 제외하여 작업량을 줄이세요.

결론

동전 교환 문제에서 탐욕 알고리즘과 DP 중 선택은 동전 체계의 구조를 증명하거나 반증하는 것에 달려 있습니다. 반례를 먼저 제시하고, 확신이 서지 않을 때는 DP로 돌아가며, 자신의 논리를 명확히 전달하세요. 연습을 통해 이 선택은 자동화되고 면접에서도 안전해집니다.

LeetCode 패턴을 마스터하고 코딩 인터뷰를 준비하는 데 도움을 주는 AI 어시스턴트를 찾고 있다면, LeetCopilot을 확인해 보세요.

Back to Blog

관련 글

더 보기 »