최장 공통 부분 수열
요즘들어 간간히 시간이 날 때 마다 DP 문제를 풀고 있는데 정답 코드를 봐도 이해가 되지 않던 LCP 문제를 위키 백과를 보고 다시 공부해본다.
골아프게 했던 문제는 백준 - LCS 문제였으며 두 문자열이 있을 때 두 문자열간의 최장 공통 부분 수열의 길이를 구하는 문제였다.
ACAYKP
CAPCAK
-> ACAK , 4처음에는 문자열A 에 해당하는 문자들의 인덱스와 문자열B에 해당하는 인덱스들을 매칭해서 뭐 어쩌구 저쩌구.. 스파게티 형식으로 3번정도 풀어봤는데 몇몇 반례에서 깨지면서 여러 블로그를 탐방했다.
처음에 탐방했던 블로그 글은 [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence 였다. 이곳에서 대략적인 감은 잡을 수 있었고 위키백과 - 최장 공통 부분 수열 를 통해 이해 할 수 있게 되었다.
최장 공통 부분 수열은 수열 A,B 가 있을 때 수열 A,B 모두의 부분 수열이 되면서 길이가 가장 긴 수열을 찾는 문제를 뜻한다.
위 예시에서 들었던 ACAYKP , CAPCAK 의 경우 A,C,A,K 수열이 두 수열의 부분 수열이면서 길이가 가장 긴 수열이다.
수열의 부분 구조 표현
우선 각 수열들은 이전 수열을 이용해 표현이 가능하다. 예를 들어 ACAYKP 란 수열들의 길이를 i 라고 두고 수열을 S 라고 둔다면
S1:AS2:S1+CS3:S2+A
...S6:S5+P
형태처럼 이전 수열(접두사)과 새롭게 추가되는 값 (접미사) 형태로 표현 가능하다.
이 특징을 이용해 최장 공통 부분 수열 (이하 LCS)을 최적 부분구조를 이용하여 풀이 할 수 있다.
LCS
부분 수열을 구할 때 LCS 의 길이를 구한 후 부분 수열을 찾는 방식을 이용한다. 길이를 먼저 구하지 않은 채로 부분 수열을 구하는 편 보다 간단하기 때문이다.
길이가 n 인 수열 X와 길이가 m 인 수열 Y에 대해 LCS를 구하는 함수를 LCS(X_n,Y_y) : number 처럼 정의했다고 가정해보자
- X : BAN ANA
- Y : AT ANA
두 수열의 공통되는 접미사는 ANA 이기에 LCS(BANANA,ATANA) 였던 문제는 두 접미사를 제거한 LCS(BAN , AT) + 3 (ANA의 길이) 로 정의 할 수 있으며 결과는 4 (AANA 의 길이) 로 구할 수 있다.
이 과정에서 최적 부분 구조 문제를 자연스럽게 이용하게 되었다.
- 전체 수열 X,Y 에 대한 LCS 는 X,Y의 부분 수열들을 이용해 구할 수 있다.
- 전체 수열의 LCS 를 구하는 방식과 X,Y 의 이전 부분 수열들의 LCS 를 구하는 방식이 동일하다.
그렇다면 점화식을 세우기 위한 다양한 조건들을 분류해보자
두 수열의 접미사가 동일한 경우
수열 X_n , Y_m 에서 LCS(X_n, Y_m) 을 구할 때 두 수열의 접미사가 동일한 경우 LCS(X_n-1, Y_m-1) + 1 라고 할 수 있다.
이는 직관적으로 이해가 된다. 두 수열의 접미사가 같기에 접미사를 제거하고 구한 후 +1을 하나, 포함하여 구하나 동일한 값이기 때문이다.
두 수열의 접미사가 다른 경우
두 수열의 접미사가 다른 경우를 생각해보자
X_n, Y_m 의 접미사가 다르기 때문에 구해지는 LCS 는 X[n], Y[m] 이 접미사가 될 수 없으며 이전 부분 수열들의 LCS 를 따라야 한다는 점을 알 수 있다.
그렇다면 두 수열의 접미사가 다른 경우엔 LCS(X_n,Y_m) = Max(LCS(X_n-1, Y_m) , LCS(X_n,Y_m-1)) 이라고 정의 할 수 있다. (최장 길이를 구하기 위해 max 를 취해준다.)
X_n 의 접미사를 제거한 부분 수열과 Y_m 의 전체 수열의 LCS 혹은 X_n 과 Y_m 의 접미사를 제거한 부분 수열의 LCS 값이 정답이 된다.
이 때 빈 수열과 비지 않은 수열의 LCS 값들은 모두 0이 되어야 함을 보장해야 한다. "" , "A" 의 최장 공통 부분 수열은 없기 때문이다.
이 두 가지 특징을 고려한다면 점화식을 다음과 같이 세울 수 있다.
DP 로 풀어보자
위 점화식을 통해 알 수 있는건 필요한 이전의 해답을 저장하는 자료구조는 2차원 자료구조야한단 것이다.
두 수열의 접미사가 다른 경우엔 2개의 수열 중 하나의 접미사를 제거 한 후의 LCS 값들중의 최대값을 구해야 하기 때문이다.
const [A, B] = fs
.readFileSync(filePath)
.toString()
.trim()
.split("\n")
// 인덱싱을 편하게 하기 위한 pad 작업
.map((line) => line.padStart(line.length + 1, "0"));
const dp = Array.from({ length: A.length + 1 }, () =>
Array.from({ length: B.length + 1 }, () => 0)
);수열 A,B 의 해답을 적을 2차원 자료구조를 생성해준다.
dp[i][j] 가 의미하는 것은 A.slice(0.i) 와 B.slice(0.j) 두 수열의 LCS 값을 의미한다.
for (let i = 1; i <= A.length; i++) {
for (let j = 1; j <= B.length; j++) {
if (A[i] === B[j]) {
// dp[i-1][j-1] 은 공통된 접미사를 제거한 문자열의 LCS
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}이후엔 위에서 정의한 점화식대로 구해주면 LCS 가 모두 구해진다.
두 수열이 ACAYKP ,CAPCAK 일 때의 LCS 테이블은 다음과같다.
| '' | C | A | P | C | A | K | |
|---|---|---|---|---|---|---|---|
| '' | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| C | 0 | 1 | 1 | 1 | 2 | 2 | 2 |
| A | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
| Y | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
| K | 0 | 1 | 2 | 2 | 2 | 3 | 4 |
| P | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
가장 마지막 테이블인 dp[A.length][B.length] 를 반환하면 된다.
LCS 테이블로 LCS 수열 찾기
구해진 테이블의 마지막 행, 열의 값으로부터 테이블의 시작점까지 가는 과정을 거침으로서 이용해 해당 길이의 수열을 찾는 것도 가능하다.
이것이 가능한 이유는 다음과 같다.
dp[i][j] 의 값이 dp[i-1][j] , dp[i][j-1] 의 값 보다 큰 경우는 dp[i][j] = dp[i-1][j-1] + 1 , 즉 A[i],B[j] 의 값이 같아 해당 값이 수열의 접미사로 사용되었다는 것을 의미하기 때문이다.
반대로 dp[i][j] 의 값이 dp[i-1][j] 혹은 dp[i][j-1] 의 값들 중 같은 값이 있다면 A[i],B[j] 의 값이 서로 달라 두 수열의 일부 부분 수열의 값을 따랐다는 것을 의미하기 때문이다. (Max 를 통해)
const result = [];
let i = A.length - 1;
let j = B.length - 1;
while (i > 0 && j > 0) {
const current = dp[i][j];
const up = dp[i - 1][j];
const left = dp[i][j - 1];
if (current === up) {
i--;
continue;
} else if (current === left) {
j--;
continue;
} else {
result.push(A[i]);
i--;
j--;
}
}
console.log(result.reverse().join("")); // ACAK전체 해답 코드
const fs = require("fs");
const path = require("path");
const filePath =
process.platform === "linux"
? "/dev/stdin"
: path.join(__dirname, "input.txt");
const [A, B] = fs
.readFileSync(filePath)
.toString()
.trim()
.split("\n")
// 인덱싱을 편하게 하기 위한 pad 작업
.map((line) => line.padStart(line.length + 1, "0"));
const dp = Array.from({ length: A.length + 1 }, () =>
Array.from({ length: B.length + 1 }, () => 0)
);
for (let i = 1; i <= A.length; i++) {
for (let j = 1; j <= B.length; j++) {
if (A[i] === B[j]) {
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[A.length][B.length]);
// dp 테이블로 부분 수열 역추적 하기
// const result = [];
// let i = A.length - 1;
// let j = B.length - 1;
// while (i > 0 && j > 0) {
// const current = dp[i][j];
// const up = dp[i - 1][j];
// const left = dp[i][j - 1];
// if (current === up) {
// i--;
// continue;
// } else if (current === left) {
// j--;
// continue;
// } else {
// result.push(A[i]);
// i--;
// j--;
// }
// }
// console.log(result.reverse().join(""));