[JavaScript/DP] 백준 골드 5 : 9251 - LCS

https://www.acmicpc.net/problem/9251

9251번: LCS

---

📌 작성한 코드 

// 9251
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const first = input[0];
const second = input[1];

const dp = Array.from({ length: first.length + 1 }, () => new Array(second.length + 1).fill(0));
let max = 0;

for (let i = 1; i <= first.length; i++) {
    for (let j = 1; j <= second.length; j++) {
        if (first[i - 1] === second[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
        } else {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
        if (max < dp[i][j]) max = dp[i][j];
    }
}

console.log(max);

📌 설명 

최장 공통 부분 수열(LCS)을 구하는 문제이다.

dp를 사용하여 현재까지 확인한 최장 공통 부분 수열의 길이에, 현재 문자를 추가할 수 있는지 여부에 따라 값을 업데이트 하면 된다. 

 

💡 참고

최장 공통 부분 수열을 설명하는 더없이 완벽한 글이 있기에 공유한다. 

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence#longest-common-subsequence-substring

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 

✅ 성공