[Algorithm] LCS (Longest Common Sequence)

DP의 대표 문제 중 하나인 LCS에 대해 다루어 보겠다. 

 

Longest Common Substring

공통 부분 문자열을 찾으라고 했을 때 우리는 보통 longest common substring을 생각하곤 한다. 이는 오늘 알아볼 LCS와는 다른 개념이니 혼동해서는 안된다.

Longest Common Substring은 말 그대로 공통으로 가지고 있는 substring 중 가장 긴 것을 구한다.

이 문제는 DP로 해결할 수 있으며 굉장히 간단하게 구현이 가능하다.

두 문자가 같다면 [j-1][i-1]의 값에 +1을 하는 방식으로 위의 표를 채워나가면 된다. 

 

 

Longest Common Subsequence

1. 기본 개념

그럼 Common Subsequence는 무엇일까? 부분 수열 중 가장 긴 것이라는 뜻은 서로 붙어있지 않고 나열된 순서가 같은 것 중 가장 긴 것을 고르라는 것이다.

위와 substring 과 같은 예제인데, 이번 정답은 BCD가 아닌 BCDF이다. subsequence와 substring의 차이를 명확히 알아두자!

 

2. 문제 풀이 접근 및 점화식 구하기

가장 쉽게 생각할 수 있는 것은 모든 경우에 대해 비교를 하는 것이다. 하지만, 당연히 그건 경우의 수가 너무 많아 시간복잡도가 너무 높아져서 사실 적용을 할 수 없다. 

우리가 주목해야할 점은 수열의 연속 상태가 저장이 되어있다면, 그 부분에 추가하는 방식으로 문제를 해결 할 수 있다는 것이다. 즉, 하위 문제를 줄이기가 가능한 문제이기 때문에 DP를 적용가능하다.

 

점화식은 다음과 같다. 이 점화식만 알면 적용하는 것은 시간문제이다.

 

3. 기본 예제 문제 풀이

x = ABCBDAB
y = BDCABA
인 경우를 해결해보자.

1. table 생성 및 i = 0 또는 j = 0인 부분을 0으로 채운다.

c	y (j=0)	B	D	C	A	B	A
x (i=0)	0	0	0	0	0	0	0
A	0
B	0
C	0
B	0
D	0
A	0
B	0

 

2. i = 1, j = 1부터 차례대로 table을 점화식에 맞게 채워나간다.

• x[i] == y[j] 이면 c[i][j] = c[i-1][j-1] + 1 이다. (왼쪽 대각선 위의 값 + 1)
• x[i] != y[j] 이면 c[i][j] = max ( c[i-1][j], c[i][j-1] ) 이다. (왼쪽과 위의 최댓값)

c[1][1]
=> x[1] != y[1] 이므로 c[0][1]과 c[1][0]의 최댓값을 취한다.
c[1][4]
=> x[1] == y[4] 이므로 c[0][3] + 1을 취한다.

c	y (j=0)	B	D	C	A	B	A
x (i=0)	0	0	0	0	0	0	0
A	0	0	0	0	1	1	1
B	0	1	1	1	1	2	2
C	0	1	1	2	2	2	2
B	0	1	1	1	1	3	3
D	0	1	2	2	2	3	3
A	0	1	2	2	3	3	4
B	0	1	2	2	3	4	4

 

3. Backtracking으로 해당 문자열 찾기

c[len(x)][len(y)]의 값이 LCS의 길이임을 알 수 있다. 하지만, 어떤 수열이 LCS인지 표만 보고 알 수 없다. 그래서 backtracking을 사용해 문자를 추적할 것이다. 

추적하기 위해서는 값을 저장할 때 이 값이 온 방향을 저장해야한다. 방향을 표시하면 아래와 같다. 

지금은 설명을 위해 화살표로 표현했는데, 실제 배열에는 그냥 0, 1, 2 등 숫자로 표현해도 된다. 

우리가 LCS 값을 넣을 때 x[i] == y[j]일 때 왼쪽 위 대각 성분의 값에서 +1을 해주었다. 즉, 대각선으로 내려온 시점이 최장 부분 수열의 일부임을 판단할 수 있다. 그래서 우리가 따로 경로를 표시해두면 대각선으로 이동한 부분을 거슬러 올라가면서 기록하면 된다.

그래서 대각선으로 올라간 부분을 보면 BCBA라는 것을 알 수 있다. 

 

4. 관련 백준 문제들 ( 풀이를 진행할 때 마다 업데이트 예정 )

2023.05.21 - [Computer Science/Baekjoon] - [9251] python : LCS

[9251] python : LCS

2023.05.21 - [Computer Science/Baekjoon] - [9252] python : LCS 2

[9252] python : LCS 2