본문내용
예로서 =A$CMA*MN 이고, =AXMC4ANB를 들을 수 있다고 가정하면, 동적계획법을 사용하여 과 의 최장 공동부분수열을 찾는 알고리즘을 작성하라. 이 알고리즘은 각 수열의 최대길이 공동부분수열을 넘겨준다.
위의 문제를 이해한 결과 s1= abcdef 와 s2= cbcdea 가 있을 때 bcde가 차례대로 나오는 것을 알 수 있습니다. 위의 두 수열을 최장 공동부분수열 알고리즘에 적용하면 s1= abcdef 과 s2= cbcdea 에 bcde가 존재하는 가장 긴 공통부분 순서 임을 알 수 있습니다.
최장공통부분순서(LCS)
1. 최장 공통 부분순서 길이 (재귀적 호출)
func lcs(x,y)
if ( length(x)=0 or length(y)=0 )
return \"\"
best = lcs(x[1,n-1],y[1,m])
if ( length(best) < length(lcs(x[1,n],y[1,m-1])) )
best = lcs(x[1,n],y[1,m-1])
if ( x[n] = y[m] and length(best) < length(lcs(x[1,n-1],y[1,m-1]) + 1 )
best = lcs(x[1,n-1],y[1,m-1]) + x[n]
return best
2. 최장 공통 부분순서 길이 (동적 프로그래밍)
func lcs(x,y)
n = length( x ), m = length( y )
for i from 0 to n
for j from 0 to m
if ( i is 0 or j is 0 )
table[i,j] = \"\"
if ( x[i] == y[j] ) table[i,j] = x[i]
else
/* Sentinel */
table[i,j] = table[i-1,j]
if ( length( table[i,j] ) < length( table[i,j-1] ) )
table[i,j] = table[i,j-1];
if ( x[i] = y[j] and length( table[i,j] ) < length( table[i-1,j-1] ) + 1 )
table[i,j] = table[i-1,j-1] + x[i];
return table[n][m]
LCS 소스 출처
: http://www.algorithmist.com/index.php/Longest_Common_Subsequence
[출처] 동적 프로그래밍 [피보나치 수열, 행렬경로, 조약돌놓기, 최장공통부분순서(LCS)]|작성자 프루케이
위의 문제를 이해한 결과 s1= abcdef 와 s2= cbcdea 가 있을 때 bcde가 차례대로 나오는 것을 알 수 있습니다. 위의 두 수열을 최장 공동부분수열 알고리즘에 적용하면 s1= abcdef 과 s2= cbcdea 에 bcde가 존재하는 가장 긴 공통부분 순서 임을 알 수 있습니다.
최장공통부분순서(LCS)
1. 최장 공통 부분순서 길이 (재귀적 호출)
func lcs(x,y)
if ( length(x)=0 or length(y)=0 )
return \"\"
best = lcs(x[1,n-1],y[1,m])
if ( length(best) < length(lcs(x[1,n],y[1,m-1])) )
best = lcs(x[1,n],y[1,m-1])
if ( x[n] = y[m] and length(best) < length(lcs(x[1,n-1],y[1,m-1]) + 1 )
best = lcs(x[1,n-1],y[1,m-1]) + x[n]
return best
2. 최장 공통 부분순서 길이 (동적 프로그래밍)
func lcs(x,y)
n = length( x ), m = length( y )
for i from 0 to n
for j from 0 to m
if ( i is 0 or j is 0 )
table[i,j] = \"\"
if ( x[i] == y[j] ) table[i,j] = x[i]
else
/* Sentinel */
table[i,j] = table[i-1,j]
if ( length( table[i,j] ) < length( table[i,j-1] ) )
table[i,j] = table[i,j-1];
if ( x[i] = y[j] and length( table[i,j] ) < length( table[i-1,j-1] ) + 1 )
table[i,j] = table[i-1,j-1] + x[i];
return table[n][m]
LCS 소스 출처
: http://www.algorithmist.com/index.php/Longest_Common_Subsequence
[출처] 동적 프로그래밍 [피보나치 수열, 행렬경로, 조약돌놓기, 최장공통부분순서(LCS)]|작성자 프루케이
소개글