🎯 LCS 알고리즘

LCS 알고리즘은 최장 공통 부분수열(Longest Common Subsequence), 혹은 최장 공통 문자열(Longest Common Substring)을 의미한다. 문자열 하나하나 모두 비교를 하다보면 시간복잡도가 최대 O(n^4)이 되기때문에 DP를 이용하는 것을 추천한다.

🎯 최장 공통 문자열 구하기

최장 공통 문자열을 구하는 과정은 상당히 쉽다. 최장 공통 부분수열을 구하기 이전에 다루고 가면 도움이 될 것 같아서 정리를 해보고자 한다.

  • 문자열A와 문자열B를 한글자씩 비교한다.
  • 두 문자가 다르다면 LCS[i][j]에 0을 표시한다.
  • 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아서 해당 값보다 +1한 값을 LCS[i][j]에 넣는다.
  • 위 과정을 이중배열 끝까지 반복한다.

위 과정이 공통 문자열을 구하는 것에서 성립되는 이유는 공통 문자열은 문자가 모두 연속되어야 하는 특성때문이다. 현재 두 문자가 같을 때 두 문자의 앞글자까지가 공통 문자열이라면 계속 공통 문자열이 이어질 것이고, 아니라면 본인부터 다시 공통 문자열을 만들어 가게 된다.

🎯 최장 공통 부분수열 길이 구하기

최장 공통 부분수열도 최장 공통 문자열과 마찬가지로 LCS라는 2차원 배열에 매칭하고 마진값을 설정한 후 검사한다.

  • 문자열A와 문자열B를 한글자씩 비교한다.
  • 두 문자가 다르다면 LCS[i-1][j]와 LCS[i][j-1] 중에 큰 값을 표시한다.
  • 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아 +1한 값을 LCS[i][j]에 넣는다.
  • 위 과정을 이중배열 끝까지 반복한다.

💎 LCS[i - 1][j]와 LCS[i][j-1]은 무슨 의미일까?

부분 수열은 최장 공통 문자열과 다르게 연속되 값을 의미하지 않는다. 때문에 현재의 문자를 비교하는 과정 이전의 최대 공통 부분수열은 계속해서 유지된다. 현재의 문자를 비교하는 과정 이전의 과정이 바로 LCS[i-1][j]와 LCS[i][j-1]가 된다.

💎 왜 문자가 같으면 LCS[i][j] = LCS[i-1][j-1] + 1인가?

최대 공통 문자열을 구할 때 비교하는 문자가 같으면 LCS[i][j] = LCS[i-1][j-1] + 1의 과정을 거쳤다. 이 과정이 어떻게 최대 공통 부분수열에도 똑같이 적용될까? 답은 간단하다. 두 문자가 같은 상황이 오면 지금까지의 최대 공통 부분수열에 1을 더해주는 것이다.

🎯 최장 공통 부분수열의 길이를 찾는 문제 코드 구현 (JS)

👉 관련 문제 확인하기 : 백준 - LSC

const str1 = input.shift().split('');
const str2 = input.shift().split('');
const N = str1.length;
const M = str2.length;

let board = Array.from({ length: N + 1 }, () => Array(M + 1).fill(0));

for (let i = 1; i <= N; i += 1) {
  for (let j = 1; j <= M; j += 1) {
    if (str1[i - 1] === str2[j - 1]) {
      board[i][j] = board[i - 1][j - 1] + 1;
    } else board[i][j] = Math.max(board[i][j - 1], board[i - 1][j]);
  }
}

console.log(board[N][M]);

🎯 최장 공통 부분수열 찾기

위에서는 LCS 과정을 통해 LCS 배열을 만들며 LCS의 길이를 알아냈다. 이제 만든 LCS 배열을 이용해 최장 공통 부분수열의 값을 찾아볼 수 있다.** 주의해야할 점은 경우에 따라 여러가지 답이 나올 수 있기 때문에 아래 예시는 한가지만 살펴본 경우이다.**

  • LCS 배열의 가장 마지막 값에서 시작한다. 결과값을 저장할 result 배열을 준비한다.
  • LCS[i-1][j]와 LCS[i][j-1] 중 현재 값과 같은 값을 찾는다.
    • 만약 같은 값이 있다면 해당 값으로 이동한다.
    • 만약 같은 값이 없다면 result 배열에 해당 문자를 넣고 LCS[i-1][j-1]로 이동한다.
  • 2번 과정을 반복하다가 0으로 이동하게 되면 종료한다. result 배열의 역순이 LCS이다.

📑 Reference

empam27님의 그림으로 알아보는 LCS 알고리즘