자바스크립트 코딩테스트 강좌, 최장 공통 부분 수열 찾기

문제 설명

두 개의 문자열이 주어졌을 때, 이 두 문자열의 최장 공통 부분 수열(Longest Common Subsequence, LCS)을 찾는 문제입니다.
최장 공통 부분 수열은 두 문자열의 순서를 유지하면서 겹치는 최대 길이의 부분 문자열을 의미합니다.
예를 들어, 문자열 A가 “ABCBDAB”이고 문자열 B가 “BDCAB”일 경우, 최장 공통 부분 수열은 “BDAB” 또는 “BCAB” 등입니다.

입력 형식

– 첫 번째 줄에 문자열 A의 길이 N과 문자열 B의 길이 M이 주어집니다. (1 ≤ N, M ≤ 1000)
– 두 번째 줄에 문자열 A가 주어집니다.
– 세 번째 줄에 문자열 B가 주어집니다.

출력 형식

– 두 문자열의 최장 공통 부분 수열의 길이를 출력합니다.

예제

문제 해결을 위한 접근법

이 문제는 동적 프로그래밍(Dynamic Programming)의 전형적인 예시입니다.
LCS를 구하기 위해서는 두개의 문자열을 비교하여 일치하는 문자를 찾고,
이 때의 부분 문제를 해결하여 최종 길이를 도출할 수 있습니다.

단계별 접근

동적 계획법 테이블 초기화:

2차원 배열 DP를 생성합니다. DP[i][j]는 문자열 A의 처음 i개 문자와 문자열 B의 처음 j개 문자까지의
최장 공통 부분 수열의 길이를 저장합니다. 배열의 크기는 (N+1) x (M+1)입니다.
테이블 채우기:

A의 i번째 문자와 B의 j번째 문자가 같으면 DP[i][j] = DP[i-1][j-1] + 1
그렇지 않다면 DP[i][j] = max(DP[i-1][j], DP[i][j-1])로 설정합니다.
결과 출력:

DP[N][M]에 도달하면 최장 공통 부분 수열의 길이를 반환할 수 있습니다.

자바스크립트 코드


function longestCommonSubsequence(A, B) {
    const N = A.length;
    const M = B.length;
    
    // DP 테이블 초기화
    const DP = Array.from(Array(N + 1), () => Array(M + 1).fill(0));
    
    // DP 테이블 채우기
    for (let i = 1; i <= N; i++) {
        for (let j = 1; j <= M; j++) {
            if (A[i - 1] === B[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]);
            }
        }
    }
    
    return DP[N][M];
}

// 입력 예제 실행
const A = 'ABCBDAB';
const B = 'BDCAB';
console.log(longestCommonSubsequence(A, B)); // Output: 4

복습 및 연습 문제

이 문제를 완전히 이해했다면, 추가적인 연습문제를 통해 능력을 키워보세요. 다음과 같은 문제에 도전해 보십시오.

주어진 두 문자열 대신 세 개의 문자열에서 최장 공통 부분 수열을 찾는 문제.
대소문자를 구분하지 않고 최장 공통 부분 수열을 찾는 문제.
최장 공통 부분 수열을 구하는 모든 가능한 조합을 출력하는 문제.

맺음말

최장 공통 부분 수열 문제는 컴퓨터 과학의 중요한 개념 중 하나로, 다양한 알고리즘 문제에 응용될 수 있습니다.
동적 계획법을 사용한 이 방식을 통해 문제를 해결하는 것은 더욱 복잡한 문제를 해결하는 데 도움이 될 것입니다. 다양한 문제를 풀며 실력을 다져 보세요!