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 qROD 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
다이나믹 프로그래밍 관련 문제도 몇개 더 풀어야징🐥
참고 |