2차 동적 계획법
2차 동적계획법(2-dimensional Dynamic Programming, 2D DP)은 동적 계획법의 일종으로, 문제를 해결하기 위해 2차원 배열(또는 테이블)을 사용하는 알고리즘 기법이다. 일반적으로 DP 테이블은 문제의 상태와 하위 문제의 결과를 저장하는데, 2차 DP는 이러한 테이블이 2차원 형태로 확장된 것을 의미한다.
2차 동적계획법은 주로 격자 형태의 문제나 이차원 배열을 다룰 때 사용된다. 예를 들어, 이항계수(binomial coefficient)계산 문제, 동전교환 문제, 최장공통부분수열( longest common subsequence), 대부분의 동적 계획법 문제가 있다.
기본적인 원리는 1차원 동적계획법과 동일하나, 문제를 표현하고 상태를 저장하는 DP 테이블이 2차원으로 확장되어 상태 전이를 구현하게 된다. 이때, 각 셀은 문제의 하위 문제의 최적해를 저장하며, 이 값을 이용해 다음 단계의 상태를 계산하게 된다.
2차 동적 계획법은 쉽게 말해서 2차원 배열로 동적계획법을 구현하는 것이다.
이항계수 (binomial coefficient)계산 문제
이항계수란 조합론에서 주어진 n개의 항목 중에서 k개의 항목을 선택하는 방법의 수를 나타낸다. 이는 수식으로 아래와 같이 표현할 수 있다.
예를 들어 20개의 항목중에서 15개의 항목을 선택하는 방법의 수는 다음과 같다.
이항 계수를 2차 동적계획법으로 구현하기 위해서는 재귀식으로 표현해야하는데 이항 계수는 파스칼의 삼각형 속성에 따라 재귀적으로 계산할 수 있다.
여기서 기본 조건은 k = 0일 경우와 k=n일 경우로 두가지이다. K=0이면 아무것도 선택하지 않는 다는 뜻이기 때문에 경우의 수는 아무것도 선택하지 않는 한자기 경우만 존재한다. K=n이면 모든 항목을 선택하는 1가지 경우만 존재한다.
위의 두가지 식을 합하여 이항계수를 재귀식으로 나타내면 다음과 같이 나타낼 수 있다.
예를 들어 문제를 해결해 보자
[서로 다른 n개의 항목 중 k개를 선택하는 조합의 수를 구하는 문제]
조합은 순서를 고려하지 않고 항목을 선택하는 방법이다. 예를 들어, 5개의 구슬 {A, B, C, D, E} 중 3개의 구슬을 선택한다고 할 때, 선택된 구슬의 조합 {A, C, E}와 {E, A, C}는 같은 경우로 간주된다.
n 구슬이 포함되지 않은 경우의 구슬 조합의 수는 C(n-1, k)이다. 개의 구슬 중 마지막 구슬을 선택하지 않는 경우의 조합의 수이다. 마지막 구슬을 선택하지 않으면 나머지 n−1개의 구슬 중에서 k개를 선택하는 경우의 수와 같기 때문에 이다. 그렇다면 n구슬이 포함된 구슬 조합의 수는 C(n-1, k-1)로 나타낼 수 있다. 번째 구슬을 선택한 경우에 나머지 k−1개의 구슬을 n−1개의 구슬 중에서 선택해야 하기 때문이다. 즉, 마지막 구슬 n을 선택하면 남은 구슬들로 조합을 완성해야 하므로 이러한 관계가 성립한다. 를 수학적으로 표현하면 아래와 같고 재귀적으로 표현하면 이항계수의 재귀식과 동일하다.
재귀식을 2차원 배열로 표현하자면 다음과 같다.
이 재귀식은 조합을 두 가지 경우로 나누어 계산함으로써, 전체 조합의 수 C(n,k)를 효율적으로 구할 수 있게 해준다.
위와 같이 B[n][k]는 B[n-1][k-1]+B[n-1][k]로 구할 수 있게된다.
이를 바탕으로 2차원 배열 B를 계산해 보면 다음과 같이 테이블이 채워진다.
k가 0인 경우는 base case로 모두 1의 값을 갖는다. 또 k=n인 경우도 base case로 모두 1의 값을 갖는다.
나머지 값들은 재귀식에 의해 bottom up 방식으로 채워진다.
위의 문제를 python 코드로 구현하면 다음과 같다.
def bin_coeff(n, k):
MAX = 30
B = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(n + 1):
for j in range(min(i, k) + 1):
if j == 0 or j == i:
B[i][j] = 1 # base case
else:
B[i][j] = B[i - 1][j - 1] + B[i - 1][j] # recursive relation
return B[n][k]
# 테스트 예시
n = 5
k = 2
print(bin_coeff(n, k)) # 결과: 10
동전교환 문제
동전교환문제는 서로 다른 단위의 동전이 주어졌을 때, 거스름돈을 교환해주는 동전의 조합의 수를 계산하는 무제이다. 단, 모든 단위의 동전은 무수히 많다고 가정한다.
예를 들어 동전의 동전의 종류가 1원, 2원, 3원일 때 거스름돈 4원을 거슬러주는 방법은 [1, 1, 1, 1], [1, 1, 2], [2, 2], [3,1] 이렇게 총 4가지 방법이다.
동전교환 문제도 위의 문제와 동일한 방법으로 전개할 수 있다.
먼저, 동전 조합의 구조를 분석해 보자면 동전의 종류가 n가지 이고 거스름돈이 k원일 때 동전(n,k)는 2가지 경우로 나타낼 수 있다.
이것을 재귀식으로 나태니면, K원을 n개의 동전으로 교환하는 동전조합의 수는 다음과 같다.
그럼 이제 재귀식으로 표현하여 2차원 배열을 구상해 보자
여기서 재귀식으로 표현해야할 때 주의해야할점은 거스름돈이 0원일 때, 아무것도 주지 않는 경우 한가지가 존재한다는 것이다. 절대 경우의 수가 0이 아님을 유의해야한다.
동전의 개수가 0개이고 거스름돈이 0원보다 클때는 거스름돈을 제공할 방법이 없으므로 경우의 수는 0이 된다.
위의 재귀식에 따라 2차원 배열을 Bottom Up으로 채우면 다음과 같이 table이 채워진다.
k=0일 때 base case에 따라 모든 값이 1이 되고 동전의 개수 n은 0이지만 거스름돈이 0원 보다 큰 경우도 basecase에 따라 모두 0이 된다. 나머지 경우는 N[n-1][k]+ N[n][k-cn]에 따라 값이 채워진다.
동전교환문제를 파이썬으로 구현하면 다음과 같다.
def min_coin_change(coins, amount):
# 초기값: 무한대로 설정하여 특정 금액을 만들 수 없는 경우를 표시
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # 0원을 만들기 위해 필요한 동전 개수는 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1 # 교환이 불가능하면 -1 반환
# 예제 사용법
coins = [1, 5, 10, 21, 25]
amount = 63
print(min_coin_change(coins, amount)) # 결과: 3
