[코딩테스트] 다이나믹 프로그래밍

다이나믹 프로그래밍

: 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘

중복되는 연산을 줄이자

피보나치 수열

n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수

# 피보나치 함수를 재귀함수로 구현
def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)

print(fibo(4))

-> 이는 f(n) 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어남
-> 이미 한 번 계산했지만 계속 호출될 때마다 계산
-> 시간 복잡도 $O(2^N)$

다이나믹 프로그래밍 사용 전제 조건

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

메모이제이션(Memoization) 기법

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

구현 : 한 번 구한 정보를 리스트에 저장하고 필요할 때 이미 구현된 정답을 그대로 가져옴

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

#피보나치 함수를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
    if x == 1 or x == 2:  #종료 조건 (1 또는 2일 때 1 반환)
        return 1
    if d[x] != 0:  #이미 계산한 적 있는 문제라면
        return d[x]  #그대로 반환

    #아직 계산하지 않은 문제라면 점화식에 따라 피보나치 결과 반환
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

print(fibo(99))

출력결과

218922995834555169026

다이나믹 프로그래밍: 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 (문제들이 서로 영향을 미침)
-> 다이나믹 프로그래밍은 한 번 해결했던 문제를 다시금 해결, 이는 이미 해결된 것이기 때문에 다시 해결하지 않고 반환
-> 다이나믹 프로그래밍 사용했을 때 피보나치 수열 알고리즘 시간 복잡도: $O(N)$

# 호출되는 함수 확인용 피보나치 수열 함수
d = [0] * 100

#피보나치 함수를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
    print('f(' + str(x) + ')', end=' ')
    if x == 1 or x == 2:  #종료 조건 (1 또는 2일 때 1 반환)
        return 1
    if d[x] != 0:  #이미 계산한 적 있는 문제라면
        return d[x]  #그대로 반환

    #아직 계산하지 않은 문제라면 점화식에 따라 피보나치 결과 반환
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

fibo(6)

출력결과

f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4) 

탑다운(Top-Down) 방식

: 재귀함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법,
  큰 문제를 해결하기 위해 작은 문제를 호출
=> 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현

보텀업(Bottom-Up) 방식

: 단순히 반복문을 이용하여 소스코드를 작성하는 방법, 작은 문제부터 차근차근 답 도출
-> 여기서 사용되는 결과 저장용 리스트: 'DP 테이블'
=> 다이나믹 프로그래밍은 전형적인 보텀업 방식

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

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

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

출력결과

218922995834555169026 

실전문제

Ex1) 1로 만들기

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.

1. X가 5로 나누어떨어지면, 5로 나눈다.
2. X가 3으로 나누어떨어지면, 3으로 나눈다.
3. X가 2로 나누어떨어지면, 2로 나눈다.
4. X에서 1을 뺀다.

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

입력조건
- 첫째 줄에 정수 X가 주어진다. (1 $\leq$ X $\leq$ 30,000)

출력조건
- 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

sol) $a_i = min(a_{i-1}, a_{i/2}, a_{i/3}, a_{i/5})+1$ 점화식을 토대로 보텀업 다이나믹 프로그래밍 구현

x = int(input())

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

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

Ex2) 개미 전사

개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량을 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이 때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야한다. 예를 들어 식량 창고 4개가 다음과 같이 존재한다고 가정하자.
{1 ,3 ,1, 5}
이 때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼앗을 수 있다. 개미 전사는 식량 창고가 이렇게 일직선상일 때 최대한 많은 식량을 얻기를 원한다. 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있ㄴ느 식량의 최댓값을 구하는 프로그램을 작성하시오.

입력조건
- 첫째 줄에 식량창고의 개수 N이 주어진다. (3 $\leq$ N $\leq$ 100)
- 둘째 줄에 공백으로 구분되어 각 식량 창고에 저장된 식량의 개수 K가 주어진다. (0 $\leq$ K $\leq$ 1,000)

출력조건
- 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

sol) 왼쪽부터 차례대로 식량창고를 털지 안털지를 결정하는 경우와 특정한 i번째 식량창고에 대해서 털지 안털지의 여부를 결정할 때, 2가지를 생각한다.
1. (i-1)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 없다.
2. (i-2)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 있다.
이 둘 중 더 많은 식량을 털 수 있는 경우 선택
$a_i = max(a_{i-1}, a_{i-2}+k_i)$ 보텀업 방식 사용

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

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

# 다이나믹 프로그래밍 진행 (보텀업)
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])

Ex3) 바닥 공사

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1x2의 덮개, 2x1의 덮개, 2x2의 덮개를 이용해 채우고자 한다. 이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2x3 크기의 바닥을 채우는 경우의 수는 5가지이다.

입력조건
- 첫째 줄에 N이 주어진다. (1 $\leq$ N $\leq$ 1,000)

출력조건
- 첫째 줄에 2xN 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.

sol) 타일링 문제 유형, 796,796으로 나눈 나머지를 출력하기 때문에 값을 계산할 때마다 특정한 수로 나눈 나머지만 취하도록 함
왼쪽부터 차례대로 바닥을 덮개로 채운다 생각
1. 왼쪽부터 i-1까지 길이가 덮개로 이미 채워져 있으면 2x1의 덮개를 채우는 하나의 경우 밖에 존재하지 않는다.
2. 왼쪽부터 i-2까기 길이가 덮개로 이미 채워져 있으면 1x2의 덮개 2개를 넣는 경우, 혹은 2x2의 덮개 하나를 넣는 경우로 2가지 경우가 존재한다.
$a_i = a_{i-1} + a_{i-2}*2$ 보텀업 방식 사용

n = int(input())

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

# 다이나믹 프로그래밍 진행 (보텀업)
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])

Ex4) 효율적인 화폐 구성

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

입력조건
- 첫째 줄에 N, M이 주어진다. (1 $\leq$ N $\leq$ 100, 1 $\leq$ M $\leq$ 10,000)
- 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다.

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

sol) 그리디의 거스름돈 문제와 유사하지만 항상 화폐의 단위가 작은 단위의 배수는 아님
다이나믹 프로그래밍 이용하여 적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾는다. 금액 $i$를 만들 수 있는 최소한의 화폐 개수 $a_i$, 화폐의 단위 $k$라 했을 때 ($a_{i-k}$는 금액 ($i-k$)를 만들 수 있는 최소한의 화폐 개수)
1. $a_{i-k}$를 만드는 방법이 존재하는 경우=> $a_i = min(a_i, a_{i-k}+1)$
2. $a_{i-k}$를 만드는 방법이 존재하지 않는 경우=> $a_i=10,001$
해당 점화식을 모든 화폐 단위에 대하여 적용
가장 먼저 K 크기의 리스트 할당하고 각 인덱스를 금액으로 고려하여 메모이제이션 진행

n, m = map(int, input().split())
array = []
for i in range(n):  #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:  #최종적으로 M원 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

기출문제

Q32 정수 삼각형

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습입니다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하세요. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있습니다.
삼각형의 크기는 1 이상 500 이하입니다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 그 값의 범위는 0 이상 9999 이하입니다.

입력조건
- 첫째 줄에 삼각형의 크기 n (1 $\leq$ n $\leq$ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어집니다.

출력조건
- 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력합니다.

sol) 특정 위치에 도달하기 위해 왼쪽 위 또는 오른쪽 위 2가지 위치에서만 내려올 수 있음
=> 모든 위치를 기준으로 이전 위치로 가능한 2가지 위치까지의 최적의 합 중 더 큰 합 가지는 경우 선택
dp[i][j] = array[i][j] + max(dp[i-1][j-1], dp[i-1][j])
단, dp 테이블에 접근해야 할 때마다 리스트의 범위를 벗어나지 않는지 체크

n = int(input())
dp = []  #다이나믹 프로그래밍을 위한 DP 테이블 초기화

for _ in range:
    dp.append(list(map(int, input().split())))
    
# 다이나믹 프로그래밍으로 두 번째 줄부터 내려가면서 확인
for i in range(1, n):
    for j in range(i+1):
        if j == 0:  #왼쪽 위에서 내려오는 경우
            up_left = 0
        else:
            up_left = dp[i-1][j-1]
        if j == i:  #오른쪽 위에서 내려오는 경우
            up_right = 0
        else:
            up_right = dp[i-1][j]
        dp[i][j] = dp[i][j] + max(up_left, up_right)  #최대 합 저장

print(max(dp[n-1]))

입력

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

출력

30

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