동적계획법(Dynamic Programming) 문제풀이

다이나믹 프로그래밍 문제에 접근하는 방법

- 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요

- 가장 먼저 그리디, 구현, 완전탐색 등의 아이디어로 해결할 수 있는지 검토

• 다른 알고리즘으로 풀이방법이 떠오르지 않으면 다이나믹 프로그래밍 고려

- 우선 재귀함수로 비효율적인 완전 탐색 프로그램을 작성한 후 Top-Down(작은 문제에서 구한 답이 큰 문제에 사용될 수 있음) 방식이 적용될 것 같으면 코드를 개선하는 식

- 점화식 떠올려보기 

- 일반적인 코딩테스트 유형에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많음

 

 

다이나믹 프로그래밍 문제1: 개미 전사

A(i): i번째까지의 식량창고가 존재할 때 털 수 있는 식량의 최댓값 

K: 식량창고 리스트 

개미전사 파이썬 코드

import sys

n = int(sys.stdin.readline())
k = list(map(int, sys.stdin.readline().split()))

# 점화식(Recurrence Relation)
# A(i) = max(Ai-1, k(1) + A(i-2))

dp = [0] * n
dp[0] = k[0]
dp[1] = max(dp[0], k[1])
for i in range(2, n):
    dp[i] = max(dp[i - 1], k[i] + dp[i - 2])

다이나믹 프로그래밍 문제2: 1로 만들기

1로 만들기 파이썬 코드 

# # X가 주어졌을 때
# # X//5 == 0 -> X//5
# # X//3 == 0 -> X//3
# # X//2 == 0 -> X//2
# # X - 1
# 네 가지 연산중 하나 골라서 실행
# bottom up

import sys

x = int(sys.stdin.readline())

dp = [0] * 30001
for i in range(2, x + 1):
    # 4가지 연산으로 갈 수 있는 dp값을 리스트에 넣어주고 그 다음 최솟값이랑 + 1을 해줌
    pre_dp = []
    if i % 5 == 0:
        pre_dp.append(dp[i//5])
    if i % 3 == 0:
        pre_dp.append(dp[i//3])
    if i % 2 == 0:
        pre_dp.append(dp[i//2])
    pre_dp.append(dp[i - 1])
    dp[i] = min(pre_dp) + 1
print(dp[x])

DP 문제3: 효율적인 화폐 구성

효율적인 화폐구성 파이썬 코드 

# 효율적인 화폐구성
import sys

n, m = map(int, sys.stdin.readline().split())
arr = []
for i in range(n):
    arr.append(int(sys.stdin.readline()))

d = [10001] * (m + 1)
d[0] = 0

for i in range(n):
    for j in range(arr[i], m + 1):
        if d[j - arr[i]] != 10001:
            d[j] = min(d[j], d[j - arr[i]] + 1)

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

이 문제는 먼저 화폐를 배열로 만든 후, 10001이라는 화폐의 최댓값보다 1이 큰 수가 m + 1개 들어가있는 DP 테이블을 생성해주어야 합니다. 그 다음 단위가 작은 화폐부터 구성할 수 있는 m 보다 작은 금액을 채워나가는 식으로 해결할 수 있습니다.

DP문제 4: 금광

이 문제의 경우 금광 분포로 2차원 배열을 생성 후 이를 토대로 새로운 배열의 각 칸에 누적된 최댓값을 입력해주는 방식으로 해결 가능하다.  

 

금광 파이썬 코드 

import sys
t = int(sys.stdin.readline())
for q in range(t):
    n, m = map(int, sys.stdin.readline().split())
    inp = list(map(int, sys.stdin.readline().split()))
    table = [[0 for r in range(n)] for c in range(m)]
    k = 0
    for r in range(n):
        for c in range(m):
            table[c][r] = inp[k]
            k += 1

    d = table
    for i in range(1, m):
        for j in range(n):
            if j == 0:
                mid, lower = d[i - 1][j], d[i - 1][j + 1]
                d[i][j] = max(mid, lower) + d[i][j]

            elif j == n - 1:
                upper, mid = d[i - 1][j - 1], d[i - 1][j]
                d[i][j] = max(upper, mid) + d[i][j]

            else:
                upper, mid, lower = d[i - 1][j - 1], d[i - 1][j], d[i - 1][j + 1]
                d[i][j] = max(upper, mid, lower) + d[i][j]
    print(max(d[m - 1]))

 

 

 

 

참고

https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6