📍문제 링크
https://www.acmicpc.net/problem/9251
📍알고리즘 분류
- 다이나믹 프로그래밍
- 문자열
📍문제 풀이
- 다이나믹 프로그래밍(DP) 관련해서 유명한 문제
- X, Y 두 수열이 주어졌을 때, 두 수열의 최장 공통 부분 수열을 구해보자
예시)
LCS(X,Y) = B C B A
_ _ _ _
A B C B D A B
_ _ _ _
B D C A B A
- 단순 무식하게 브루트 포스 방식으로 푼다면 X의 모든 부분 수열을 구하고, 이 중에서 Y의 부분 수열이 되는 것을 구한뒤, 가장 길이가 긴 것을 구하면 된다.
- 하지만 부분 수열을 구하는데는 X가 N개의 원소를 가질 떄, O(2^N) 의 시간 복잡도를 가진다.
- 시간이 너무 오래걸려서 적합하지 않다
- DP를 사용하면 빠르게 문제를 해결할 수 있다.
- [ x(1) ], [ y(1) ] 을 비교하여 원소가 같으면 LCS의 길이를 1 늘리고,
- 원소가 다르면 [ x(1) ], [ y(1), y(2) ] 와 [ x(1), x(2) ], [ y(1) ] 의 LCS 길이 중 큰 것을 답으로 취한다.
- 반복문을 통해 이차원 배열을 만들어 최종 출력할 답을 만들어가고, 이는 메모이제이션으로 빠르게 진행된다.
📍의사 코드 (tabulation, bottom-up 방식)
- 두 수열의 길이 m, n을 통해 m + 1 * n + 1 크기의 이차원 배열 memo를 만들고 0으로 채운다
인덱스 0인 row 와 column은 0으로 사용할 기본값이므로 전체 길이를 m + 1 * n + 1 크기로 설정한다
- 중첩 반복문으로 이차원 배열을 순회하는데
두 수열에서 X[i] === Y[j] 이면, memo[i - 1][j - 1] + 1의 값을 memo[i][j] 에 기록한다
두 수열에서 X[i] !== Y[j] 이면, memo[i][j-1] 과 memo[i - 1][j] 중에서 큰 값을 memo[i][j] 에 기록한다
- 반복문이 끝나면 memo[m + 1][n + 1] 값을 출력한다
📍코드 (JavaScript)
const [X, Y] = require('fs')
.readFileSync('/dev/stdin')
.toString()
.trim()
.split('\n');
const lcs = (x, y) => {
const [m, n] = [x.length, y.length];
const memo = Array.from({ length: m + 1 }, (_) =>
Array.from({ length: n + 1 }, (_) => 0)
);
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (x[i - 1] === y[j - 1]) memo[i][j] = memo[i - 1][j - 1] + 1;
else memo[i][j] = Math.max(memo[i - 1][j], memo[i][j - 1]);
}
}
console.log(memo[m][n]);
};
lcs(X, Y);