동적 계획 알고리즘(DP/Dynamic Programming)

동적 계획 알고리즘(DP)

 

주어진 문제를 부분 문제로 나누어서 푼 다음, 그 결과로 주어진 문제를 푸는 방법

부분 문제의 정보를 저장->시공간적 효율 증가

memoization 활용

최적 부분 구조(기본 문제의 최적해가 부분 문제의 최적해를 포함)

 

 

DP 적용 여부 판단 방법

 

1.문제를 같은 형태의 하위 구조로 나눌 수 있는가

2.하위 문제의 계산이 반복되는가

(최적화, 최대화, 최소화, 어떡 작업의 경우의 수를 구하는 문제인가 *애매한 경우에 참고할 수 있는 대표적인 DP 문제 유형)

 

 

DP 적용 과정

 

1. 점화식 / 재귀 과정 정의

 - 문제를 Top-Down(하향식/재귀) 으로 정의한다

 - 문제 풀이에 필요한 기본적인 문제의 하위 부분 값을 초기화

 - 종료 조건 추가

2. memoization 적용

3. bottom-up(상향식/반복문) 즉, DP 로 풀이

 

 

동적 계획법의 사용

1. 피보나치 수열

재귀 함수로 표현하면 f(1), f(2) 등 하위 부분이 반복적으로 계산 -> 비효율적

dp[i]=dp[i-1]+dp[i-2] 로 풀이 가능

 

 

2. 역간 거리 최솟값 문제

0~n-1 까지 n개의 역이 존재하고 한 방향(단방향 그래프)으로 이동할 떄, 역부터 역 사이 거리의 최솟값을 구하는 문제

 

naive하게 접근하면, 0에서 4까지 이동하려고 할 때, (0,3)+(3,4) / (0,2)+(2,4) / (0,1)+(1,4) 의 경우를 비교할 수 있고 이는 또 ((0,1)+(1,3))+(3,4) 등으로 작게 나누어질 수 있다. 계산의 반복이 잦기 때문에 최적화가 필요하다.

 

naive한 풀이법 코드

n=4

cost=[[0,10,75,94],[-1,0,35,50],[-1,-1,0,80],[-1,-1,-1,0]]

def minCost(s,d):
	if(s==d or s==d-1):
        return cost[s][d]

    min_value=cost[s][d]
    for i in range(s+1,d):
        temp=minCost(s,i)+minCost(i,d)
        min_value=min(temp,min_value)
    return min_value

print(minCost(0,3))

 

memoization을 사용하여 재귀적으로 구현하면 하위 문제의 반복 계산을 피하면서 문제를 구체화할 수 있다.

memo라는 2차원 리스트를 만들어서 계산한 cost 값을 저장해주고 memo 값이 있으면 더 계산하지 않고 바로 그 값을 return 해주면 된다.

 

memoization 풀이법 코드

n=4
cost=[[0,10,75,94],[-1,0,35,50],[-1,-1,0,80],[-1,-1,-1,0]]
memo=[[0]*4 for _ in range(n)]

def minCost(s,d):
    if s==d or s==d-1:
        return cost[s][d]
    if not memo[s][d]:
        value=cost[s][d]
        for i in range(s+1,d):
            temp=minCost(s,i)+minCost(i,d)
            value=min(value,temp)
        memo[s][d]=value

    return memo[s][d]

print(minCost(0,3))

memoization도 재귀 호출에 의한 메모리 소모로 인해 속도가 느릴 수 있다.

이를 해결하기 위해 DP 방법을 사용한다.

 

dp 풀이법 코드

n=4
cost=[[0,10,75,94],[-1,0,35,50],[-1,-1,0,80],[-1,-1,-1,0]]
mincost=[10**6]*n
mincost[0]=0
mincost[1]=cost[0][1]

for i in range(2,n):
    mincost[i]=cost[0][i]
    for j in range(1,i):
        mincost[i]=min(mincost[j]+cost[j][i],mincost[i])

print(*mincost)

 

 

3. 배낭 문제

각 물건의 가중치와 무게가 주어졌을 때, 가방에 최대한 많은 물건을 담을 수 있도록 하는 문제

-배낭의 무게와 물건의 무게를 비교하여 담을 수 있는지 판단한다

-배낭에 새로 물건을 넣지 못하면 이전 값을 그대로 사용

 

이를 재귀적으로 구현하면

w=[1,4,3]
v=[15,30,20]

def knapsack(w,v,n,c):
    if(n<=0 or c<=0):
        return 0
    if w[n-1]>c:
        return knapsack(w,v,n-1,c) 
    carry=v[n-1]+knapsack(w,v,n-1,c-w[n-1]) #집어넣은 물건 만큼 용량 빼줌
    leave=knapsack(w,v,n-1,c) #물건 넣지 않고 다음으로 넘어감
    print(carry,leave)
    return max(carry,leave)
    
print(knapsack(w,v,3,4))

이와 같이 구현 할 수 있다.

 

이를 일반화하면, cell[i][j]의 max 값은 

-지금 까지 구한 cell[i-1][j]의 값 중 max 값

-현재 물건의 가치 + 남은 공간의 가치(cell[i-1][j-물건무게]) 

를 비교한 값이다. 

 

DP로 구현한 코드

w=[1,4,3]
v=[15,30,20]

def knapsack(w,v,n,c):
    cell=[[-1]*(c+1) for _ in range(n+1)]
    for i in range(n+1):
        cell[i][0]=0

    for j in range(c+1):
        cell[0][j]=0

    # cell#초기화
    for i in range(1,n+1):
        for j in range(1,c+1):
            if w[i-1]<=j: #배낭 안에 들어올 수 있으면
                x=j-w[i-1]
                ##남는 공간
                cell[i][j]=max(cell[i-1][j],v[i-1]+cell[i-1][x])
            else:
                cell[i][j]=cell[i-1][j] #배낭에 넣지 못하면 그대로 이전값
    print(*cell)
    
    knapsack(w,v,3,4)

 

 

4. 부분문자열 문제

어떠한 문자열이 주어졌을 때, 부분 문자열의 합이 같도록 문자열을 선택할 때, 그 길이가 최대가 되도록 하는 문제

(즉, [0-3]의 문자열을 선택하면 [0-1]까지 문자열의 합과 [2-3]까지 문자열의 합이 같고 부분 문자열의 길이는 4)

 

이 문제는 단순하게 bruteforce 방식으로 모든 경우의 수를 다 탐색하면서 결과를 구할 수 있다.

모든 경우의 수를 다 탐색하고 이가 3중 for문으로 구현되기 때문에 O(n^3)의 시간복잡도를 지닌다.

 

bruteforce 코드 구현

string='9430726'

def maxSubstring(string):
    n=len(string)
    result=0

    for i in range(n):
        for j in range(i+1,n,2):
            leng=j-i+1 #현재 부분 문자열의 길이
            if(result>=leng):
                continue
            lsum=0;rsum=0
            for k in range(leng//2):
                lsum+=int(string[i+k])
                rsum+=int(string[i+k+leng//2])
            if lsum==rsum:
                result=leng
        
    return result

print(maxSubstring(string))

 

문제를 자세히 들여다보면, 이미 탐색했던 부분 문자열들에 대해서는 

dp[i][j]=dp[i][k]+dp[k][j] 로 점화식을 세울 수 있다.

이때 k는 i-j의 길이의 절반으로 두 문자열을 나누는 기준이며 

dp[i][k] 값과 dp[k+1][j]의 값이 같으면 부분 문자열의 합이 같으므로 기존의 result값과 비교하여 갱신해준다.

이는 2중 for문으로 구현할 수 있기 때문에 O(n^2)의 시간복잡도를 갖는다.

 

dp코드 구현

string='9430726'

def maxString(string):
    result=0
    n=len(string)
    dp=[[0]*n for _ in range(n)]
    for i in range(n):
        dp[i][i]=int(string[i]) #자기 자신 값으로 초기화 =

    for leng in range(2,n+1):
        for i in range(n-leng+1):
            j=i+leng-1
            k=(i+j)//2
            #j,k
            dp[i][j]=dp[i][k]+dp[k+1][j]
            if dp[i][k]==dp[k+1][j] and leng%2==0:
                result=max(result,leng)
    print(dp)
    return result
print(maxString(string))

 

 

5. 최소비용경로

(0,0)에서 (m-1, n-1) 까지 이동할 때, 최소 비용을 구하는 문제이다. 이 떄 이동할 수 있는 방법은 (+1,0) 또는 (0,+1) 로 두가지 방향으로만 이동 가능하다.

 

[x][y]로 이동하는 경우에 [x-1][y]까지 이동한 비용에 cost[x][y]와 [x][y-1]까지 이동한 비용에 cost[x][y]를 더한 값을 비교하여 더 작은 값으로 갱신해주면 된다.

 

이를 재귀적으로 구현하면

m=3
n=4
cost=[[1,3,5,8],[4,2,1,7],[4,3,2,3]]

def minPath(cost,m,n):
    if m==0 and n==0:
        return cost[0][0]
    if m==0:
        return minPath(cost,0,n-1)+cost[0][n]
    if n==0:
        return minPath(cost,m-1,0)+cost[m][0]
    
    x=minPath(cost,m-1,n)
    y=minPath(cost,m,n-1)

    return min(x,y)+cost[m][n]

print(minPath(cost,m-1,n-1))

위와 같이 작성할 수 있다.

 

이는 하위 부분의 계산이 반복되기 때문에

memoization 기법을 사용하여 구현하면

m=3
n=4
cost=[[1,3,5,8],[4,2,1,7],[4,3,2,3]]
memo=[[0]*n for _ in range(m)]

def minPath(cost,m,n):

    if memo[m][n]!=0:
        return memo[m][n]
    ##이전에 계산되었다면 반복 계산 X 바로 결과 return
    if m==0 and n==0:
        memo[m][n]=cost[0][0]
        
    elif m==0:
        memo[m][n]=minPath(cost,0,n-1)+cost[0][n]
    elif n==0:
        memo[m][n]=minPath(cost,m-1,0)+cost[m][0]
    else:
        x=minPath(cost,m-1,n)
        y=minPath(cost,m,n-1)
        memo[m][n]=min(x,y)+cost[m][n]
        #둘 중 더 작은 값으로 선
    return memo[m][n]
print(minPath(cost,m-1,n-1))

위처럼 memo 배열을 만들어서 이전에 계산되었던 값들은 더이상 계산하지 않고 바로 return 할 수 있다.

 

이를 반복문과 다음의 점화식

dp[x][y]=min(dp[x-1][y],dp[x][y-1])+cost[x][y]

을 사용하여 DP로 구현해보면

m=3
n=4
cost=[[1,3,5,8],[4,2,1,7],[4,3,2,3]]

dp=[[10**6]*n for _ in range(m)]
def minPath(cost,m,n):
    dp[0][0]=cost[0][0]
    for i in range(1,m):
        dp[i][0]=dp[i-1][0]+cost[i][0]
    for j in range(1,n):
        dp[0][j]=dp[0][j-1]+cost[0][j]
    for x in range(1,m):
        for y in range(1,n):
            dp[x][y]=min(dp[x-1][y],dp[x][y-1])+cost[x][y]

    return dp[m-1][n-1]

print(minPath(cost,m,n))

이렇게 구현할 수 있다.

이때, dp[0][0] 값은 자기 자신의 비용이므로 cost[0][0]으로 초기화해준다.

0번째 행이나 0번째 열의 값은 이동이 한 방향으로 제한적이므로 그에 맞게 점화식을 세워준다.

 

 

6. 타일채우기

높이가 2이고 너비가 n인 바닥이 있을 때, 높이가 2이고 너비가 1인 타일으로 바닥을 채울 수 있는 경우의 수를 구하는 문제

 

너비가 1인 경우에는 한가지,

너비가 2인 경우에는 ||,= 으로 두가지 이므로 이 값을 초기화해두고

그 다음 타일부터는 i-1 너비의 바닥을 채우는 경우의 수와 i-2 너비의 바닥을 채우는 경우의 수를 더한 값과 같다.

 

즉, 피보나치 수열과 비슷한 점화식 

dp[i]=dp[i-2]+dp[i-1]

을 사용할 수 있고 이 식에서 초기화 값 (dp[1],dp[2])만 다른 문제이다.

 

DP코드

def tilePlacement(n):
    tiles=[0]*(n+1)
    tiles[1]=1
    tiles[2]=2

    for i in range(3,n+1):
        tiles[i]=tiles[i-1]+tiles[i-2]
    print(tiles)
    return tiles[n]

print(tilePlacement(5))

 

 

7. 특정 점수에 도달하는 경우의 수

한 번에 얻을 수 있는 점수가 3점, 5점, 10점이라고 할 때, 특정 점수에 도달하는 경우의 수를 구하는 문제이다.

score(i-3) + score(i-5) + score(i-10) 값을 더하여서 socre(i)의 값을 구할 수 있다.

 

이를 재귀적으로 표현하면

def score(n):
    if n<0:
        return 0
    elif n==0:
        return 1
    else:
        return score(n-3)+score(n-5)+score(n-10)

위와 같이 표현할 수 있다.

 

재귀 대신 반복문을 사용하여 하위 문제의 반복 계산을 피하도록 

def score(n):
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(1,n+1):
        if i-3>=0:
            dp[i]+=dp[i-3]
        if i-5>=0:
            dp[i]+=dp[i-5]
        if i-10>=0:
            dp[i]+=dp[i-10]
    return dp

이처럼 표현할 수 있다.

 

재귀에서는 0보다 같은 값이나 작은 값이 들어오면 바로 0이나 1을 return 해주었고

DP에서는 i값이 3,5,10보다 큰지 비교하여 각 값보다 크면 dp[i-3]을 더해주는 방식으로 구현하였다.

 

 

 

8. 최대 연속 부분 수열의 합

연속되는 부분 수열의 합이 최대가 되도록 부분 수열을 선택하는 문제이다.

 

naive하게 접근하면 모든 부분 수열의 경우를 탐색하여 최대가 되는 방법을 찾을 수 있다.

n=8
arr=[-2,-3,4,-1,-2,1,5,-3]

def maxsub():
    temp=result=0
    for i in range(n):
        for j in range(i,n):
            temp=0
            for k in range(i,j+1):
                temp+=arr[k]
            result=max(temp,result)
    return result
print(maxsub())

####->비효율적인코드

이를 더 효율적으로 구현하는 방법은 현재 위치까지의 부분수열의 합을 정하는 arr 변수를 만들어서 이 값이 0보다 작아지면 이보다 큰 경우가 존재할 수 있으므로 arr 변수를 0 값으로 바꾸어주면서 탐색을 진행하는 방법이다.

 

n-1까지 for문을 돌면서 result 값과 현재의 arr 값을 비교하여 값을 갱신하기 때문에 for문을 빠져나온 뒤의 result 값이 최대 연속 부분 수열의 합이다. 

n=8
arr=[-2,-3,4,-1,-2,1,5,-3]

def maxsub():
    curr=result=0

    for i in range(n):
        curr+=arr[i]
        if curr<0:
            curr=0
        result=max(result,curr)
        
    return result

print(maxsub())