[백준] JavaScript - LCS (9251)

개요

문제 이름: LCS (9251)
문제 링크: https://www.acmicpc.net/problem/9251
플랫폼: 백준
알고리즘 분류: DP
소요 시간: 1시간

 

문제 전문

설명

입출력

 

문제 풀이

해설

이 문제는 두 문자열이 주어졌을 때, 두 문자열의 최장 공통 부분 수열(Longest Common Subsequence, LCS)의 길이를 찾는 문제입니다. LCS 문제는 대표적인 동적 계획법(Dynamic Programming, DP) 문제 중 하나입니다.

 

동적 계획법은 큰 문제를 작은 부분 문제로 나누어 풀이하는 알고리즘 설계 기법입니다. LCS 문제에서는 두 문자열의 부분 문제에 대한 솔루션을 통해 전체 문제의 솔루션을 구할 수 있습니다.

 

이 문제를 해결하기 위해서는 2차원 DP 테이블을 사용합니다. DP 테이블의 각 셀 dp[i][j]는 str1의 i번째 문자까지와 str2의 j번째 문자까지 고려했을 때의 LCS 길이를 나타냅니다.

 

DP 테이블을 채우는 규칙은 다음과 같습니다.

1. 두 문자열의 현재 문자(i번째와 j번째)가 같은 경우...?
   1. dp[i][j] = dp[i-1][j-1] + 1
   2. 즉, 이전까지의 LCS 길이에 1을 더합니다.
2. 두 문자열의 현재 문자(i번째와 j번째)가 다른 경우...?
   1. dp[i][j] = max(dp[i-1][j], dp[i][j-1])
   2. 즉, 이전 상태의 LCS 길이 중 더 큰 값을 선택합니다.

이 규칙에 따라 DP 테이블을 채워나가면 최종적으로 dp[len1][len2]에는 두 문자열 전체를 고려한 LCS의 길이가 저장됩니다.

 

문제의 요구사항은 다음과 같습니다.

1. 입력으로 두 문자열이 주어집니다.
2. 출력으로 두 문자열의 LCS의 길이를 출력합니다.

 

문제 접근 방식은 다음과 같습니다.

1. fs 모듈을 사용하여 입력값을 받고, 줄바꿈을 기준으로 str1, str2로 분리합니다.
2. 각 문자열의 길이를 len1, len2에 저장합니다.
3. (len1+1) x (len2+1) 크기의 2차원 DP 테이블 dp를 생성하고 모든 값을 0으로 초기화합니다.
4. 이중 for문을 사용하여 DP 테이블을 채웁니다.
   1. 현재 비교하는 문자가 같은 경우, dp[i][j]에 이전까지의 LCS 길이 + 1을 저장합니다.
   2. 현재 비교하는 문자가 다른 경우, dp[i][j]에 이전 상태의 LCS 길이 중 더 큰 값을 저장합니다.
5. 최종적으로 dp[len1][len2]의 값이 LCS의 길이가 되므로 이를 출력합니다.

대충 이러한 과정으로 접근하면 될 것 같습니다.

 

시도

1차 시도  (성공)

// 입력값을 받아서 줄바꿈을 기준으로 str1, str2로 분리
const fs = require('fs');
const [str1, str2] = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// LCS(Longest Common Subsequence)를 구하는 함수
function lcs(str1, str2) {
   // 각 문자열의 길이를 저장
   const len1 = str1.length;
   const len2 = str2.length;

   // 2차원 DP 테이블 생성 및 0으로 초기화
   // (len1 + 1) x (len2 + 1) 크기의 2차원 배열
   const dp = Array.from(Array(len1 + 1), () => new Array(len2 + 1).fill(0));

   // 두 문자열을 한 글자씩 비교하면서 LCS 길이 계산
   for (let i = 1; i <= len1; i++) {
       for (let j = 1; j <= len2; j++) {
           // 현재 비교하는 문자가 같은 경우
           if (str1[i - 1] === str2[j - 1]) {
               // 이전 LCS 길이에 1을 더함
               dp[i][j] = dp[i - 1][j - 1] + 1;
           } 
           // 현재 비교하는 문자가 다른 경우
           else {
               // 이전 상태의 LCS 중 더 큰 값을 선택
               dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
           }
       }
   }

   // 최종적인 LCS의 길이를 반환
   return dp[len1][len2];
}

// 결과 출력
console.log(lcs(str1, str2));

위 코드는 동적 계획법을 사용하여 LCS 문제를 해결합니다.

1. fs 모듈을 사용하여 입력값을 받아옵니다. 입력값은 두 개의 문자열이 줄바꿈으로 구분되어 있으므로 split('\n')을 사용하여 분리합니다. 분리된 문자열은 각각 str1과 str2에 할당됩니다.
2. lcs 함수를 정의합니다. 이 함수는 두 문자열 str1과 str2를 인자로 받아 LCS의 길이를 계산하고 반환합니다.
3. 각 문자열의 길이를 len1과 len2에 저장합니다.
4. Array.from()과 fill()을 사용하여 (len1 + 1) x (len2 + 1) 크기의 2차원 DP 테이블 dp를 생성하고 모든 값을 0으로 초기화합니다.
   1. Array.from(Array(len1 + 1), () => new Array(len2 + 1).fill(0))은 길이가 len1 + 1인 배열을 생성하고, 각 요소를 길이가 len2 + 1이고 0으로 채워진 배열로 초기화합니다.
5. 이중 for문을 사용하여 DP 테이블을 채워나갑니다.
   1. 바깥쪽 for문은 str1의 문자를 순회하고, 안쪽 for문은 str2의 문자를 순회합니다.
   2. 현재 비교하는 문자가 같은 경우(str1[i - 1] === str2[j - 1]), dp[i][j]는 dp[i - 1][j - 1] + 1이 됩니다.
   3. 현재 비교하는 문자가 다른 경우, dp[i][j]는 Math.max(dp[i - 1][j], dp[i][j - 1])이 됩니다.
6. 최종적으로 dp[len1][len2]에 저장된 값을 반환합니다. 이 값이 입력된 두 문자열의 LCS 길이입니다.
7. lcs 함수를 호출하여 결과를 출력합니다.

 

사용된 주요 메서드

• Array.from(arrayLike, mapFn): arrayLike로부터 새로운 Array 객체를 생성하여 반환합니다. mapFn을 지정하면 배열의 각 요소에 대해 호출되어 매핑됩니다.
• Array.prototype.fill(value): 배열의 시작 인덱스부터 끝 인덱스까지 정적인 값 하나로 채웁니다.
• Math.max(a, b, ...): 주어진 숫자 중 가장 큰 숫자를 반환합니다.

 

시간 복잡도와 공간 복잡도

• 시간 복잡도: O(len1 * len2)
  • 두 문자열의 길이를 len1, len2라고 할 때, 이중 for 루프에서 len1 * len2 번 반복하므로 시간 복잡도는 O(len1 * len2)입니다.
• 공간 복잡도: O(len1 * len2)
  • DP 테이블로 사용되는 2차원 배열 dp의 크기가 (len1+1) x (len2+1)이므로 공간 복잡도는 O(len1 * len2)입니다.