[Algorithm] LCS(Longest Common Subsequence)

Longest Common Subsequence vs Longest Common Substring

LCS 알고리즘에는 주로 Longest Common Subsequece(최장 공통 부분 수열) 을 의미하지만, 가끔 Longest Common Substring(최장 공통 부분 문자열)을 의미하기도 한다.

 

1. Longest Common Substring

두 문자열 사이에 공통적인 연속된 부분 문자열을 말한다. 

포인트는 '연속된' 이다. 

'ABCDE'와 'BGCDE' 의 최장 공통 부분 문자열은 'CDE'가 될 것이다.  

 

2. Longest Common Subsequece 

두 문자열 사이에 공통적인 부분 문자열을 말한다. 이는 연속적일 필요가 없다.
하지만 순서가 뒤바뀐 것은 인정하지 않는다. ex) EDCB

'ABCDE'와 'BGCDE' 의 최장 공통 부분 수열은 'BCDE'가 될 것이다.  

 

 

 

LCS는 어떻게 풀까? 

LCS는 DP를 사용하여 해결한다. 두 개의 풀이 과정은 비슷하지만, 약간의 코드에서 차이가 있다. 

(두 개의 차이는 아래 

그 과정에 대해서 표 그림과 코드를 통해 이해해보자!

 

 

1) DP 테이블 초기화

 

처음에는 DP 테이블을 초기화해야 한다.

이 단계를 거치기 전에는 각각의 문자열 앞에 빈문자열이나 '.' 과 같이 다른 문자열로 채워둬야한다. 

이 과정은 인덱스를 단순화하기 위해서 편의상 둔다.

 

테이블의 0인덱스의 열과 행은 모두 0으로 채우도록 한다.

그럼 아래와 같이 테이블이 만들어질 것이다. 

 

이를 코드로 나타내면 어떻게 될까? ( 입력으로 받는 문자열을 string1, string2라고 가정하여 코드를 작성하였다. )

이 코드의 경우에는 모든 테이블의 값을 임의로 0으로 채웠다.

string1 = '.' + string1; // string1 = 'BGCDE'
string2 = '.' + string2; // string2 = 'ABCDE'

const dp = new Array(string1.length + 1).fill(0).map(() => new Array(string2.length).fill(0);

/* dp = [
         [0,0,0,0,0,0], 
         [0,0,0,0,0,0], 
         [0,0,0,0,0,0], 
         [0,0,0,0,0,0], 
         [0,0,0,0,0,0],
         [0,0,0,0,0,0]
         ]
*/

 

 

2) 두 개의 부분 문자열 비교하여 칸에 숫자 채우기

 

이제 반복문을 통해 테이블을 돌면서 해당 열과 행에 해당하는 값의 비교 결과 값을 dp[i][j] 칸에 알맞는 값을 넣어야한다. 

그림을 통해 알기 쉽게 봐보자!

 

초기화해준 테이블을 하나씩 돌며 칸에 맞는 값을 찾는 로직을 반복한다. 

테이블을 도는 순서는 아래와 같이 왼쪽 상단 부터 시작해서 오른쪽으로 이동하며 열을 다 돌면 아래 행으로 이동해서 다시 열을 돌며 로직을 반복한다. 

 

일단 이중 for문을 통해 테이블을 하나씩 돈다.

for(let i=0; i<string1.length; i++) {
	for(let j=0; j<string2.length; j++) {
    	// 로직 구현
    }
}

 

 

Q1. 그렇다면 해당 칸은 무엇을 의미할까?

 

예를 들어 테이블의 3번째 열, 4번째 행의 칸이라고 한다면, 이 칸은 string1의 3번째 인덱스까지의 문자열('AB')과 string2의 인덱스 4번째까지의 문자열('BGC') 의 LCS 값을 말한다.

 

이 칸은 코드로 보면 테이블의 3번째 열, 4번째 행의 칸이라고 하여 DP[3][4]으로 표현한다. 

그럼 위에 이중 for문으로 돌았을 때, 각각의 도달한 칸은 DP[i][j] 가 될 것이다. 

 

Q2. 이 칸에는 어떤 로직을 통해 값을 넣을까?

 

string1[i]와 string2[j]을  비교하고, 조건에 따른 점화식을 통해 계산한 값을 해당 칸에 채운다.  

 

(1) if( string1[i] === string2[j] )

 

해당 조건에 대한 점화식을 먼저 보자

if(string1[i] === string[j]) {
   DP[i][j] = DP[i - 1][j - 1] + 1;
}

 

그림을 통해 보면 왼쪽 위에 있는 값에 +1을 더한 값을 채운다. 

 

왜 왼쪽 위에 있는 DP[i-1][j-1] 값에 1을 더할까?

 

아래의 비교하는 두 문자가 다를 경우, DP[i][j]는 근처 칸의 최댓값을 채운다. 

즉, 이는 DP[i][j]이던, DP[i-1][j-1]이던 열과 행의 값이 같은 칸의 값은 자신이 최댓값을 갖고 있기 때문에, 해당 조건에는 다른 비교 없이 이미 최댓값인 DP[i-1][j-1]에 1을 더한 값을 채우면 되는 것이다.

 

이 부분이 이해가 가지 않는다면 두 문자가 다른 경우를 보자!

 

 

 

(2) if( string1[i] !== string2[j] )

 

해당 과정까지는 Longest Common Sequence 와 Longest Common Substring 을 구하는 것은 동일했다.

하지만 해당 조건에서의 두 개의 점화식은 다르다. 

 

 

- Longest Common Substring

최장 공통 부분 문자열은 연속된 문자열을 구해야한다. 

때문에, 비교하려는 두 문자가 같지 않다면 지금까지의 최댓값은 기억할 필요 없이 바로 0으로 채운다. 

if(string1[i] !== string[j]) {
   DP[i][j] = 0;
}

 

해당 두 개의 조건에 따른 점화식을 적용해보면 아래와 같다. 

연속된 문자열의 길이가 잘 출력됨을 알 수 있다. 

 

 

 

- Longest Common Sequence

 

최장 공통 부분 수열은 연속되지 않아도, 같기만 하면 result 값에 추가 된다.

그렇기 때문에 문자열이 다르더라도 해당 칸은 지금까지의 최댓값을 기억하고, 마지막까지 전달해주어야한다. 

if(string1[i] !== string[j]) {
   DP[i][j] = Math.max(DP[i-1][j], DP[i][j-1]);
}

 

해당 점화식을 적용한 결과 값은 아래와 같다. 

공통 부분 문자열과 달리 비교하는 두 문자가 같으면 그 최댓값을 계속 기억해서 그 값에 +1 을 해준다. 

 

 

 

LCS 알고리즘과 이중 for 문을 통한 문자열 비교의 시간 복잡도

LCS 알고리즘을 사용하여 공통 부분 수열을 찾을 때와 이를 사용하지 않고, 그냥 이중 for문을 돌려 하나하나 문자를 비교하는 것은 얼마나 차이가 클까?

 

LCS 알고리즘

두 문자열의 길이가 각각 n과 m이라고 하면 DP 테이블을 채우기 위해 필요한 시간 복잡도는 O(n*m)이다.

테이블 저장을 위한 공간 복잡도도 필요하다. 공간 복잡도 또한 O(n*m)이다.

 

이중 for문

똑같이 두 문자열의 길이가 각각 n과 m이라고 하면 각각의 문자 조합에 대한 부분 집합을 고려하는 추가적인 연산이 필요하기 때문에 이를 위해 필요한 시간 복잡도는 O(n × m × min(n, m)) 이다.

 

 

그렇기 때문에 알고리즘 문제를 풀 때 만약 최장 공통 부분 문자열이나, 수열을 구하는 문제다!! 싶으면 바로 LCS 알고리즘을 이용하는 것이 효율적일 것 같다. 

 

 

📚 참고 자료

https://chanhuiseok.github.io/posts/algo-34/

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence