다이나믹 프로그래밍 / 동적 계획법은 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 그렇기에 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법 중 하나이다. 프로그래밍에서 다이나믹(Dynamic)은 ‘프로그램이 실행되는 도중에’라는 의미이다.

다이나믹 프로그래밍을 사용하기 위해 만족해야 하는 조건

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

다이나믹 프로그래밍의 2가지 방식

1. 탑다운(Top-Down) 방식
   • 큰 문제를 해결하기 위해 작은 문제를 호출 ⇒ 하향식
   • 메모제이션 : 메모제이션은 다이나믹 프로그래밍(탑다운 방식)을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 메모제이션은 값을 저장하는 방법이므로 캐싱(Cashing)이라고도 한다.
2. 보텀업(Bottom-Up) 방식
   • 작은 문제부터 차근차근 답을 도출 ⇒ 상향식
   • DP 테이블 : 보텀업 방식에서 사용되는 결과 저장용 리스트

예시 - 피보나치 수열

재귀 함수를 사용한 피보나치 수열 소스코드

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

print(fibo(4))

• 재귀함수를 이용할 경우 n이 커질수록 수행시간이 기하급수적으로 늘어난다
• 시간 복잡도 = $O(2^N)$

메모제이션(Top-Down 방식)을 이용한 피보나치 수열 소스코드

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
    # 종료 조건(1 혹은 2일 때 1을 반환)
    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]

print(fibo(99))

• 한 번 구한 값은 다시 구하지 않기 때문에 n이 커져도 시간이 크게 증가하지 않는다
• 시간 복잡도 = $O(N)$

반복문(Bottom-Up방식)을 이용한 피보나치 수열 소스코드

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])

• 재귀함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생한다
• 하지만 위처럼 반복문을 이용해서 구할 경우 오버헤드를 줄일 수 있다

실전 문제

1로 만들기

• 만약 x가 26이라면 다음과 같이 계산해서 3번의 연산이 최솟값이다
  1. 26 - 1 = 25
  2. 25 / 5 = 5
  3. 5 / 5 = 1
• 이 문제를 단순히 조건문으로 풀게 되면 26이 2로 나누어지기 때문에 2로 나누면서 3번보다 더 많은 연산을 하게 된다. 따라서 이 문제는 단순 구현이 아니라 다이나믹 프로그래밍으로 풀어야 한다.
• 일단 1을 빼는 것으로도 1을 만들 수 있으므로 반복문의 처음에서 해당 값은 그 전의 값을 1로 만드는 횟수 + 1로 계산한다. 그리고 그 값과 2 또는 3 또는 5로 나눈 값과 비교해서 더 작은 값을 해당 값으로 사용하면 된다. 이 때 5로 나누는 것이 가장 좋으므로 2, 3, 5 순서대로 비교하여 2, 3, 5 모두 나누어지는 경우에는 더 큰 수로 나눠서 해당 값을 업데이트하도록 한다.

# 정수 X를 입력 받기
x = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1000001

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
for i in range(2, x + 1):
    # 현재의 수에서 1을 빼는 경우
    d[i] = d[i - 1] + 1
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    # 현재의 수가 5로 나누어 떨어지는 경우
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])

개미 전사

• 개미 전사가 정찰병에게 들키지 않고 식량 창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량 창고를 약탈해야 한다. 이 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램

• 만약 N이 4이고, 차례대로 식량이 1, 3, 1, 5만큼 들어있다면 식량을 선택할 수 있는 경우의 수는 아래 그림처럼 8이다. 7번 째 경우에서 총 8 만큼의 식량을 얻을 수 있기 때문.

  

• 왼쪽부터 차례대로 식량창고를 털지 안 털지 결정하는 경우와 특정한 i번째 식량창고에 대해 털지 안 털지의 여부를 결정할 때, 아래처럼 단 2가지 경우에 대해서만 확인하면 된다. 따라서 a와 b 중에서 더 많은 식량을 털 수 있는 경우를 선택하면 된다. 이 때 (i-3) 번째 이하의 식량창고의 경우는 한 칸 이상 떨어진 식량 창고는 항상 털 수 있기 때문에 신경쓰지 않아도 된다.

  

• 이해하기 쉽게 1, 2, 3 이렇게 식량 창고가 있다면 2를 터는 것과 1과 3을 같이 터는 것 중에서 식량의 합이 더 큰 것을 고르면 된다.

# 정수 N을 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
    d[i] = max(d[i - 1], d[i - 2] + array[i])

# 계산된 결과 출력
print(d[n - 1])

바닥 공사

• 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥을 1x2의 덮개, 2x1의 덮개, 2x2의 덮개를 이용해 채우고자 한다. 이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램

• 왼쪽부터 차례대로 바닥을 덮개로 채운다고 생각하면 아래와 같이 생각할 수 있다.

  

• 왼쪽부터 N-2 미만의 길이의 경우 사용할 수 있는 덮개의 형태가 최대 2x2의 직사각형 형태이기 때문에 따로 고려할 필요가 없다.

# 정수 N을 입력 받기
n = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1001

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[1] = 1
d[2] = 3
for i in range(3, n + 1):
    d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796

# 계산된 결과 출력
print(d[n])

효율적인 화폐 구성

• N가지 종류의 화폐가 있을 때, 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록하는 프로그램 (이 때 사용한 화폐의 구성이 같고 순서만 다르더라도 같은 경우로 구분)
• 예를 들어, 2(N)가지 종류의 화폐를 이용해 15(M)원을 만들려고 한다. 이 때 화폐의 종류에는 2원과 3원이 있다. 이 때 최소한으로 이용하려면 3원을 5개 사용하면 된다.
• 그리디의 거스름돈 문제와 비슷하지만, 화폐 단위에서 큰 단위가 작은 단위의 배수가 아니기 때문에 그리디 알고리즘이 아닌 다이나믹 프로그래밍을 이용해서 풀어야 한다

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

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
# M의 최댓값은 10000이므로 10001로 초기화
d = [10001] * (m + 1)

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1)

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