[알고리즘] 다이나믹 프로그래밍 적용 문제 (4) 최장 공통 부분순서 LCS

다이나믹 프로그래밍 적용 문제 (4) 최장 공통 부분순서 LCS

 

문제 설명

부분순서와 공통 부분순서의 예시는 다음과 같다.

<BCDB>는 문자열 <ABCBDAB>의 부분순서.

<BCA>는 문자열 <ABCDBAB>와 <BDCABA>의 공통 부분순서.

 

최장 공통 부분순서(Longest Common Subsequence)란 공통 부분순서들 중 가장 긴 것을 말한다.

 

예를 들어, 다음 두 문자열의 LCS를 구하면 다음과 같다.

h e r o i c a l l y

s c h o l a r l y

결과 문자열 : holly, LCS : 5

 

주어지는 두 문자열의 LCS를 구하라.

 

 

점화식

LCS(i, j) : 문자열  X[i] = "x1,x2, … ,xi" 과 Y[j] = "y1,y2, … ,yj" 의 LCS 길이

LCS(i, j) = {

    0    ( if  i = 0 or j = 0 )

    LCS(i-1, j-1) + 1    ( if  i, j > 0 and x[i] = y[j] )

    max{ LCS(i-1, j), LCS(i, j-1) }    ( if  i, j > 0 and x[i] ≠ y[j] )

}

 

 

LCS : 재귀적 알고리즘 (효율적 측면에서 부적합)

LCS(i, j) { 
        if (i = 0 or j = 0) then 
			return 0; 
        else if (x[i]= y[j]) then 
			return LCS(i-1, j-1) + 1; 
        else 
			return max( LCS(i-1, j), LCS(i, j-1) ); 
} 
print ( LCS(m, n) );

 

 

LCS : 다이나믹 프로그래밍

for i ← 0 to m
	C[i,  0] ← 0; 
for j ← 0 to n 
	C[0,  j] ← 0; 

for i ← 1 to m {
	for j ← 1 to n 
		if (x[i]= y[j]) then C[i,  j] ← C[i-1,  j-1] + 1;  
			else C[i,  j] ← max(C[i-1,  j], C[i,  j-1]); 
}
print (C[m, n]);

 

 

문제 예시1

주어진 문자열

X = "AABACA"

Y = "ABCAB"

	∮	A	B	C	A	B
∮	0	0	0	0	0	0
A	0	1	1	1	1	1
A	0	1	1	1	2	2
B	0	1	2	2	2	3
A	0	1	2	2	3	3
C	0	1	2	3	3	3
A	0	1	2	3	4	4

LCS = 4

 

 

문제 예시2

주어진 문자열

X = "ADFGT"

Y = "AFOXT"

	∮	A	F	O	X	T
∮	0	0	0	0	0	0
A	0	1	1	1	1	1
D	0	1	1	1	1	1
F	0	1	2	2	2	2
G	0	1	2	2	2	2
T	0	1	2	2	2	3

LCS = 3

 

 

문제 예시3

주어진 문자열

X = "SPRINGTIME"

Y = "PIONEER"

	∮	P	I	O	N	E	E	R
∮	0	0	0	0	0	0	0	0
S	0	0	0	0	0	0	0	0
P	0	1	1	1	1	1	1	1
R	0	1	1	1	1	1	1	2
I	0	1	2	2	2	2	2	2
N	0	1	2	2	3	3	3	3
G	0	1	2	2	3	3	3	3
T	0	1	2	2	3	3	3	3
I	0	1	2	2	3	3	3	3
M	0	1	2	2	3	3	3	3
E	0	1	2	2	3	4	4	4

LCS = 4

 

 

문제 예시4

주어진 문자열

X = "XYZABCB"

Y = "ABCXYZAY"

	∮	A	B	C	X	Y	Z	A	Y
∮	0	0	0	0	0	0	0	0	0
X	0	0	0	0	1	1	1	1	1
Y	0	0	0	0	1	2	2	2	2
Z	0	0	0	0	1	2	3	3	3
A	0	1	1	1	1	2	3	4	4
B	0	1	2	2	2	2	3	4	4
C	0	1	2	3	3	3	3	4	4
B	0	1	2	3	3	3	3	4	4

LCS = 4