[Algorithm 완전 정복] 다이나믹 프로그래밍 | Dynamic Programming | 계속 쓰일 값은 저장해놓고 가져다 쓰자

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

 

💡 다이나믹 프로그래밍 (Dynamic Programming, DP)

우리는 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 그런데 어떤 문제는 메모리 공간을 약간만 더 사용하면 연산 속도를 매우 빠르게 증가시킬 수 있는 방법이 있다. 대표적인 방법이 바로 다이나믹 프로그래밍 Dynamic Programming이다!

 

다이나믹 프로그래밍은 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 다이나믹 프로그래밍을 설명하기 위한 대표적인 예시로 피보니치 수열이 있다.

 

 

💡 다이나믹 프로그래밍 활용 예제 - 피보나치 수열 구현하기

피보나치 수열은 다음의 점화식을 갖는 수열이다. 

$$F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2} \ \ for\ n > 1$$

source: https://en.wikipedia.org/wiki/Fibonacci_number

점화식을 프로그래밍으로 표현하기 위해 재귀 함수를 사용할 수 있다. f(n)을 계산하기 위해서는 같은 피보나치 함수의 f(n-1)과 f(n-2)의 값이 필요하기 때문이다.

#Fibonacci Function을 재귀 함수로 구현
def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)

print(fibo(4))   # 4

 

하지만 위와 같이 피보나치 수열을 작성하면 x가 매우 커질 때 연산량이 매우 많아 짐에 따라 연산 속도가 매우 느려지게 된다. 빅오 표기법으로 위 코드의 시간 복잡도를 표현하면 $$O(2^n)$$인데, 예를 들여 n이 30이라면 연산 횟수가 무려 약 10억번이 된다. 연산속도가 엄청나게 걸릴 것이다.

 

이때, 다이나믹 프로그래밍을 이용하면 메모리를 조금 더 쓰는 대신, 수행 시간을 아주 빠르게 할 수 있다.

다이나믹 프로그래밍은 아래 두 가지 조건을 만족할 때 사용할 수 있다.

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

즉, 다이나믹 프로그래밍은 큰 문제를 작은 문제들로 분할하여 작은 문제들을 푼 결과를 이용해서 큰 문제를 해결하는 방법이다. 작은 문제의 답은 항상 같으므로 작은 문제들을 푼 결과값을 저장해놓고 점차 큰 문제를 풀 때에 그 결과값을 이용하여 연산 시간을 줄이는 것이다.

source : 이것이 코딩 테스트다 (나동빈, 한빛미디어)

위의 코드에서 f(6)을 계산하려고 한다면 f(3)을 3번 연산하여야 한다. f(3)은 항상 같은 값을 갖기 때문에 같은 계산과정을 반복하는 것은 매우 비효율적이다. 따라서 이 f(3)을 저장해놓은 후, 나중에 f(3)이 필요할 때는 계산하지 않고 먼저 계산해놓은 값을 가져다 쓰면 연산 횟수가 줄어들 것이다! (메모리는 아주 조금 더 쓰겠지만!)

이때, 작은 부분 문제가 반복될 때 저장된 결과값을 활용하는 방식을 메모이제이션(memoization) 또는 캐싱(caching)이라고 한다. 피보나치 수열을 메모이제이션으로 구현하면 다음과 같다.

# 한 번 계산된 결과를 memoization하기 위한 리스트 초기화
d = [0] * 100

# Fibonacci Function을 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
    #종료 조건 (1 혹은 2일 때 1을 반환)
    if x == 1 or x == 2:
        return 1
    #이미 계산한 적 있는 문제라면 그대로 반환 (memoization)
    if d[x] != 0:
        return d[x]
    #아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[x] =  fibo(x-1) + fibo(x-2)
    return d[x]

이렇게 피보나치 수열을 구하는 함수를 구현한 코드의 시간복잡도는 $$O(N)$$이다. 왜나햐면 한번 구한 피보나치수는 리스트에 저장되므로 다시 필요할 때 찾아서 꺼내오기만 하면 되기 때문에 N번째 피보나치 수열을 구할 때 N번의 연산만 필요하다. (f(6)을 구할 때 f(5), f(4), f(3)을 각각 한번씩만 연산하면 된다)

실선으로 표현된 노드만 연산하면 된다. (source : 이것이 코딩 테스트다 (나동빈, 한빛미디어))

 

 

💡 탑다운 방식과 보텀업 방식

위의 코드처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 알고리즘을 사용하는 방법은 큰 문제를 해결하기 위해 작은 문제를 호출하여 탑다운Top-Down 방식이라고 한다.

"f(6)을 구하려고 보니 f(5)가 필요하고 f(5)를 구하려고 보니 f(4)가 필요하고.."의 과정이 반복되어 결국 맨 밑의 값까지 구하는 연산까지 갔다가 값을 저장하면서 차레대로 다시 올라온다.

 

반면에 단순히 반복문을 이용해서 다이나믹 프로그래밍 알고리즘을 사용하는 방법은 작은 문제부터 답을 도출하여 보텀업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])

6번째 피보나치수을 구하기 위해서 3번째 피보나치수부터 차례대로 수를 구해서 최종적으로 6번째 피보나치수에 다다른다. (다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.)

보텀업 방식에서 사용되는 작은 부분 문제들의 결과를 저장해놓는 리스트는 DP 테이블이라고 부르며, 메모이제이션은 탑다운 방식에서 국한되어 사용되는 방식이다.

(단, 메모이제이션이 탑다운 방식에 포함되는 개념은 아니며 맥락이 다른 용어이다. (이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 의미로 쓰인다.))

 

 

💡 분할 정복과 다이나믹 프로그래밍의 차이점

큰 문제를 작은 문제들로 분할하는 알고리즘 중에는 '분할 정복 알고리즘'도 있다. 다이나믹 프로그래밍이 분할 정복과 다른점은 '작은 부분 문제를 반복적으로 풀어야 한다는 것'이다.

# 분할 정복 알고리즘
: 큰 문제를 작은 문제로 쪼갠 후, 각각 작은 부분 문제들을 풀어서 큰 문제를 해결한다.

 # 다이나믹 프로그래밍
: 작은 부분 문제로 큰 문제를 쪼개는 것은 같지만, 다이나믹 프로그래밍은 작은 문제의 결과값이 다른 부분 문제를 푸는 데에 반복되어 사용된다. (예를 들면 위에서 이야기 한 것처럼  피보나치 수열에서 f(6)를 계산하기 위해서는 f(3)의 결과값이 3번 필요한 것처럼..!_!)

 

✅ 문제) 1이 될 때까지

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
1. X가 5로 나누어 떨어지면 5로 나눈다.
2. X가 3으로 나누어 떨어지면 3으로 나눈다.
3. X가 2로 나누어 떨어지면 2로 나눈다.
4. X에서 1을 뺀다.

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

이 문제를 다이나믹 프로그래밍으로 풀기 위한 조건은 만족한다.

• 각 X의 최소 연산 횟수는 항상 같다.
• 각 X의 최소 연산 횟수의 값이 더 큰 X의 최소 연산 횟수를 구하는데에 반복적으로 필요하다.

문제풀이 소스코드는 다음과 같다.

x = int(input())
d = [0] * (x+1)

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

• x의 최소 연산 횟수를 저장하기 위한 list (d)를 생성한다.
• 2의 최소 연산 횟수부터 저장하기 시작하여 마지막으로 26의 최소 연산 횟수까지 저장한다. → Bottom-Up 방법
• 문제 해결 아이디어는 점화식으로 표현하면 $$a_i = min(a_{i-1}, a_{i/2}, a_{i/3}, a_{i/5})+1$$이다. 
  즉, 24의 최소 연산 횟수는 23(=24-1)의 연산횟수, 8(=24/3)의 최소연산횟수, 12(=24/2)의 최소연산횟수의 최솟값 + 1이다. (24는 5로 나누어떨어지지 않으므로 최솟값을 고르는 선택지에 포함될 수 없다.) 1을 더해주는 이유는 23, 8, 12로 가기위한 연산 횟수를 더해줘야하기 때문이다!

x가 15일 때까지의 최소연산횟수를 저장한 리스트를 표현하면 이와 같다.

 

 

✅ 문제) 개미 전사

개미 전사는 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 식량창고는 일직선으로 이어져 있고, 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 메뚜기 정찰병들이 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 식량창고 N개에 대한 정보가 주어졌을 때, 개미 전사가 얻을 수 있는 식량의 최댓값을 구하여라.

이 문제를 다이나믹으로 풀 수 있는 조건은 다음과 같이 만족한다.

• N번째 방까지 털었을 때의 최대 수집 식량은 항상 일정하다.
• N번째 방까지의 최대 수집 식량을 구하기 위해서는 N-1번째 방까지의 최대 수집 식량과 N번째 방까지의 최대 수집 식량을 알아야 한다. → N-1번째 방까지 털기로 결정했다면 N번째 방을 털 수 없고, N-2번째 방까지 털기로 결정했다면 N번째 방까지 털 수 있다. 즉, N번째 방을 터는 것이 식량을 최대로 하는지, N-1번째 방까지 터는 것이 식량을 최대로 하는지 비교해서 결정해야 한다.

n = int(input())
w = list(map(int, input().split()))
w.insert(0, 0) #창고를 1번째 원소부터로 취급하기 위해 0번째 원소에 의미없는 값 넣기
d = [0] * (n+1)
d[1] = w[1]

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

• w는 식량 창고의 정보이고, d는 각 인덱스의 방까지 공격했을 때의 최대 수집 식량의 양을 저장한 리스트이다. (w[0]에 0을 넣은 것은 N번째 창고의 정보를 w[n]에 저장하기 위함이다.)
• 첫번째 식량 창고까지만 공격한다고 했을 때 최대 수집 식량의 양은 무조건 첫번째 창고에 저장되어 있는 식량의 양이므로 d[1]에는 바로 w[1]의 값을 넣어준다.
• 각각 i번째 창고까지 공격했을 때 얻을 수 있는 최대 식량 개수를 저장한다. → Bottom-Up
• i번째 창고까지 공격할 때의 최대 식량을 구하기 위해서는 i번째 창고를 공격할 때와 공격하지 않을 때의 최대 수집 식량을 비교하여야 한다.
  i번째 창고를 공격한다는 것은 최대 식량의 양이 i-2번째 창고까지 털었을 때의 최대 수집 식량(=d[i-2]) + i번째 창고의 식량의 양(=w[i])이고,
  i번째 창고를 공격하지 않는 다는 것은 최대 식량의 양이 i-1번째 창고까지 털었을 때의 최대 수집 식량의 양(=d[i-1])과 같다는 것이다. 

 

✅ 문제) 바닥 공사

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

타일링 문제 또한 대표적인 다이나믹 프로그래밍 알고리즘을 활용하는 문제이다.

왼쪽부터 덮개를 채운다고 생각해보자. 덮개의 종류에서 가로의 길이는 1, 2로 2가지 뿐이므로 왼쪽부터 덮개를 채울때, 생각할 수 있는 경우는 2가지로 나뉠 수 있다.

1. 왼쪽부터 i-1까지의 길이가 덮개로 채워져 있는 경우

: i-1 이후로는 길이 1만 채워주면 되므로 선택할 수 있는 덮개는 1가지이다.

2. 왼쪽부터 i-2까지의 길이가 덮개로 채워져 있는 경우
: i-2 이후로 길이 2를 채워주어야 하므로 선택할 수 있는 덮개의 조합은 2x2 1개 또는 1x2 2개로 2가지이다.

따라서 점화식은 $$a_i = a_{i_1} + a_{i_2}*2$$로 표현될 수 있고, 소스 코드는 다음과 같다.

n = int(input())
d = [1] * (n+1)

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

print(d[n], d, end='\n')

• 가로의 길이가 N인 바닥에 덮개를 까는 경우의 수를 d[n]에 저장하기 위하여 길이가 n+1인 list(d)를 생성하였다.
• 가로의 길이가 i인 바닥에 덮개를 까는 경우의 수는 길이가 i-1인 바닥에 덮개를 까는 경우(=d[i-1])에 2x1 덮개를 갖다 붙이는 경우(*1) + 길이가 i-2인 바닥에 덮개를 까는 경우(=d[i-2])에 1x2 덮개를 붙이거나 2x2 덮개를 붙이거나(*2)이다.

 

✅ 문제) 효율적인 화폐 구성

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같비남 순서만 다른 것은 같은 경우로 구분한다. 화폐들의 개수의 최솟값을 구하시오.

이 문제를 다이나믹 프로그래밍으로 풀 수 있는 조건은 다음과 같이 만족한다.

• 화폐의 종류가 일정할 때, 만들고자 하는 금액을 구성할 수 있는 최소 화폐 개수는 항상 일정하다.
• 만들고자 하는 금액(M)을 구성할 수 있는 최소 화폐 개수(dp_tbl[M])를 구할 때, M에서 어떤 하나의 화폐 종류를 뺐을 때의 값을 구성하는 최소 화폐 개수의 값(dp_tbl(M-coin1))이 필요하다.a

점화식은 다음과 같이 작성될 수 있다.

$$a_i = min(a_i, a_{i-coin}+1)$$

n, m = map(int, input().split())
dp_tbl = [10001] * (m+1)
coins = []
[coins.append(int(input())) for _ in range(n)]
coins.sort()
coins = [coin for coin in coins if coin <= m] # coin은 만들고자하는 값보다 작거나 같은 화폐만 필요
    
for i in range(coins[0], m+1):
    for coin in coins:
        dp_tbl[coin] = 1
        dp_tbl[i] = min(dp_tbl[i], dp_tbl[i-coin]+1)

if dp_tbl[m] == 10001:
    print(-1)
else:
    print(dp_tbl[m])

• dp_tbl = [10001] * (m+1)
  : 만들고자 하는 값(M)의 최댓값이 10,000이므로 DP테이블에 저장된 값이 10,001이라면 금액을 만들 수 있는 화폐 구성이 불가능하다는 의미이다. DP테이블(dp_tbl)을 10001의 값으로 구성된 길이가 m+1의 list로 초기화한다.
• coins = [coin for coin in coins if coin <= m]
  : 만들고자하는 금액보다 큰 화폐는 확인할 필요가 없으므로 제거한다.
• 가장 작은 코인과 같은 값의 금액(coins[0])부터 만들고자 하는 값(m)부터 확인하고, 각각의 금액에서 화폐 단위별로 확인한다. → Bottom-Up 방법

* 또다른 풀이 방법

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

# N개의 화폐 단위 정보를 입력받기
array = []
for i in range(n):
    array.append(int(input()))
    
# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m+1)

# 다이나믹 프로그래밍 진행 (보텀업)
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:
    print(-1)
else:
    print(d[m])