이 글에서는 동전 교환(Coin Change) 문제를 파이썬으로 해결하는 방법을 단계별로 살펴봅니다.
문제 정의
여러 액면가를 가진 동전 집합 S가 주어졌을 때, 각 액면가의 동전은 무한개만큼 사용할 수 있다고 가정합니다. 이때 목표 금액 n을 만들 수 있는 조합의 개수(순서는 고려하지 않음)를 구하는 것이 문제입니다.
예를 들어 동전이 [1, 2, 3]이고 목표 금액이 4라면, {1,1,1,1}, {1,1,2}, {2,2}, {1,3}처럼 총 4가지 방법이 존재합니다.
접근 방법: 동적 계획법(Dynamic Programming)
단순 재귀 호출로 모든 조합을 탐색하면 지수 시간이 걸릴 수 있습니다. 대신 동적 계획법을 활용하면 중간 결과를 테이블에 저장해 중복 계산을 피하고, 시간 복잡도를 O(n × m)(n은 목표 금액, m은 동전 종류 수)로 줄일 수 있습니다.
핵심 아이디어는 다음과 같습니다.
table[i][j]= j번째 동전까지만 사용해서 금액 i를 만드는 방법의 수- S[j] 동전을 포함하는 경우: table[i - S[j]][j]
- S[j] 동전을 제외하는 경우: table[i][j-1]
- 두 경우를 더하면 table[i][j]가 됩니다.
구현 예제
# 동적 계획법 접근
def count(S, m, n):
# DP 테이블 초기화
table = [[0 for x in range(m)] for x in range(n+1)]
# 기저 사례: 금액이 0일 때는 방법이 1가지 (아무것도 선택하지 않음)
for i in range(m):
table[0][i] = 1
# 나머지 값은 bottom-up 방식으로 채워나감
for i in range(1, n+1):
for j in range(m):
# S[j] 동전을 포함하는 경우의 해
x = table[i - S[j]][j] if i-S[j] >= 0 else 0
# S[j] 동전을 제외하는 경우의 해
y = table[i][j-1] if j >= 1 else 0
# 두 경우를 합산
table[i][j] = x + y
return table[n][m-1]
# 메인 실행부
arr = [1, 3, 2, 4]
m = len(arr)
n = 5
print("방법의 수:", end="")
print(count(arr, m, n))실행 결과
방법의 수: 6
코드 설명
위 코드에서 사용된 변수들은 모두 함수 내 지역 범위(local scope)에서 선언되며, 각각의 역할은 다음과 같습니다.
arr = [1, 3, 2, 4]: 사용 가능한 동전의 액면가 목록m = len(arr): 동전 종류의 개수 (4)n = 5: 만들고자 하는 목표 금액
실제로 목표 금액 5를 [1, 2, 3, 4] 동전으로 만드는 방법은 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+2+2, 1+4, 2+3의 총 6가지이며, 프로그램의 출력과 일치합니다.
결론
이 글에서는 동적 계획법을 활용해 동전 교환 문제의 경우의 수를 효율적으로 구하는 파이썬 프로그램을 작성해 보았습니다. 이 접근법은 단순 재귀 풀이보다 훨씬 빠르며, 코딩 테스트에 자주 등장하는 대표적인 DP 유형이므로 반드시 익혀두는 것이 좋습니다.