최장 공통 부분 수열 (LCS problme)

Long Common Subsequence

한 개 이상의 문자열이 주어질 때,

중간에 다른 문자가 들어가더라도

공통되면서 가장 긴 부분 문자열을 찾는 문제

 

다이나믹 프로그래밍(DP, Dynamic Programming)을 사용해야 한다.

 

EX ) A와 B 두 개의 문자열이 주어진다.

         => A = 'ACAYKP' / B = 'CAPCAK'

 

1 ) ( 문자열의 길이 + 1 ) 만큼 2차원 배열을 생성한다.

      단, 인덱스가 0인 부분은 0으로 채워넣는다.

	-	A	C	A	Y	K	P
-	0	0	0	0	0	0	0
C	0
A	0
P	0
C	0
A	0
K	0

 

2) 한 글자씩 비교한다.

	-	A	C	A	Y	K	P
-	0	0	0	0	0	0	0
C	0	0
A	0
P	0
C	0
A	0
K	0

   - 글자가 같지 않다면, 위의 값과 왼쪽 값 중 큰 값을 삽입한다.

      = 글자가 같지 않다는 것은 전에 찾은 공통 수열 부분을 그대로 가져간다는 것을 의미한다.

         전에 찾은 공통 수열 부분은 위의 값과 왼쪽 값뿐이며, 최장 공통 부분이기 때문에 큰 값을 가져오면 된다.

	-	A	C	A	Y	K	P
-	0	0	0	0	0	0	0
C	0	0	1
A	0
P	0
C	0
A	0
K	0

   - 글자가 같다면, 왼쪽 위 대각선에 1을 더한 값을 삽입한다.

      = 왼쪽 위 대각선(A)과 현재 위치의 문자열(AC/C)을 비교할 때의 달라진 점은

         두 문자열 모두 현재 위치의 문자(C)가 추가되었다는 점이다.

         때문에 왼쪽 위 대각선에 1을 더한 값을 가져오면 된다.

 

❗점화식 ❗

( A[i] === B[j] ) graph[i][j] = graph[i - 1][j - 1] + 1

( A[i] !== B[j] ) graph[i][j] = Math.max( graph[i][j - 1], graph[i - 1][j] )

 

3) 최종 배열은 다음과 같다.

	-	A	C	A	Y	K	P
-	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

 

자바스크립트 코드

const fs = require('fs');
const filePath = process.platform==='linux' ? '/dev/stdin':'input.txt';
const [a, b] = fs.readFileSync(filePath).toString().split('\n').map((v) => v.trim());

const [n, m] = [a.length, b.length];
let graph = Array.from(Array(n + 1), () => Array(m + 1).fill(0));

for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= m; j++) {
    if (a[i - 1] === b[j - 1]) {
      graph[i][j] = graph[i - 1][j - 1] + 1;
    } else {
      graph[i][j] = Math.max(graph[i][j - 1], graph[i - 1][j]);
    }
  }
}

console.log(graph[n][m]);