최장 공통 부분순열은 두 순열의 각 부분순열 집합에서 공통으로 속하면서 길이가 가장 긴 부분순열을 찾는 알고리즘
최장 공통 부분문자열과의 차이점은 부분문자열과 다르게 부분순열 문제에서는 순서만 일치한다면 값의 연속성을 고려하지 않아도 된다.
최장 공통 부분순열을 해결하기 위해서는 각 순열의 부분순열 집합에서 공통된 최장 부분순열 행렬을 계산해야한다.
const createMatrix = (setA, setB) => {
const matrix = Array(setB.length + 1)
.fill(0)
.map(() => Array(setA.length + 1).fill(0));
const arrayA = Array.from(setA);
const arrayB = Array.from(setB);
for (let i = 1; i < setB.length + 1; i++) {
for (let j = 1; j < setA.length + 1; j++) {
if (arrayA[j - 1] === arrayB[i - 1]) {
matrix[i][j] = matrix[i - 1][j - 1] + 1;
} else {
matrix[i][j] = Math.max(matrix[i][j - 1], matrix[i - 1][j]);
}
}
}
return matrix;
}
행렬의 값을 역추적하여 최장 공통 부분순열을 구할 수 있다. 역추적 과정은 DFS를 활용했다.
const LCS = (setA, setB) => {
const arrayA = Array.from(setA);
const arrayB = Array.from(setB);
const matrix = createMatrix(setA, setB);
const subMaxLength = matrix[setB.length][setA.length];
const stack = [[setA.length, setB.length, ""]];
let answer = null;
while (stack.length > 0) {
const [x, y, string] = stack.pop();
if (string.length === subMaxLength) {
answer = [string, subMaxLength];
break;
}
if (x > 0 && y > 0) {
if (arrayA[x - 1] === arrayB[y - 1]) {
stack.push([x - 1, y - 1, arrayA[x - 1] + string]);
} else {
if (matrix[y][x] === matrix[y - 1][x]) {
stack.push([x, y - 1, string]);
}
if (matrix[y][x] === matrix[y][x - 1]) {
stack.push([x - 1, y, string]);
}
}
}
}
return answer;
};