[알고리즘] 🤪이죵의 LCS(Longest Common Substring/Subsequence) 알고리즘을 알아보자🙌

🧶 LCS란 무엇일까?

문자열 알고리즘 문제중에는 연속된 혹은 연속되지 않은 부분 문자열을 찾는 문제가 종종 나온다.

LCS 알고리즘은 그러한 부분 문자열을 찾을때 사용하는 알고리즘이다😋

LCS는 최장 증가 부분 수열과 같이 DP(Dynamic Programming)를 기반으로 한다.

1. 최장 공통 문자열 (Longest Common Substring)
   • 연속된 문자열을 확인하는 방법
   • 공통 문자열은 부분이 아니기 때문에 한번에 이어져 있는 문자열만 가능함.
2. 최장 공통 수열(Longest Common Subsequence)
   • 연속되지 않은 부분문자열을 찾는 방법
   • 문자사이를 건너뛰어 공통되면서 가장 긴 부분 문자열

예를들어 "ABCDFGO"라는 문자열과 "BCDHIGLO"라는 문자열이 있다면..

최장 공통 문자열은 연속된 한번에 이어져 있어야하기 때문에 "BCD"

최장 공통 수열은 연속되지 않아도 되므로 "BCDGO"라는 결과가 나오게 된다.

 

 

그럼 코드로는 어떻게 짜야할까?🤔

 

 

 

🎰 최장 공통 문자열(Longest Common Substring)

최장 공통 문자열 (Longest Common Substring)을 위에 사용한 예제를 기반으로 구현해보자👩‍🔧

 

LCS알고리즘은 2차원 배열을 이용하여 알고리즘을 구성한다.

이전의 연속된 값을 체크하기 때문에 이전값을 가져와 비교하게되므로 배열의 0번째값을 0으로 채워놓아야 범위를 Out of Bounds 에러를 피할수 있다👩‍🏫

	0	A	B	C	D	F	G	O
0	0	0	0	0	0	0	0	0
B	0

 

 

 

이제 한줄씩 LCS를 구해보자

B를 ABCDFGO와 한 글자씩 비교하고 같은 문자가 존재하면 이전의 연속된 문자열의 값에 +1을 해주면 된다.

식으로 적어보자면 LCS[ i ][ j ]의 값은 LCS[ i - 1 ][ j - 1 ] +1의 값을 담아준다

	0	A	B	C	D	F	G	O
0	0	0	0	0	0	0	0	0
B	0	0	1	0	0	0	0	0
C	0

 

 

 

같은 방식으로 C또한 ABCDFGO와 한글짜식 비교하고 같은 문자라면 이전의 LCS값에서 +1을 해주면 된다.

	0	A	B	C	D	F	G	O
0	0	0	0	0	0	0	0	0
B	0	0	1	0	0	0	0	0
C	0	0	0	2	0	0	0	0
D	0

 

 

 

이렇게 순차적으로 검사해준다면 아래의 표가 나오게 된다.

이렇게 나온 표의 최대값의 위치가 최장증가수열의 문자열 끝이 된다.

	0	A	B	C	D	F	G	O
0	0	0	0	0	0	0	0	0
B	0	0	1	0	0	0	0	0
C	0	0	0	2	0	0	0	0
D	0	0	0	0	3	0	0	0
H	0	0	0	0	0	0	0	0
I	0	0	0	0	0	0	0	0
G	0	0	0	0	0	0	1	0
L	0	0	0	0	0	0	0	0
O	0	0	0	0	0	0	0	1

 

 

 

이걸 코드로 작성해보자💨╰(*°▽°*)╯

if(i==0 || j==0){    // 마진설정
	LCS[i][j] = 0;
} else if (stringA[i] == stringB[j]){
	LCS[i][j] = LCS[i-1][j-1] +1;
} else {
	LCS[i][j] = 0;
}

• 문자열 A,B의 한글자씩을 비교한다
• 최장 공통 문자열은 이어지는 문자열이므로 두 문자가 다르다면 LCS[i][j]에 0을 표시한다.
• 만약 두 문자가 같다면 이전에 체크한 LCS[i-1][j-1]값을 찾아 +1을함.
• 위 과정을 통해 최장 공통 문자열을 만들었다면 2차원 배열은 완탐하여 최장 길이를 찾아낼 수 있다.

 

 

🧩 최장 공통 부분수열 (Longest Common Subsequence)

부분수열은 연속되지 않은 값이므로 이전의 최대 공통 부분수열의 값이 계속해서 유지된다.

그러므로 만약 구하려는 부분문자열이 같다면 언제나 최대 공통 부분수열을 가지고 있는 LCS값에서 +1을 해주고

다르다면 이전의 부분수열인 LCS[i-1][j]와 LCS[i][j-1]중 max값을 가져가서 부분수열을 유지시켜주면 된다.

 

 

2차원 배열을 보며 공식을 대입해보자 :)

B를 ABCDFGO와 비교하면 같은 B를 만났을 때 최대 공통 부분수열을 갖는 LCS[i-1][j-1]의 값 +1을 해준다

이후 CDFGO와 비교할때는 동일한 문자열이 아니므로 LCS[i-1][j]와 LCS[i][j-1]중 max값으로 유지시킨다.

	0	A	B	C	D	F	G	O
0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1
C	0

 

 

그럼 이걸 전체적으로 반복하면 최종 2차원 배열의 구성은 이렇게 변하게 된다.👩‍💻

	0	A	B	C	D	F	G	O
0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1
C	0	0	1	2	2	2	2	2
D	0	0	1	2	3	3	3	3
H	0	0	1	2	3	3	3	3
I	0	0	1	2	3	3	3	3
G	0	0	1	2	3	3	4	4
L	0	0	1	2	3	3	4	4
O	0	0	1	2	3	3	4	5

 

 

이걸 코드로 작성해보자💨╰(*°▽°*)╯

if(i==0 || j==0){    // 마진설정
	LCS[i][j] = 0;
} else if (stringA[i] == stringB[j]){
	LCS[i][j] = LCS[i-1][j-1] +1;
} else {
	LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);
}

 

이렇게 해서 최종 공통 부분수열의 문자열의 길이는 5개가 만들어진다🙁...

그렇다면 공통 부분수열의 문자열은 어떻게 구해야할까?

 

 

🧩 최장 공통 부분수열 (Longest Common Subsequence)의 문자열

최장 공통 부분수열의 문자열은 LCS의 가장 마지막 값에서부터 시작하여 LCS[i-1][j]와 LCS[i][j-1] 중 현재의 값과 동일한 값을 찾아서 올라가는 것이다.만약 같은 값이 없다면 LCS[i-1][j-1]로 이동하고 이동하기 전 해당 문자열을 배열에 담아준다.0이 나올때까지 해당 탐색을 반복하고 배열을 뒤집어주면 문자열을 구할 수 있다 😏

 

 

🎈 마치며

알고리즘에서 해당 기법은 의외로 종종 보이는 유형이므로 시간이 된다면 꼭 공부해서 개념을 이해해 놓는것이 좋다고 생각한다.