🛝Dynamic Programming🛝

intro

🐥 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함. 따라서 완전탐색의 비효율적인 시간 복잡도 성능 한계점을 해결해준다. 또한 '다이나믹 프로그래밍 = 동적계획법'이라고도 부른다. (동적(dynamic) 할당(allocation) - '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'). DP 알고리즘을 활용한다면 여러 sub-problem 포함 모든 문제의 정답이 들어가는 메모리 미리 배치(이 때 여러 문제들의 결과를 저장하는 저장용 list는 dp-table). DP 알고리즘을 활용하기 위해서는 아래 두가지 조건을 만족해야 한다.

 

① 최적 부분 구조(Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제 해결

② 중복되는 부분 문제 (Overlapping Subproblem) - 동일한 작은 문제를 반복적으로 해결

 

🐥 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식 → top-down(위에서 아래-하향식) & bottom-up(아래에서 위-상향식)으로 구성된다.

 

① top-down (하향식) : memoization

: dp 구현법 중 하나로, 한 번 계산한 결과를 메모리 공간(테이블, 캐시, dp)에 메모 하는 기법이다. 즉, 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져오고, 값을 기록해 놓는다는 점에서 caching이라고 부른다. 큰 문제를 작게 나누어 푸는 방식으로 주로 재귀가 사용(이 과정에서 한번 계산된 결과는 기록하는 메모이제이션 진행. 즉, 메모이제이션이란, 이전에 계산된 결과를 일시적으로 기록해 놓는 개념을 뜻한다여기서 메모이제이션이란 한 번 계산된 결과를 담아 놓기만 하고 dp를 위해 활용하지도 않을 수도 있으므로 엄밀히 말하면 메모이제이션과 dp는 같은 개념이 아니다. 혼동하지 말자.

 

② bottom-up (상향식) : tabulation

: 아래쪽에서 작은 문제를 먼저 차근차근 해결해나가면서 그 다음의 문제까지 차례로 해결해 나가는 과정을 뜻한다. 반복문을 주로 사용하며, dp에서 가장 많이 구현하는 방식이다. 즉 '여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘'이다. 문제 해결을 위한 점화식을 찾아낸 후, 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태의 알고리즘

ex - fibonacci

🐥 피보나치는 1,1,2,3,5,8,13,21,34,55,89, .... 와 같은 수열이다. 점화식은 $a_n = a_{n-1} + a_{n-2}, a_1 = 1, a_2 = 1$ n번째 fibonacci 수를 f(n)이라고 할 때 4번째 fibonacci 수 $f(4)$를 구하는 과정은 아래와 같다. 이 때 fibonacci 수는 여러개의 f(n)로 나누어지므로 ① 최적 부분 구조 조건을 만족. 아래 오른쪽 그림과 같이 동일한 f가 여러 번 반복적으로 사용. 따라서  ② 중복되는 부분 조건도 만족. 예를 들어 f(6)을 구하는 과정에서 f(2)가 여러 번 호출된다. 따라서 dp를 사용해 여러번 호출되는 f(2)를 한 번만 계산해서 별도 메모리에 저장해 이후 f(2)가 계속 계산되는 낭비를 막을 수 있다.

 

🐥 예를 들어 f(99)를 구한다고 했을 때 아래와 같이 두 가지 방식을 사용할 수 있다.

 

① top-down 방식(memoization) - 재귀사용, 함수 종료 조건

#dp-table initialization
d=[0]*100

#fibonacci recursive function (top-down dp)
def fibo(x):
    #exit
    if x==1 or x==2: return 1

    #if sub-problem already solved, get the answer
    if d[x]!=0:return d[x]

    #if not solved, add the results
    d[x]=fibo(x-1)+fibo(x-2)
    return d[x]
    
print(fibo(99))#218922995834555169026

: 메모이제이션 결과 위 색칠된 노드만 방문됨을 확인할 수 있다. 따라서 메모이제이션 기법 사용 시 fibonacci 수열 함수의 시간 복잡도는 O(N) 피보나치 수열의 지수 형태 시간 복잡도를 선형 시간 복잡도로 줄일 수 있다.

 

② bottom-up 방식(tabulation) - 반복문 사용, 첫 항 설정

d=[0]*100

d[1],d[2]=1,1
n=99

#bottom-up dp
for i in range(3,n+1):
    d[i]=d[i-1]+d[i-2]
print(d[n]) #218922995834555169026

dp vs divide-conquer 

🐥 dp와 분할정복 알고리즘 모두 최적 부분 구조를 가질 때 사용할 수 있다(위 조건 ①). 즉, 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황이라면 dp 또는 분할정복을 사용할 수 있는 조건 충족. 그러나 dp문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다(위 조건②) / 그러나 분할 정복 문제는 동일한 부분 문제가 반복적으로 계산되지 않는다. 여러 분할 문제는 서로 별개이다. 예를 들어 분할 정복 대표 문제인 quick sort 문제는, 한 번 기준 원소(pivot)가 자리를 변경해서 자리를 잡으면, 해당 원소의 위치는 바뀌지 않는다. 따라서 분할 이후 해당 pivot을 다시 처리하는 부분 문제는 호출하지 않는다. 하지만 dp는 여러 sub-problem의 결과로 다른 sub-problem 해결의 실마리가 된다. 따라서 dp 문제를 풀기 위한 접근 순서는 아래와 같다.

 

① 주어진 문제가 dp 유형임을 파악 - 최적부분구조 조건을 만족하는 지 / 중복되는 부분 문제 조건을 만족하는 지. 그리고 그리디 / 구현 / 완전탐색 등의 아이디어로 먼저 문제를 해결할 수 있는 지 검토

② dp-table initialization

③ 각 항과의 관계 점화식을 찾기

④ 초깃값 정의: 일반적으로 bottom-up 방식의 dp유형이 많이 출제되므로 초깃값을 적절히 정의한 다음 아래에서 위로 올라가며 값을 쭉 구해나가면 된다.

dp - memoization vs recursion

# Python program to find
# fibonacci number using memoization.
def fibRec(n, memo):
  
    # Base case
    if n <= 1:
        return n

    # To check if output already exists
    if memo[n] != -1:
        return memo[n]

    # Calculate and save output for future use
    memo[n] = fibRec(n - 1, memo) + \
              fibRec(n - 2, memo)
    return memo[n]

def fib(n):
    memo = [-1] * (n + 1)
    return fibRec(n, memo)

n = 5
print(fib(n))

 

: dp-memoization 기법은 recursion과 다르다. recursion 기법이 쓰였을 뿐, recursion 알고리즘 자체를 dp-memoization 기법이라 할 수 없다. recursion으로 재귀를 진행하며 도중에 업데이트 안된 칸이 있다면, 해당 칸만 재귀적으로 진행할 뿐, 업데이트 된 칸은 memoization 기법으로 기억해 놓은 칸의 내용을 바로 사용(위 예시 코드에선 바로 return).

dp vs greedy

 

🐥 dp와 greedy 모두 최적 부분 구조 문제로 부분적으로 선택한 문제의 최적해에 이어서 계속해 더 큰 문제의 최적해를 구한다는 점에서 동일.

 

(1) 하지만, greedy는 당장 탐욕적으로 선택한 부분이 전체 문제의 최적해를 보장하지만, dp 기법으로는 그렇지 않다. 예를 들어 16원이 있고, 동전 단위가 10, 7, 3원이 있다면 당장 10원부터 선택하는게 전체의 greedy 보장. 하지만, 10, 8, 6원이 있다면 당장 10원부터 선택하는게 전체의 greedy 보장이라 말할 수 없다. 따라서 greedy choice property를 만족하는 지 하지 않는 지 greedy는 만족해야 하며, dp는 그렇지 않다.

 

(2) 또한, dp는 각 sub-problem들이 서로 overlapping 되는 성질을 만족해야 한다. 예를 들어 dp는 점화식으로 나타낼 수 있고, dp[x] = dp[x-1] + dp[x-2]와 같이 dp[x]라는 문제 자체가 dp[x-1]과 dp[x-2]의 일부와 overlapping되어 만족한다.

dp exercises

Q. 개미 전사

Q. 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량 창고를 몰래 공격하려고 합니다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있습니다. 각 식량 창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정입니다. 이 때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있습니다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 합니다.

예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정합시다. {1,3,1,5}

이 때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼앗을 수 있습니다. 개미 전사는 식량창고가 이렇게 일직선상일 때 최대한 많은 식량을 얻기를 원합니다. 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하세요.

#my answer
N=int(input())

counts=list(map(int,input().split()))
an=[0]*N #dp-table initialization

for n in range(N):
    if n==0: an[0] = counts[n]
    elif n==1: an[1] = max(an[0],counts[n])
    else:
        an[n] = max(an[n-1],an[n-2]+counts[n]) #an 
print(an[-1])

#answer
n=int(input())
array=list(map(int,input().split()))

#dp-table initialization
d = [0]*100

#bottom-up dp
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])

 

🐥 문제에 의해, 각 창고별로 최대로 털 수 있는 식량의 개수를 a(n)이라고 하자. 그렇다면 n번째 식량 창고에서 아래 두 가지 경우의 수 중 최댓값은 a(n)

a(n) = max(a(n-1), a(n-2)+n)

 

🐥 위 문제는 dp문제로 두 가지 dp 조건을 만족한다. ① 최적 부분 구조 - 위의 두가지 경우에 대해서만 최적의 솔루션을 구하므로 성립 / ② 중복되는 부분 구조 - 위 점화식 수열에 의해 계속 a(n)을 호출할 때 앞에서 고려된 a(n-1)과 a(n-2)가 중복으로 고려되므로 조건 성립. 또한 이는 bottom-up 상향식 dp 문제로 풀 수 있다. a[0]일때부터 최종 a[n]까지 계속 수열 연산을 진행하기 때문에 bottom-up 상향식 dp 구조 문제. 이렇게 dp문제는 문제 상황에 맞게 점화식을 세운 뒤, bottom-up 방식으로 최종 수열값 a(n)을 새롭게 만든 dp-table에서 구하는 유형이 매우 빈번히 등장하므로 기억

Q. 1로 만들기

Q. 정수 X가 주어졌을 때, 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지입니다. (1) X가 5로 나누어 떨어지면, 5로 나눕니다. (2) X가 3으로 나누어 떨어지면, 3으로 나눕니다. (3) X가 2로 나누어 떨어지면, 2로 나눕니다. (4) X에서 1을 뺍니다.

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 값을 1로 만들고자 합니다. 연산을 사용하는 횟수의 최솟값을 출력하세요. 예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값입니다.

26 → 25 → 5 → 1

 

#bottom-up dp
n=int(input())
if n==1:print(0)
elif n==2 or n==3:print(1)
elif n==4:print(2)
else:
    dp=[0]*(n+1)
    dp[2],dp[3],dp[5]=1,1,1
    cnt=0
    for i in range(4,n+1):
        a,b,c,d=30001,30001,30001,30001
        if i%5==0:
            a=dp[i//5]
        if i%3==0:
            b=dp[i//5]
        if i%2==0:
            c=dp[i//2]
        d=dp[i-1]
        dp[i]=min(a,b,c,d)+1
    print(dp[n])

 

🐥 이 문제도 dp의 두가지 조건(최적 부분구조, 중복되는 부분)을 모두 만족한다. 중요한 건, greedy 유형과는 다르다는 점! greedy의 경우 그 어떤 상황이어도 5로 나누는 경우가 1을 빼는 경우보다 매 상황에서 우선시되어야 하는데, 해당 문제는 1을 먼저 빼고 난 다음의 연산 결과가 먼저 5로 나누는 경우의 결과보다 더 최적일 수 있으므로 greedy를 적용할 수 없다. greedy 유형은 여러 상황이 주어졌을 때 최적의 결과를 내기 위해 반드시 상황의 우선순위가 존재할 때 쓸 수 있음 점화식을 세워보면, a(i)를 1로 만들기 위한 최소 연산 횟수라 정의했을 때,

 

a(i) = min(a(i-1), a(i/2), a(i/3), a(i/5)+1)

(단, 1을 빼는 연산을 제외하고는 해당 수로 나누어 떨어질 때에 한해 점화식 적용 가능)

x=int(input())

d=[0]*30001

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)

print(d[x])

Q. 효율적인 화폐 구성

Q. N가지 종류의 화폐가 있습니다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 합니다. 이 때 각 종류의 화폐는 몇 개라도 사용할 수 있습니다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수입니다. M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하세요.

 

🐥 점화식 idea: 만들 수 있는 금액에서, 두 화폐 종류 2와 3이 있다고 할 때, 5를 2와 3으로 만들 수 있는 최소 가짓수는 현재 위치에서 2와 3을 뺀 각각의 최솟값에 1을 더한 결과이다. 즉, 현재 금액에서 화폐 단위를 각각 뺀 경우의 dp table 값의 최솟값에서 1을 더한 결과가 화폐 단위로 만들 수 있는 최소 가짓수로 dp-table을 update할 수 있다.

N,M=map(int,input().split())
dp=[M+1]*(M+1)
coins=[]
i=0
for _ in range(N):
    coin=int(input())
    coins.append(coin)
    i=coin
    if coin<=M:dp[coin]=1

#dp-table initialization from i+1
for cur_coin in range(i+1,M+1):
    cur_min=M+1
    for c in coins:
        if cur_min>dp[cur_coin-c]:
            cur_min=dp[cur_coin-c]
    dp[cur_coin]=cur_min+1    
print(dp)
print(-1 if dp[-1]>M else dp[-1])

 

🐥 먼저 화폐단위에 해당하는 dp table 칸에 1 배치. 그리고 i+1(화폐 단위 최댓값+1)부터 본격적으로 dp table 진행 시작한다. 반복문으로 현재 금액에서 각각 화폐 단위를 뺀 경우 중 최솟값을 찾았다면, 해당 최솟값에서 1을 더한 값을 dp table에 업데이트한다. inf값 넘었으면 화폐단위로 계산할 수 있는 경우가 없다는 뜻이므로 -1 출력, 그렇지 않다면 최종 값 출력. a(i)를 금액 i를 만들 수 있는 최소한의 화폐 개수라고 하자. 점화식은 각 화폐 단위인 k를 하나씩 확인하며 a(i-k)를 만드는 방법이 존재한다면 a(i) = min(a(i), a(i-k)+1). 그리고 a(i-k)를 만드는 방법이 존재하지 않는 경우는 a(i-k) = ∞ 설정

n,m=map(int,input().split())

array=[]
for i in range(n):array.append(int(input()))

#dp table
d=[10001]*(m+1)

#dp (bottom-up)
d[0]=0
for i in range(n):
    for j in range(array[i],m+1):
        if d[j-array[i]]!=10001:#if exists
            d[j]=min(d[j],d[j-array[i]]+1)

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

Q. 금광

Q. nxm 크기의 금광이 있다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다. 채굴자는 첫번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다. 이후에 m-1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하자.

 

for _ in range(int(input())):
    n,m=map(int,input().split())
    l=list(map(int,input().split()))
    golds=[]
    digs=[[0]*m for _ in range(n)]
    length=len(l)
    j,ans=0,0

    #2-dimensional array (golds)
    for i in range(0,length+1,m):
        if j==n:break
        golds.append(l[i:i+m])
        j+=1

    #assign first col    
    for i in range(0,n):
        digs[i][0] = golds[i][0]

    #dp-table - digs (bottom-up)
    for col in range(1,m):
        for row in range(0,n):
            if row==0:
                digs[row][col]=max(digs[row][col-1],digs[row+1][col-1])+golds[row][col]
            elif row==(n-1):
                digs[row][col]=max(digs[row][col-1],digs[row-1][col-1])+golds[row][col]
            else:
                digs[row][col]=max(digs[row][col-1],digs[row+1][col-1],digs[row-1][col-1])+golds[row][col]
    
    #find the maximum value of the last column of 'digs'
    for i in range(0,n):
        ans=max(ans,digs[i][-1])
    print(ans)

 

(오른쪽 그림) dp 2차원 배열 할당 과정

 

🐥 2차원 배열을 다루어야 하는 문제이므로 앞선 문제보다 약간 난이도가 높았다. digs라는 dp-table을 만든다. 이 때 golds[i][j] = i행 j열에 존재하는 금의 양, digs[i][j] = i행 j열까지의 최적의 해는 얻을 수 있는 금의 최댓값으로 설정.

 

① 1열과 마지막 열이 아닌 모든 열의 최적의 금의 양 구하기

digs[i][j] = golds[i][j] + max(golds[i-1][j-1], golds[i][j-1], golds[i+1][j-1])

 

② 1열의 최적의 금의 양 구하기 점화식

digs[i][j] = golds[i][j] + max(golds[i][j-1], golds[i+1][j-1])

 

③ 마지막 열의 최적의 금의 양 구하기 점화식

digs[i][j] = golds[i][j] + max(golds[i-1][j-1], golds[i][j-1])

 

🐥 별도의 dp-table을 만들지 않고 한 dp table update

for tc in range(int(input())):
    #mine info
    n,m=map(int,input().split())
    array=list(map(int,input().split()))

    #dp-table initialization
    dp=[]
    index=0

    for i in range(n):
        dp.append(array[index:index+m])
        index+=m
    
    #dp(bottom-up)
    for j in range(1,m):
        for i in range(n):
            #from upper-left
            if i==0: left_up=0
            else: left_up=dp[i-1][j-1]

            #from lower-left
            if i==n-1:left_down=0
            else: left_down=dp[i+1][j-1]

            #from left
            left=dp[i][j-1]
            
            #dp-table update
            dp[i][j]=dp[i][j]+max(left_up, left_down, left)
        res=0
        for i in range(n):
            res=max(res,dp[i][m-1])
        print(res)

---

이코테 2021

BaaarkingDog