Dynamic Programming(1)

다이나믹 프로그래밍의 가장 큰 컨셉은

"subproblem의 결과를 저장해서 사용한다"

 

그래서, 2가지가 가장 중요한 포인트라고 생각하는데,

1. subproblem을 어떻게 만들것인가? (90%)

2. 이걸 어떤 형식으로 저장하고, 사용할 것인가? (10%)

 

subproblem을 어떻게 만들것인가를 아는 순간 2번은 자연스럽게 나올것이라고 생각된다.

 

다이나믹 프로그래밍을 다루는(?) 2방식이 있는데,

첫번째는 "Bottom to Top" 으로 일단 inital부터 내가 구하는 값까지의 데이터를 다 저장한 뒤, 꺼내쓰는 방법

두번째는 "Top to Bottom(memoized)"으로 재귀를 통해 값들을 채워나가는 방법 

 

아마 두번째가 더 많이 쓰이는 것 같기는 한데, 처음 다이나믹 프로그래밍을 다룰때 빠른 이해는 1번. 조금 익숙해지면 2번이 더 간결하고 직관적인 느낌적인 느낌느낌.

 

아무튼 대표적인 Dynamic programming 문제 ROD cutting 과 LCS를 각각 2가지 방식으로 풀어보았다.

문제 : ROD cutting 

나무길이와 나무 길이당 가격이 주어질때 나무를 어떻게 잘라야 가장 높은 가격을 받을 수 있는가?

 

생각해보면 엄청 간단한 subproblem이 보인다.

P에 0부터 충분히 큰수까지의 길이당 price가 있다고 가정

예를들어 ROD(4)를 구한다면,

max( P[1]+ROD(3),P[2]+ROD(2),P[3]+ROD(1),P[4])

P는 바로 구할수 있는거고, 만약 4보다 작은 ROD(n)의 데이터가 있다면, 바로 꺼내쓸수 있다.

 

def b_to_u_rod(length,prices):
    r=[0]
    for i in range(1,length+1):
        q=0
        for j in range(1,i+1):
            q=max(q,prices[j]+r[i-j])
        r.append(q)
    return r[length]

ROD bottom to top 

r : 과거 데이터 저장

for 구문에서 1부터 length까지 하나씩 돌면서, 해당 나무 길이에서의 최대 수익을 리스트 r 에 저장

 

def t_to_d_rod(length,prices,r):
    if r[length]>=0:#값을 가지고 있다면
        return r[length]
    elif length==0:
        q=0
    else:#no value
        q=-10000
        for i in range(1,length+1):
            q=max(q,prices[i]+t_to_d_rod(length-i,prices,r))
    
    r[length]=q
    print(r)
    return q

ROD memoized

재귀방식으로 값을 불러오면서, 계산.

데이터를 저장하는 리스트 r을 매개변수로 받으면서 업데이트

 

문제 : LCS (Longest Common Subsequence)

2개의 문자열, 공통의 subsequence 중 최장 subsequence 길이

(솔직히 이건 좀 어려웠던 기억쓰.. subproblem으로 만드는데도 꽤 걸렸다. 그래서 하나 기억하고 있는건 뒤에서부터 맞추기)

 

하 설명 너무 못하겠다...ㅠ

예를들어 "ABC","BCAC"의 LCS구한다고 했을때,

나는 맨 마지막 원소만 비교를 한다.

만약에 맨마지막 원소가 같다면, 각 문자열의 마지막 원소를 제외한 문자열들의 LCS값+1이 LCS가 될것이다.

LCS("ABC","BCAC")=1+LCS("AB","BCA")

그리고 만약, 맨 마지막 원소가 다르다면, 문자열중 하나씩 마지막 원소를 뺏을때의 최대 LCS값이 LCS가 될것이다.

LCS("AB","BCA")=max(LCS("AB","BC") , LCS("A","BCA"))

 

이런식으로 가다보면, " "이되는 문자열을 만나는 순간 LCS값이 0이 될거고,

이걸 시작으로 차근차근 저장하면,

빠르게 LCS값을 구할수 있다는.. 방법..!

 

저 장황한 설명을 그림으로 표현하면 요렇게!

예를들어 표의(6,1)은 LCS("ABCBDA","B")를 구하는것으로 이해하면 된다.

그러면 맨뒤의 원소들이 다르므로 max (LCS("ABCBD","B"),LCS("ABCBDA",""))값이고,

이미 저장되어있는 표에는 LCS("ABCBD","B")=1 / LCS("ABCBDA","")=0이므로, LCS("ABCBDA","B")=1 이다.

 

장황하다.. 됴르륵

 

아무튼 Python으로 LCS풀이 구현

 

def lcs1(X,Y):
    n=len(X)
    m=len(Y)
    T=[[0 for j in range(m+1)] for i in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,m+1):
            if X[i-1]==Y[j-1]:
                T[i][j]=1+T[i-1][j-1]
            else:
                T[i][j]=max(T[i-1][j],T[i][j-1])
    
    return T[n][m]

LCS Bottom to Top

T 과거데이터 저장 2차원 리스트

똑같이 for 문을 돌면서 T에 차곡차곡 쌓는다.

 

def lcs2(X,Y,T):
    n=len(X)
    m=len(Y)
    if T[n][m]>=0: #값이 있다면
        return T[n][m]
    elif n==0 or m==0:
        T[n][m]=0
    else:

        if X[n-1]==Y[m-1]:
            T[n][m]=1+lcs2(X[:(n-1)],Y[:(m-1)],T)
        else:
            T[n][m]=max(lcs2(X[:(n-1)],Y[:m],T),lcs2(X[:n],Y[:(m-1)],T))

    return T[n][m]

LCS memoized

 

 

 

다이나믹 프로그래밍 관련 문제도 몇개 더 풀어야징🐥

 

참고 | 

https://www.youtube.com/watch?v=ASoaQq66foQ