Coin Change
서로 다른 동전 액면가 목록 coins와 목표 amount가 주어집니다. 각 동전 액면가는 원하는 만큼 사용할 수 있습니다. 액면가의 합이 정확히 amount가 되는 동전의 최소 개수를 반환하고, 동전을 어떻게 조합해도 목표 금액을 만들 수 없다면 -1을 반환합니다. 금액이 0이면 동전은 0개가 필요합니다.
함수
- coinsinteger-array
- 각 동전의 서로 다른 액면가는 각각 원하는 만큼 사용할 수 있습니다
- amountinteger
- 정확한 지불 총액
- 반환값integer
- 필요한 동전의 최소 개수 또는 해당 금액을 만들 수 없으면 -1
제약 조건
1 ≤ coins.length ≤ 121 ≤ coins[i] ≤ 1040 ≤ amount ≤ 104- 모든 동전의 값은 서로 다릅니다.
예제
- 입력
- coins = [2, 5, 10]amount = 27
- 출력
- 4
- 설명
- 10 + 10 + 5 + 2개의 동전으로 27을 만들 수 있습니다. 동전 3개로는 불가능합니다. 27은 홀수이므로 5짜리 동전이 정확히 하나 필요하고, 나머지 두 동전의 합은 최대 20으로 22에 미치지 못합니다.
- 입력
- coins = [4, 6]amount = 7
- 출력
- -1
- 설명
- 두 동전의 값은 모두 짝수이므로 만들 수 있는 모든 합계는 짝수입니다. 7은 홀수이므로 답은 -1입니다.
- 입력
- coins = [3, 7]amount = 0
- 출력
- 0
- 설명
- 0을 지불하는 데는 동전이 전혀 필요하지 않으므로, 동전의 액면가가 무엇이든 답은 0입니다.
후속 질문
가장 적은 동전 개수를 찾는 대신, amount를 만드는 서로 다른 동전 조합이 몇 가지인지 셀 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
들어맞는 가장 큰 동전을 항상 선택한다고 해서 동전 개수가 항상 가장 적어지는 것은 아닙니다. 동전
[1, 3, 4]와 금액6으로 시도해 보세요.t보다 작은 모든 금액을 만드는 데 필요한 최소 동전 수를 이미 알고 있다고 가정해 보세요. 동전 하나를 더 사용하면t에 도달할 수 있는 더 작은 금액은 무엇일까요?fewest[0..amount]테이블을0부터 채우세요.fewest[0] = 0으로 설정하고, 각fewest[t]는 동전c <= t에 대해 가장 작은fewest[t - c]값에 1을 더한 값입니다. 도달할 수 없는 금액은 실제 답보다 큰 값(예:amount + 1)으로 표시하고, 마지막에-1로 바꾸세요.
풀이
들어맞는 가장 큰 동전을 선택하는 방법은 실패합니다. 동전이 1, 3, 4일 때 6을 4 + 1 + 1로 지불하지만, 3 + 3이면 동전 두 개만 필요합니다. 어떤 금액에 필요한 최소 동전 개수는 더 작은 금액에 필요한 최소 동전 개수에만 달려 있으므로, 0부터 amount까지 각 금액을 한 번씩 계산하면 됩니다.
재귀를 사용해 모든 조합을 시도해 보세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
마지막으로 내는 동전의 가치가 c라면, 그 전에 내는 동전으로 remaining - c를 가능한 한 적은 동전으로 만듭니다. 따라서 fewest(remaining)는 맞는 모든 동전마다 fewest(remaining - c)의 최솟값에 1을 더한 값입니다. 이 방법은 금액을 초과하지 않는 모든 동전 조합을 시도하므로, 최선의 조합을 놓칠 수 없습니다.
같은 금액을 계속해서 다시 계산합니다. 동전이 2, 5, 10일 때 금액 27은 10 + 2, 2 + 10, 5 + 5 + 2 등 여러 순서로 동전을 낸 뒤 15에 도달하며, 매번 15를 처음부터 계산합니다. 호출 횟수는 금액에 따라 기하급수적으로 증가합니다.
알고리즘
fewest(remaining)이 남은 금액을 만들 수 있는 동전의 최소 개수를 반환하고, 만들 수 없으면 -1을 반환하는 도우미 함수를 작성합니다.remaining이 0이면 0을 반환합니다.remaining보다 크지 않은 각 동전에 대해, 해당 동전을 낸 뒤 남은 금액을 인수로 도우미 함수를 호출합니다.- -1이 아닌 결과 중 가장 작은 값에 낸 동전의 개수 1을 더해 저장합니다.
- 그 개수를 반환하고, 모든 동전으로 만들 수 없으면 -1을 반환합니다. 답은
fewest(amount)입니다.
def coinChange(coins, amount):
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
return best
return fewest(amount)메모이제이션을 활용한 재귀
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
재귀는 0부터 amount까지의 금액만 묻습니다. 각 답을 처음 계산할 때 배열에 저장하고, 해당 금액이 다시 나오면 저장된 값을 반환하세요. 각 금액은 동전들을 순회하는 루프로 한 번만 계산됩니다. 필요한 작업량은 O(amount × coins)입니다.
호출은 여전히 지불한 동전 하나당 한 단계씩 중첩됩니다. 가치가 1인 동전이 있으면 중첩 수준이 최대 10^4에 이르며, 이는 여러 언어의 기본 호출 스택이 허용하는 수준을 넘어섭니다.
알고리즘
- 0부터
amount까지 모든 금액을 담을 수 있는 배열memo를 만들고, 아직 계산되지 않았음을 나타내는 표시자로 채우세요. fewest(remaining)에서 0이면 0을 반환하고, 이미 답이 들어 있다면memo[remaining]을 반환하세요.- 그렇지 않으면 기본 재귀 방식처럼 들어맞는 모든 동전을 시도하고, 가장 작은 결과에 1을 더한 값을 유지하세요.
- 반환하기 전에 -1을 포함한 결과를
memo[remaining]에 저장하세요. fewest(amount)를 반환하세요.
def coinChange(coins, amount):
# memo[r] holds the answer for r once it is worked out; None means not yet
memo = [None] * (amount + 1)
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
if memo[remaining] is not None:
return memo[remaining]
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
memo[remaining] = best
return best
return fewest(amount)금액에 대한 상향식 동적 프로그래밍
핵심 아이디어
fewest 테이블을 0부터 시작해 위로 채우세요. 총액 t에 도달하면, 그보다 작은 모든 총액은 이미 정해졌으므로 fewest[t]는 맞출 수 있는 동전 c에 대해 가장 작은 fewest[t-c] 값에 1을 더한 값입니다.
어떤 동전 조합으로도 만들 수 없는 총액에는 표시값 amount + 1을 넣습니다. 모든 동전의 값은 최소 1이므로, 실제 답에서 사용하는 동전은 amount개를 넘지 않으며 표시값은 모든 비교에서 지게 됩니다. 재귀 대신 루프를 사용하므로 호출 스택의 깊이는 더 이상 문제가 되지 않습니다.
알고리즘
amount + 1개의 항목으로fewest를 만들고, 모두 표시값amount + 1로 설정한 다음fewest[0]을 0으로 설정합니다.- 1부터
amount까지 각 합계t에 대해c ≤ t인 모든 동전c를 살펴봅니다. fewest[t-c] + 1이fewest[t]보다 작으면, 그 값을fewest[t]에 저장합니다.- 반복문이 끝난 후에도
fewest[amount]에 표시값이 들어 있으면 -1을 반환하고, 그렇지 않으면fewest[amount]를 반환합니다.
def coinChange(coins, amount):
impossible = amount + 1
fewest = [0] + [impossible] * amount
for total in range(1, amount + 1):
for coin in coins:
if coin <= total and fewest[total - coin] + 1 < fewest[total]:
fewest[total] = fewest[total - coin] + 1
return fewest[amount] if fewest[amount] != impossible else -1
함정과 경계 사례
- 가장 큰 동전을 먼저 선택하는 것. 동전이 3과 5이고 금액이 9일 때 5와 3을 내고 1에서 막혀 -1을 반환하지만, 3 + 3 + 3으로는 해결할 수 있습니다.
- 가장 큰 정수를 표시 값으로 사용하는 것. 여기에 1을 더하면 오버플로로 음수가 되고, 이 값이 모든 비교에서 이기게 됩니다.
amount + 1을 사용하세요. - 막다른 경로에 1을 더하는 것. -1을 반환하는 분기에 낸 동전 값을 더하면 0이 되어 모든 비교에서 이기게 됩니다. -1 결과는 건너뛰세요.
amount단계만큼 깊게 재귀 호출하는 것. 가치가 1인 동전과 금액10^4를 사용하면 Python은 기본 한도인 1000단계에서 중단되고, JavaScript, Dart, Ruby, R도 스택이 부족해집니다.- 동전 값이
t보다 클 때, 테이블의 시작 위치보다 앞에 있는fewest[t-c]를 읽는 것.
자주 묻는 질문3
Coin Change에서 탐욕적 접근 방식은 왜 실패할까요?
들어맞는 가장 큰 동전을 선택하는 방법은 대부분의 실제 화폐처럼 일부 동전 체계에서만 안전합니다. 동전이 1, 3, 4일 때는 동전 두 개 대신 세 개로 6을 지불하고, 동전이 3, 5일 때는 9를 전혀 지불할 수 없습니다. 동적 프로그래밍은 모든 선택을 비교하므로 어떤 동전 체계도 이를 속일 수 없습니다.
Coin Change의 시간 복잡도는 무엇인가요?
동적 프로그래밍 솔루션은 시간 O(amount × coins)와 공간 O(amount)을 사용합니다. 각 금액마다 테이블 항목 하나를 두고, 각 항목에 대해 모든 동전을 확인합니다. 메모이제이션을 사용하지 않는 단순 재귀는 금액에 대해 지수 시간이 걸립니다.
Coin Change에는 하향식과 상향식 중 어느 방식이 더 좋을까요?
둘 다 동일하게 O(amount × coins)만큼의 작업을 수행합니다. 하향식 재귀는 금액만큼 깊게 중첩될 수 있어, 여러 언어에서 10^4일 때 호출 스택이 넘칠 수 있습니다. 상향식은 반복문으로 테이블을 채우므로 깊이 제한이 없으며, 면접에서는 더 안전한 선택입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def coinChange(coins, amount):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
coins = [2, 5, 10] amount = 27
예상 출력
4