https://www.acmicpc.net/problem/5582
5582번: 공통 부분 문자열
두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들
www.acmicpc.net
📌 작성한 코드
// 5582
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;
}
if (dp[i][j] > max) max = dp[i][j];
}
}
console.log(max);
📌 설명
공통 부분 문자열을 어떻게 구하는지에 대해 이미지와 표로 너무 멋지게 설명해놓은 블로그가 있어서 소개하려고 한다.
[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence
LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다.
velog.io
해당 블로그를 통해 어떻게 점화식을 세우고 구하는지 충분히 이해할 수 있을 것이다.
📍 주의해야 하는 부분
dp를 채워나갈때 인덱스가 0인 부분(마진)은 dp[i-1][j-1]에서 접근하기 위해서 있는 부분이라 0으로 초기화 되어있어야한다.
따라서, dp를 선언할 때 0을 할당하고, 반복문 인덱스를 돌 때 1부터 시작하되, 문자열에 접근할 때는 첫번째 문자가 0번 인덱스에 저장되어 있으니 i-1,j-1 해서 접근해야 한다.
예를 들어 문자열이 ''abc', 'abd'라면 dp[1][1]에는 각각 첫번째 문자까지 비교하였을 때 최장 공통 문자열의 길이가 저장되어야 한다.
그러면 우리는 a가 같으니까 1을 저장해야 함을 알 수 있다.
- 반복문 i, j : (1, 1) -> (i, j)로 접근
- 이때 각 문자열에 접근할 때 사용하는 인덱스 : 0 -> (i-1, j-1)로 접근
- 저장되는 위치 : (1, 1) -> (i, j)로 접근
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++) { // dp는 1에서 시작
for (let j = 1; j <= second.length; j++) {
if (first[i - 1] === second[j - 1]) { // -1한 위치로 접근 (문자열은 0에서 시작)
dp[i][j] = dp[i - 1][j - 1] + 1;
}
if (dp[i][j] > max) max = dp[i][j];
}
}
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/구현] 백준 골드 3 : 16236 - 아기 상어 (0) | 2024.03.20 |
|---|---|
| [JavaScript/DP] 백준 골드 5 : 2666 - 벽장문의 이동 (2) | 2024.03.19 |
| [JavaScript] 백준 골드 5 : 1174 - 줄어드는 수 (0) | 2024.03.11 |
| [JavaScript/DP] 백준 골드 5 : 2294 - 동전 2 (1) | 2024.03.09 |
| [JavaScript/DP] 백준 골드 5 : 9084 - 동전 (0) | 2024.03.08 |