[Algorithm] 다이나믹 프로그래밍

중복되는 연산을 줄이자

컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터 개수도 한정적이다.

따라서 우리는 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘이 필수적이다.

프로그래밍에서 '다이나믹'이란, '프로그램이 실행되는 도중에'라는 의미이다. (ex. 동적할당)
그러나 다이나믹 프로그래밍은 이와 관련이 없다.

 

---

# 예시

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다.

 

$$a_n = a_{n-1} + a_{n-2}, a_1 = 1, a_2 = 1$$

 

그럼, 코드로는 어떻게 구현할 수 있을까?

가장 쉽게 생각할 수 있는 방법은 바로 재귀함수일 것이다.

 

 

그러나 코드를 이와 같이 짜면 심각한 문제가 생긴다.

바로 n이 커지면 커질수록 수행시간이 기하급수적으로 증가하는 것이다.

이 코드의 시간 복잡도는 $$O(2^N)$$이기 때문이다.

$$N=30$$이면, 약 10억 가량의 연산을 수행해야 한다면 더욱 감이 잡힐 것이다.

 

$$f(6)$$일 때의 호출 과정은 아래와 같이 시각화할 수 있는데,

이때 자세히 보면 동일한 함수가 반복적으로 호출되는 것을 알 수 있다.

 

$$f(6)$$을 호출하는데 $$f(3)$$은 무려 3번이나 호출된 것이다.

이처럼 피보나치 수열을 재귀 함수를 사용해 만들 수는 있지만,

단순히 매번 계산하도록 하는건 문제를 효율적으로 풀지 못한다.

 

다이나믹 프로그래밍을 사용하면 효율적으로 처리할 수 있는데

이 프로그래밍을 항상 사용할 수 있는 것은 아니다. 아래 두 가지 조건이 정의되어야 한다.

[전제]

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

 

피보나치 문제를 재귀함수가 아닌, 메모이제이션(Memoization) 기법을 사용하여 해결해보자!

메모이제이션(Memoization) = 캐싱(Caching)
: 다이나믹 프로그래밍 기법 중 하나로
  한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면
  메모한 결과를 그대로 가져오는 기법

구현 방법
: 한 번 구한 정보를 리스트에 저장
: 재귀적으로 수행하다가 같은 정보가 필요할 때 정답을 그대로 리스트에서 가져오면 됨

 

코드를 살펴보면 아래와 같다.

$$d$$ 리스트에는 한 번 구한 정보인지 아닌지에 대한 정보가 담겨있는 것이다.

 

문제를 작게 나눈다고? 퀵 정렬의 분할 정복 알고리즘과 비슷해보이는데?

비슷하지만,
퀵 정렬은 한번 기준 원소 Pivot가 자리를 변경해서 자리를 잡게 되면
그 기준 원소의 위치는 더 이상 바뀌지 않고 그 피벗값을 다시 처리하는 부분 문제는 존재하지 않는다.
그에 반해 다이나믹 프로그래밍은 한번 해결했던 문제를 다시금 해결한다.

 

 

 

메모이제이션 방법을 사용한 알고리즘을 시각화해보면 다음과 같다.

$$f(6)$$을 호출할 때, 이제는 아래처럼 훨씬 호출 횟수가 줄었다.

다이나믹 프로그래밍에 의해 피보나치 수열 알고리즘의 시간 복잡도는 $$O(N)$$으로 줄었다.

 

이처럼 재귀함수를 이용해서 다이나믹 프로그래밍 소스코드를 작성하는 방법을,

큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운Top-Down = 상향식 방식이라고 말한다.

반면에, 단순히 반복문을 이용하여 소스코드를 작성하는 경우

작은 문제부터 차근차근 답을 도출한다고 하여 보텀업Botton-Up = 하향식 방식이라고 한다. 

 

보텀업Bottom-Up 방법을 사용해서 해결한 코드는 이와 같다. 훨씬 간단한 듯!

 

다이나믹 프로그래밍의 전형적인 형태는 보텀업Bottom-Up 방식이다.
보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라고 부르고,
메모이제이션은 탑다운 방식에서 국한되어 사용되는 표현이다.

 

---

# 문제 푸는 방법

1. 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하기

2. 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 > 다이나믹 프로그래밍 적용 가능할까?

3. 재귀 함수로 비효율적인 프로그램 작성 (탑다운) > 코드 개선 -- 메모제이션 방법 사용

4. 3번 보다는 보텀업 방식으로 구현하는 것을 권장, 스택 크기가 한정되어 있을 수 있기 때문

---

# 2-1. 1로 만들기

import sys
X = int(input())

d = [0]*(X+1)

for i in range(2, X+1):
  d[i] = d[i-1] + 1
  if i%5 == 0:
    d[i] = min(d[i], d[i//5]) + 1
  elif i%3 == 0:
    d[i] = min(d[i], d[i//3]) + 1
  elif i%2 == 0:
    d[i] = min(d[i], d[i//2]) + 1

print(d[X])

함수가 호출되는 과정을 그리면 코드를 짜는게 더 간단해진다.

우리는 $$X$$가 있을 때 (만약 x가 2,3,5에 모두 나누어떨어진다면..)

$$f(X) = f(X-1) + 1$$

$$f(X) = f(X//2) + 1$$

$$f(X) = f(X//3) + 1$$

$$f(X) = f(X//5) + 1$$

이 중에 가장 작은 값을 취하게 된다. 점화식으로 표현하면, $$a_i = min(a_{i-1}, a_{i/2},  a_{i/3},  a_{i/5})$$

---

# 2-2. 개미전사

 

import sys
N = int(sys.stdin.readline().strip())
array = list(map(int,sys.stdin.readline().split()))

d = [0]*(N)
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])

 

현재 위치에서 어떤 식량 창고를                                                                                                                                                                   털지는 아래처럼 (1) 바로 직전과 (2) 전 전을 확인하면 된다.

이를 표현한 점화식은 다음과 같다. $$a_i = max(a_{i-1}, a_{i-2} + k_i)$$

---

# 2-3. 바닥 공사

import sys
N = int(sys.stdin.readline().strip())

d = [0]*(N+1)
d[1] = 1
d[2] = 3

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

print(d[N])

점화식을 표현하면 다음과 같다 $$a_i = a_{i+1} + a_{i-2}*2$$

---

# 2-4. 효율적인 화폐 구성

 

import sys
N, M = map(int,sys.stdin.readline().split())

coins = [int(sys.stdin.readline().strip()) for _ in range(N)]
d = [10001]*(M+1)

d[0] = 0
for i in range(N):
  for j in range(coins[i], M+1):
    if d[j-coins[i]] != 10001:
      d[j] = min(d[j], d[j-coins[i]]+1)

if d[M] == 10001:
  print(-1)
else:
  print(d[M])

 

금액 $$i$$를 만들 수 있는 최소한의 화폐 개수: $$a_i$$, 화폐의 단위: $$k$$

- $$a_{i-k}$$를 만드는 방법이 존재하는 경우: $$a_i = min(a_i, a_{i-k}+1)$$

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

예를 들어, $$N=3, K=7$$이고, 각 화폐의 단위가 $$2,3,5$$인 경우를 생각해보자!

 

step0: 초기화

특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다는 의미로 = 10,001 값 설정

 

step1: 화폐 단위 2부터 점화식을 확인하기 시작한다.

$$a_2 = a_0 + 1 = 0 + 1 = 1$$

$$a_4 = a_2 + 1 = 1 + 1 = 2 $$

$$a_6 = a_4 + 1 = 2 + 1 = 3 $$

다음 점화식에 의해 표를 채워 넣을 수 있다.

 

step2: 그 다음은 화폐 단위 3을 확인하기 시작한다.

$$a_3 = a_0 + 1 = 0 + 1 = 1$$

$$a_6 = a_3 + 1 = 1 + 1 = 2 $$ (update!)

$$a_7 = a_4 + 1 = 2 + 1 = 3 $$

다음 점화식에 의해 표를 채워 넣을 수 있다.

 

step3: 마지막으로, 화폐 단위 5을 확인하기 시작한다.

$$a_5 = a_0 + 1 = 0 + 1 = 1$$

$$a_7 = a_2 + 1 = 1 + 1 = 2 $$ (update!)

다음 점화식에 의해 표를 채워 넣을 수 있다.