[알고리즘] 🤪이죵의 LCS(Longest Common Substring/Subsequence) 알고리즘을 알아보자🙌
🧶 LCS란 무엇일까?
문자열 알고리즘 문제중에는 연속된 혹은 연속되지 않은 부분 문자열을 찾는 문제가 종종 나온다.
LCS 알고리즘은 그러한 부분 문자열을 찾을때 사용하는 알고리즘이다😋
LCS는 최장 증가 부분 수열과 같이 DP(Dynamic Programming)를 기반으로 한다.
- 최장 공통 문자열 (Longest Common Substring)
- 연속된 문자열을 확인하는 방법
- 공통 문자열은 부분이 아니기 때문에 한번에 이어져 있는 문자열만 가능함.
- 최장 공통 수열(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이 나올때까지 해당 탐색을 반복하고 배열을 뒤집어주면 문자열을 구할 수 있다 😏
🎈 마치며
알고리즘에서 해당 기법은 의외로 종종 보이는 유형이므로 시간이 된다면 꼭 공부해서 개념을 이해해 놓는것이 좋다고 생각한다.