LCS ( Longest Common Subsequence/Substring) 알고리즘

이 게시글은 게시자의 이해를 위해 작성됨.

" Longest Common Subsequence / Substring "

이는 한국어로 최장 공통 부분수열 / 문자열 이라고 함. ( 주로 최장 공통 부분수열을 말함. )

 

먼저 최장 공통 문자열에 대해 알아보자.

 

---

 

{ 최장 공통 문자열 / Longest Common Substring }

Longest Common Substring

최장 공통 문자열은 위처럼 연결되어있는 문자열이 같은 경우를 말함.

무조건 이어져 있어야함. 최장 공통 부분수열은 떨어져있는 경우도 생각해야하는데

이건 그렇지 않으니까 더 쉬움.

최장 공통 문자열에서 생각해야 하는 것은 두 문자열의 문자가 같은지와 문자가 연속되는지를 생각해야함.

[ 두 문자의 비교 순서 ]

1. 두 문자열의 문자를 하나씩 비교.

2. 두 문자가 다르면 LCS[ i ][ j ] = 0 으로 표시.

3. 두 문자가 같으면 LCS[ i ][ j ] = LCS[ i - 1 ][ j - 1 ] + 1 으로 표시

4. 위 과정 반복.

 

공통 문자열은 연속되어야 하니까 두 문자가 연속해서 같으면 값이 증가되면서 이어지게 될 것이고

두 문자가 같더라도 연속하지 않으면 다시 1부터 시작해서 증가될 것.

 

[ 구현순서 ]

※  첫 문자부터 같다면 LCS[ i -1 ][ j - 1] + 1을 할 때 조건을 또 붙여줘야 하기 때문에 편의를 위해서 마진값을 0으로 설정.

 

1. LNYDS의 L을 LIYDS와 비교 -> 같은 문자가 존재하기에 LCS[i - 1][ j - 1] + 1로 설정.

-	-	L	I	Y	D	S
-	0	0	0	0	0	0
L	0	1	0	0	0	0
N	0
Y	0
D	0
S	0

 

2. LNYDS의 N을 LIYDS와 비교, 같은 문자가 존재하지 않기

-	-	L	I	Y	D	S
-	0	0	0	0	0	0
L	0	1	0	0	0	0
N	0	0	0	0	0	0
Y	0
D	0
S	0

 

3. LNYDS의 Y을 LIYDS와 비교 -> 같은 문자가 존재하기에 LCS[i - 1][ j - 1] + 1로 설정.

-	-	L	I	Y	D	S
-	0	0	0	0	0	0
L	0	1	0	0	0	0
N	0	0	0	0	0	0
Y	0	0	0	1	0	0
D	0
S	0

 

4. LNYDS의 D을 LIYDS와 비교 -> 같은 문자가 존재하기에 LCS[i - 1][ j - 1] + 1로 설정.

-	-	L	I	Y	D	S
-	0	0	0	0	0	0
L	0	1	0	0	0	0
N	0	0	0	0	0	0
Y	0	0	0	1	0	0
D	0	0	0	0	2	0
S	0

 

5. LNYDS의 S을 LIYDS와 비교 -> 같은 문자가 존재하기에 LCS[i - 1][ j - 1] + 1로 설정.

-	-	L	I	Y	D	S
-	0	0	0	0	0	0
L	0	1	0	0	0	0
N	0	0	0	0	0	0
Y	0	0	0	1	0	0
D	0	0	0	0	2	0
S	0	0	0	0	0	3

 

 

---

 

{ 최장 공통 부분수열 / Longest Common Subsequence }

Longest Common Subsequence

이번엔 최장 공통 부분수열을 알아보자. 아까와는 바르게 띄워져있는 문자도 포함되어야 한다.

부분 수열이기에 띄워져있고 공통된 가장 긴 부분수열을 찾으면 된다.

여기서 생각해야할 것은 문자가 공통된다는 것과 떨어져있는 애도 포함해야한다는 것이다.

위에서 봤던 최장 공통 문자열의 흐름을 이용할 것.

 

[ 두 문자의 비교 순서 ]

1. 두 문자열의 문자를 하나씩 비교.

2. 두 문자가 다르면 LCS[ i ][ j ] = LCS[ i - 1 ][ j ]와 LCS[ i ][ j - 1 ] 중 큰 값으로 표시.

3. 두 문자가 같으면 LCS[ i ][ j ] = LCS[ i - 1 ][ j - 1 ] + 1 으로 표시

4. 위 과정 반복.

 

이전 최장 공통 문자열을 구하는 과정에서는 두 문자가 다른 경우 0으로 둬서 연결되지 않은 경우는 값의 증가가 연결되지 않게 만들었지만 최장 공통 부분수열에서는 두 문자가 연결되지 않더라도 이 증가하는 값이 연결되어야함.

그렇기 때문에 다른 경우 LCS[ i ][ j ] = max(LCS[ i - 1][ j ], LCS[ i ][ j - 1 ])을 하라는 것.

 

< LCS[ i ][ j ] = max(LCS[ i - 1][ j ], LCS[ i ][ j - 1 ]) 의 의미 ?? >

앞서 말했던 것처럼 증가가 떨어져 있는 경우에도 연결이 되어야한다. -> 부분수열이기 때문에

-	-	L	I	Y	D	S
-	0	0	0	0	0	0
L	0	1	0	0	0	0
N	0	0	0	0	0	0
Y	0	0	0	1	0	0
D	0
S	0

이전에 최장 공통 문자열에서는 이렇게 1의 값을 끌고 가지 않으니까 L과 Y에서 값이 연결되지 않는 것을 볼 수 있다.

하지만 LCS[ i ][ j ] = max(LCS[ i - 1][ j ], LCS[ i ][ j - 1 ])를 이용하게 된다면 이렇게 연결될 수 있는 것이다.

-	-	L	I	Y	D	S
-	0	0	0	0	0	0
L	0	1	1	1	1	1
N	0	1	1	1	1	1
Y	0	1	1	2	2	2
D	0
S	0

LCS[ i ][ j ] = max(LCS[ i - 1][ j ], LCS[ i ][ j - 1 ])에서

LCS[ i -1 ][ j ]은 무엇을 의미하는가?

위의 표를 보게 되면 LNY와 LI를 비교하는 부분에서 생각을 해보자. 

LCS[ i -1 ][ j ]는 LI와 LN 사이에서의 최대 공통 부분수열을 찾는 것이다. 이때 최대 부분 수열은 L이다.

LCS[ i  ][ j - 1 ]은 L과 LNY 사이에서의 최대 공통 부분수열을 찾는 것이다. 이때 최대 부분 수열은 L이다.

이 두개를 비교하는 과정이 꼭 필요하다.

LIYD와 LNY를 비교할 때를 생각해보면 LCS[ i ][ j - 1]인 경우가 더 크다. 

(LIY, LNY) > (LIYD, LN) 현재 비교중인 문자가 같은 경우엔 이 경우가 더 커지고

현재 비교중인 문자가 같지 않은 경우엔 LCS[ i - 1 ][ j ]가 더 커진다.

LCS[ i - 1 ][ j ]은 이전의 최대 부분 수열을 들고 오기 위함이고 LCS[ i ][ j - 1 ]은 현재 비교중인 문자가 공통이 되었을 때 최대값을 끌고 가기 위함이다.

 

< 같을 때 LCS[ i ][ j ] = LCS[ i - 1 ][ j - 1 ] + 1 인 이유 ?? >

문자가 같은 상황에서는 지금까지 최대 공통 부분수열에 1을 더해줘야한다.

같지 않은 경우엔 이전의 값들을 가지고 끌고 가기 위해서 두 값들의 최대 값을 가지고 갔다.

하지만 같은 경우엔 이전 최대 공통 부분수열에서 값을 더해줘야한다.

LIY, LNY를 생각하면 마지막에 비교하는 문자를 빼고 그전에 가장 큰 공통 부분수열을 가지고 올 수 있는 문자열은

LI, LN 사이의 최대 공통 부분수열이고 여기에서 마지막 문자를 비교한 값을 더해줘야 하기 때문에

이와 같은 식이 나온다.

 

이와 같이 구하면 최장 공통 부분수열을 구할 수 있다.

 

 

---

 

{ 최장 공통 부분수열 / Longest Common Subsequence  값을 찾기 }

이전에는 길이만을 찾을 수 있었는데 거기에서 부분수열 값을 찾으려면 추가적인 구현이 필요하다.

 

[ 부분수열 찾는 순서 ]

1. LCS 마지막 값에서 시작.

2. 현재 값과 LCS[ i -1 ][ j ]와 LCS[ i ][ j -1 ] 중 같은 값을 찾기.

3. 같은 값이 존재하면 해당 값으로 이동.

4. 만약 같은 값이 없다면 해당 문자를 저장하고 LCS[ i - 1 ][ j - 1]로 이동

5. 위 과정 반복. -> 값이 0이 되면 종료.

 

이 과정이 성립하는 이유는 LCS[ i -1 ][ j ]와 LCS[ i ][ j -1 ] 중 같은 값을 계속 넣어갔음. 그 뜻은 똑같지 않은 애들에는 이 값들로 쭉 채워졌을 것이란 뜻이고 그렇기 때문에 이 연결된 것이 끝났을 때, 공통 부분수열의 원소가 등장하고 거기에서 LCS[ i - 1 ][ j - 1]로 이동해야 그 전의 부분수열을 찾을 수 있음.