동전 교환 문제란?
동전 교환(Coin Change) 문제는 주어진 금액을 만들기 위해 필요한 최소 동전 개수를 구하는 대표적인 동적 계획법(Dynamic Programming) 문제입니다. 이 글에서는 상향식(Bottom-Up) 접근 방식을 활용하여 C#으로 이 문제를 해결하는 방법을 알아보겠습니다.
상향식(Bottom-Up) 접근 방식의 동작 원리
CoinChangeBottomUpApproach 메서드는 다음과 같이 3개의 매개변수를 입력받습니다.
- n : 만들어야 할 목표 금액
- coins : 사용 가능한 동전 종류가 담긴 배열
- t : 동전의 총 개수
먼저 이전에 계산된 값들을 저장할 동적 배열(dp 테이블)을 선언합니다. 이후 1부터 목표 금액까지 순차적으로 순회하면서 각 금액을 만드는 데 필요한 최소 동전 개수를 계산합니다. 작은 문제부터 차례대로 해결하고 그 결과를 배열에 저장해 두기 때문에, 한 번 계산된 값은 배열에서 즉시 가져다 사용할 수 있으며 불필요한 중복 계산이 사라집니다. 이것이 상향식 접근 방식, 즉 타뷸레이션(Tabulation) 기법의 핵심입니다.
시간 복잡도 및 공간 복잡도
- 시간 복잡도 : O(N × t) — 금액 N만큼 순회하면서 매 단계마다 t개의 동전 종류를 검사
- 공간 복잡도 : O(N) — 금액별 최소 동전 개수를 저장하는 1차원 배열 사용
예제 코드
public class DynamicProgramming{
public int CoinChangeBottomUpApproach(int n, int[] coins, int t){
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++){
dp[i] = int.MaxValue;
for (int j = 0; j < t; j++){
if (i - coins[j] >= 0 && dp[i - coins[j]] != int.MaxValue){
int subProb = dp[i - coins[j]];
dp[i] = Math.Min(dp[i], subProb + 1);
}
}
}
return dp[n];
}
}
static void Main(string[] args){
DynamicProgramming dp = new DynamicProgramming();
int[] coins = { 1, 7, 10 };
int ss = dp.CoinChangeBottomUpApproach(15, coins, coins.Length);
Console.WriteLine(ss);
}
실행 결과
3
코드 상세 설명
- DP 테이블 초기화 : 크기가 n+1인 배열 dp를 선언합니다. dp[i]는 "금액 i를 만들기 위해 필요한 최소 동전 개수"를 의미하며, dp[0]은 동전을 하나도 사용하지 않는 경우이므로 0입니다.
- 최솟값 갱신 : 각 금액 i에 대해 사용 가능한 모든 동전을 하나씩 시도해 봅니다. 동전 coins[j]를 사용할 수 있다면(i - coins[j] ≥ 0), 남은 금액(i - coins[j])의 최소 동전 개수에 1을 더한 값과 현재 저장된 값을 비교하여 더 작은 값으로 갱신합니다.
- 오버플로 방지 : 아직 도달할 수 없는 금액(int.MaxValue)에 1을 더하면 정수 오버플로가 발생할 수 있으므로, dp[i - coins[j]] != int.MaxValue 조건을 추가하여 안정성을 높였습니다.
- 결과 반환 : 목표 금액 n에 해당하는 dp[n] 값을 반환합니다.
예제에서는 동전 {1, 7, 10} 세 종류를 사용하여 금액 15를 만듭니다. 최적의 조합은 7 + 7 + 1로, 총 3개의 동전이 필요하므로 실행 결과로 3이 출력됩니다.