Dynamic Programming

다이나믹 프로그래밍은 중복 연산을 줄임으로써 컴퓨터의 연산 속도를 증가시켜주는 대표적인 방법이다. 즉 하나의 문제를 단 한 번만 풀도록 하는 알고리즘이라고 할 수 있다.

피보나치 수열(Fibonacci Sequence)

피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열로, 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시이다.

피보나치 수열의 점화식은 다음과 같이 표현된다.

이 점화식에 따라 실제로 피보나치 수를 구하는 과정은 다음과 같다. n번째 피보나치 수를 fibo(n)이고 표현할 때, fibo(5)를 구하기 위해서는 아래 그림과 같이 함수 fibo를 반복해서 호출할 것이다.

수학적 점화식을 재귀 함수를 사용하여 코드로 구현하면 다음과 같다.

def fibo(n):
  if n == 1 or n == 2 :
    return 1
  return fibo(n - 1) + fibo(n - 2)     

하지만 이렇게 재귀 함수를 이용해 작성한 코드는 함수의 n이 커질수록 수행 시간이 기하급수적으로 늘어나게 되는 문제가 발생한다. 빅오 표기법을 이용하면 $O(2^{N})$의 지수 시간이 소요된다.

위 사진에서도 fibo(3) 같은 경우 여러 번 호출되고 있는 것을 확인할 수 있다.

이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다. 다음의 조건이 만족될 때, 다이나믹 프로그래밍을 사용하면 효율적인 코드 작성이 가능해진다.

• 큰 문제를 작은 문제로 나눌 수 있다.
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

메모이제이션(Memoization)

메모이제이션은 DP를 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그래도 가져오는 기법을 의미한다. 값을 저장하는 방법이므로 캐싱(Caching)이라고도 한다.

한 번 구한 정보를 리스트에 저장하는 방식으로 사용할 수 있고, 탐다운 방식에 국한되어 사용되는 표현이다.

Top-Down 방식

d = [0] * 100

def fibo(x):
  if x == 1 or x == 2 :
    return 1
  if d[x] != 0:
    return d[x]
  d[x] = fibo(x - 1) + fibo(x - 2)
  return d[x]

위 코드는 재귀적으로 작성한 피보나치 수열 소스코드이다.

1. 한 번 계산된 결과를 메모제이션 하기 위한 리스트 초기화
2. 피보나치 함수를 재귀함수로 구현 (Top-down)
3. 종료 조건 설정 (1 혹은 2일 때 1을 반환)
4. 이미 계산한 적 있는 문제라면 그대로 반환
5. 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환

이처럼 DP를 사용하여 구현하면 여러 번 사용되는 함수들을 한 번씩만 연산하도록 만들어줘서 훨씬 빠른 연산이 가능해진다.

그리고 이와 같이 큰 문제를 해결하기 위해 작은 문제를 호출하는 것을 탑다운(Top-Down) 방식이라고 하고, 단순히 반복문을 이용하여 소스코드를 작성하는 경우는 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업(Bottom-Up) 방식이라고 한다.

시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있다. 예를 들어 재귀적인 피보나치 수열의 소스코드에서 오천 번째 이상의 큰 피보나치 수를 구하도록 하면 recursion depth와 관련된 오류가 발생할 수 있다. 이 경우 sys 라이브러리에 포함되어 있는 setrecursionlimit() 함수를 호출하여 재귀 제한을 완화할 수 있다.

Bottom-Up 방식

d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

for i in range(3, n+1):
  d[i] = d[i-1] + d[i-2]

이처럼 단순히 반복문을 이용하여 문제를 해결하는 것은 보텀업 방식이고, DP의 전형적인 형태는 보텀업 방식이다. 해당 방식에서 사용되는 결과 저장용 리스트는 DP 테이블이라고 부른다.

문제

[효율적인 화폐 구성]

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이 때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 다섯개 사용하는 것이 가장 최소한의 화폐 개수이다.

입력

• 첫째 줄이 N, M이 주어진다. (1 <= N <= 100, 1 <= M <= 10000)
• 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10000보다 작거나 같은 자연수이다.

출력

• 첫째 줄을 M원을 만들기 위한 최소한의 화폐의 개수를 출력한다.
• 불가능할 때는 -1을 출력한다.

입력 예시

입력 예시	출력 예시
2 15 2 3	5
3 4 3 5 7	-1

풀이

최소한의 화폐 개수를 $a_{i}$, 화폐의 단위를 $k$라고 했을 때 점화식은 다음과 같다.

• $a_{i-k}$를 만드는 방법이 존재하는 경우, $a_{i} = min(a_{i}, a_{i-k})$
• $a_{i-k}$를 만드는 방법이 존재하지 않는 경우, $a_{i} = 10,001$

해당 점화식을 모든 화폐 단위에 대하여 차례대로 적용하면 된다. 실제로 문제를 풀기 위해서는 가3장 먼저 $k$ 크기만큼 리스트를 할당한다. 이후에 각 인덱스를 '금액'으로 고려하여 DP를 진행한다.

예시 : $N=3$, $K=7$, 화폐 단위 2, 3, 5인 경우

• 초기화
  각 인덱스에 해당하는 값으로 10,001을 설정한다. 10,001은 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다는 의미이다. 0원의 경우 화폐를 하나도 사용하지 않았을 때 만들 수 있으므로 값으로 0을 설정한다.

  인덱스	0	1	2	3	4	5	6	7
  값	0	10,001	10,001	10,001	10,001	10,001	10,001	10,001

• 화폐 단위 2
  인덱스 2의 경우 1이라는 값을 가지는데, 이는 2원짜리 화폐 하나를 이용하여 2원을 만들 수 있다는 의미이다. 인덱스 4의 경우 $a_{4}=a_{2}+1$로 2이다. 즉, 2원짜리 두개를 이용하여 4원을 만들 수 있다는 것이다.

  인덱스	0	1	2	3	4	5	6	7
  값	0	10,001	1	10,001	2	10,001	3	10,001

• 화폐 단위 3
  $a_{5}=a_{2}+1=2$, $a_{6}=a_{3}+1=2$, $a_{7}=a_{4}+1=3$

  인덱스	0	1	2	3	4	5	6	7
  값	0	10,001	1	1	2	2	2	3

• 화폐 단위 5
  점화식에 따라 값을 도출하면 다음과 같이 리스트가 갱신된다. 예를 들어 인덱스 7은 $a_{7}=a_{2}+1=2$이고, 이는 2원짜리 화폐 1개와 5원짜리 화폐 1개로 7원을 만들 수 있다는 의미이다. 기존에 3의 값보다 2가 작기 때문에 리스트가 갱신된다.

  인덱스	0	1	2	3	4	5	6	7
  값	0	10,001	1	1	2	1	2	2

코드

# 정수 N, M 입력 받기
n, m = map(int, input().split())

# N개의 화폐 단위 정보를 입력받기
array = []
for i in range(n):
  array.append(int(input()))

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)
 
# DP 진행(Bottom-Up)
d[0] = 0
for i in range(n):
  for j in range(array[i], m + 1):
    d[j] = min(d[j], d[j - array[i]] + 1)

if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
  print(-1)
else:
  print(d[m])

---

Reference

나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020)