알고리즘
[백준] LCS(9251)
27 views
문제 설명
백준 LCS 문제 풀이(https://www.acmicpc.net/problem/9251)
문제 개요
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
코드 구현
text
const input =
process.platform === "linux"
? require("fs").readFileSync("/dev/stdin").toString().trim().split("\n")
: require("fs").readFileSync("./input.txt").toString().trim().split("\r\n");
const [str1, str2] = input;
const answer = Array.from({ length: str1.length + 1 }, () => Array.from({ length: str2.length + 1 }, () => 0))
for (let i = 1; i <= str1.length; i++) {
for (let j = 1; j <= str2.length; j++) {
if (str1[i - 1] === str2[j - 1]) answer[i][j] += answer[i - 1][j - 1] + 1
else {
answer[i][j] = Math.max(answer[i][j - 1], answer[i - 1][j])
}
}
}
console.log(answer[str1.length][str2.length])
코드 해설
이 문제는 DP(동적 프로그래밍)을 활용해 해결할 수 있다.
배열을 만들고 dp[i][j] 의 경우 다음과 같은 점화식이 성립한다.
dp[i][j] =
if A[i-1] == B[j-1] → dp[i-1][j-1] + 1
else → max(dp[i-1][j], dp[i][j-1])
요약 및 참고사항
- 점화식을 먼저 발견하자