[알고리즘] LCS(Longest Common Subsequence, 최장 공통 부분 수열) (자바스크립트/javascript/js/동적계획법/동적 프로그래밍 /다이나믹 프로그래밍) (백준 9251)

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

 

이번 시간에는 LCS(Longest Common Subsequence, 최장 공통 부분 수열)에 대해 알아보겠습니다.

지난 시간에 LIS(Longest Increasing Subsequence, 최장 증가 부분 수열)에 대한 문제를 백준에서 풀어보았는데요.

(이전 포스팅 참조)

이번 에는 LCS에 대해 알아보겠습니다.

 

LCS, 최장 공통 부분 수열이란 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제입니다.

예를 들어, CAPCAK와 ACAYKP의 LCS는 ACAK가 됩니다.  (이 때 꼭 문자열이 연속해야 할 필요는 없습니다.)

 

이 문제를 풀어보는 방법은 다음과 같습니다.

우선 ACAYKP와 CAPCAK를 문자열의 인덱스를 이용하여 이중 for문으로 서로 각각의 문자를 하나씩 비교해야합니다.

 

* 현재 비교하고 있는 두 문자가 같다면 : DP[i][j] = DP[i-1][j-1] + 1

* 현재 비교하고 있는 두 문자가 다르다면 : DP[i][j] = max(DP[i-1][j], DP[i][j-1])

 

왜 이런 점화식이 나왔는지 차근차근 알아봅시다.

우선, 비교대상인 문자열 2개가 있을 텐데 각각의 문자열 길이보다 + 1 큰 배열로 2차원 배열을 만들어줍니다.

그리고 0행과 0열에는 마진으로 0을 넣어줍니다. 

예를 들어 (0,A) 즉 0행A열의 경우에는 빈 문자열 vs "A"를 비교하겠다는 의미가 되므로 마진으로 0을 넣어주는 겁니다.

그럼 이제 반복문을 돌며 각 칸을 채워보겠습니다.

 

 

우선 (C,A) 즉 C행A열은 전체 문자열인 CAPCAK와 ACAYKP 중에서 "C" vs "A"를 비교하는 것이 됩니다.

"C"와 "A"는 다르기 때문에 DP[i-1][j]와 DP[i][j-1] 중 큰 값이 들어와야 합니다. 여기서 DP[i-1][j]라는 것은 C를 비교하기 전인 "" vs "A"를 말하고, DP[i][j-1]는 A를 비교하기 전인 "C" vs ""를 말합니다. 즉, "C" vs "A"라는 것은 현재 비교중인 "C"와 "A"가 다르니까 그 둘을 비교하기 전인 녀석들과 값이 같기 때문에 그 중에서도 최댓값을 넣어주는 겁니다. 

그런데 둘다 0이니까 0을 넣게됩니다.

 

다음으로는 (C,C) 즉 (C행 C열) 이니까 "C" vs "AC"를 비교하고 있습니다. 현재 비교중인 문자는 "C"와 "C"로 둘다 같습니다. 같으면 DP[i][j] = DP[i-1][j-1] + 1 라고 했습니다. 이 의미는 현재 C를 비교하기 전인 "" vs "A"에 LCS (최장공통부분수열) 길이가 1 추가된 것과 같기 때문입니다. 그러므로 왼쪽 대각선에 있는 값에서 1이 추가가 되는 겁니다.

 

C행 A열을 보겠습니다. "C" vs "ACA"를 비교하는 것이고 현재 비교중인 문자 "C"와 "A"가 서로 다르기 때문에 첫번째 문자열에 C가 포함되기 전인 "" vs "ACA"와 두번째 문자열에 A가 포함되기 전인 "C" vs "AC"중 큰 값이 오는 것과 같으므로 1이 옵니다. 

 

이렇게 해서 채우다보면 위와 같은 표가 만들어지고 , 결국에 우리가 구하고자 하는 것은 CAPCAK vs ACAYKP이기 때문에 맨 마지막 K행 P열을 확인하면 4라는 숫자가 들어있음을 알 수 있습니다. 

 

이에 대한 문제는 백준 9251번 LCS 라는 문제가 있습니다. (https://www.acmicpc.net/problem/9251)

 

 

구현한 코드 (자바스크립트)

let fs = require("fs");
let string = fs.readFileSync("/dev/stdin").toString().split("\n");
const string1 = string[0];
const string2 = string[1];
const s1 = string1.length;
const s2 = string2.length;

const dp = Array.from(new Array(s1 + 1), () => new Array(s2 + 1));
for (let i = 0; i <= s1; i++) {
  dp[i][0] = 0;
}
for (let j = 0; j <= s2; j++) {
  dp[0][j] = 0;
}

for (let i = 1; i <= s1; i++) {
  for (let j = 1; j <= s2; j++) {
    if (string1.charAt(i - 1) === string2.charAt(j - 1)) {
      dp[i][j] = dp[i - 1][j - 1] + 1;
    } else {
      dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
}
console.log(dp[s1][s2]);