JavaScript로 두 배열에서 최장 공통 부분 수열(LCS) 찾기

문제 소개

두 개의 리터럴 배열(arr1, arr2)을 입력으로 받아, 두 배열에 공통으로 나타나는 가장 긴 요소 시퀀스, 즉 최장 공통 부분 수열(Longest Common Subsequence)을 찾는 JavaScript 함수를 작성해 보겠습니다. 함수는 최종적으로 해당 요소들을 배열 형태로 반환해야 합니다.

예시

입력 배열이 다음과 같다고 가정해 봅시다.

const arr1 = ['a', 'b', 'c', 'd', 'e'];
const arr2 = ['k', 'j', 'b', 'c', 'd', 'w'];

이 경우 출력 결과는 다음과 같아야 합니다.

const output = ['b', 'c', 'd'];

동적 계획법(DP)을 활용한 접근 방식

이 문제는 알고리즘 분야에서 유명한 최장 공통 부분 수열(LCS) 문제로, 동적 계획법(Dynamic Programming)을 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

두 배열을 문자열로 변환한 뒤, (str2 길이 + 1) × (str1 길이 + 1) 크기의 2차원 DP 테이블을 생성합니다.
테이블의 각 셀 (i, j)에는 str2의 앞 i개 문자와 str1의 앞 j개 문자 사이의 최장 공통 부분 수열 길이가 저장됩니다.
두 위치의 문자가 서로 같으면 대각선 왼쪽 위 값에 1을 더하고, 다르면 왼쪽 값과 위쪽 값 중 더 큰 값을 선택합니다.
표를 모두 채운 후, 오른쪽 아래 끝에서부터 역추적(backtracking)하며 실제 공통 부분 수열을 구성합니다.

만약 공통 요소가 하나도 없다면 빈 문자열 배열 ['']을 반환하도록 처리했습니다.

구현 코드

const arr1 = ['a', 'b', 'c', 'd', 'e'];
const arr2 = ['k', 'j', 'b', 'c', 'd', 'w'];
const longestCommonSubsequence = (arr1 = [], arr2 = []) => {
    let str1 = arr1.join('');
    let str2 = arr2.join('');
    const arr = Array(str2.length + 1).fill(null).map(() => Array(str1.length + 1).fill(null));
    for (let j = 0; j <= str1.length; j += 1) {
        arr[0][j] = 0;
    }
    for (let i = 0; i <= str2.length; i += 1) {
        arr[i][0] = 0;
    }
    for (let i = 1; i <= str2.length; i += 1) {
        for (let j = 1; j <= str1.length; j += 1) {
            if (str1[j - 1] === str2[i - 1]) {
                arr[i][j] = arr[i - 1][j - 1] + 1;
            } else {
                arr[i][j] = Math.max(
                    arr[i - 1][j],
                    arr[i][j - 1],
                );
            }
        }
    }
    if (!arr[str2.length][str1.length]) {
        return [''];
    }
    const res = [];
    let j = str1.length;
    let i = str2.length;
    while (j > 0 || i > 0) {
        if (str1[j - 1] === str2[i - 1]) {
            res.unshift(str1[j - 1]);
            j -= 1;
            i -= 1;
        }
        else if (arr[i][j] === arr[i][j - 1]) {
            j -= 1;
        }
        else {
            i -= 1;
        }
    }
    return res;
};
console.log(longestCommonSubsequence(arr1, arr2));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

['b', 'c', 'd']

복잡도 분석

이 알고리즘은 두 문자열의 모든 문자 조합을 한 번씩 비교하므로 시간 복잡도는 O(m × n)(m, n은 각 배열의 길이)입니다. 공간 복잡도 역시 DP 테이블 저장을 위해 O(m × n)이 필요합니다. 이 방식은 단순한 완전 탐색(O(2ⁿ))보다 훨씬 효율적이며, 배열뿐 아니라 문자열 비교 등 다양한 유사 문제에 응용할 수 있습니다.