Computer >> 컴퓨터 >  >> 프로그래밍 >> 프로그래밍

최장 공통 부분 수열(LCS) – 다이나믹 프로그래밍으로 손쉽게 해결하기

최장 공통 부분 수열(LCS)이란?

최장 공통 부분 수열(Longest Common Subsequence, LCS)은 주어진 두 문자열 또는 배열에 모두 포함되어 있는 부분 수열 중 길이가 가장 긴 것을 찾는 고전적인 알고리즘 문제입니다. 여기서 부분 수열(subsequence)은 원래 문자열에서 문자의 상대적인 순서를 유지한 채 일부 문자를 제거해 만든 수열을 의미하며, 반드시 연속적일 필요는 없습니다.

예를 들어 "AGGTAB"과 "GXTXAYB"의 최장 공통 부분 수열은 "GTAB"이며, 그 길이는 4입니다.

이 문제를 단순 재귀로 풀면 동일한 하위 문제를 여러 번 반복해서 계산해야 하므로 매우 비효율적입니다. 다이나믹 프로그래밍(Dynamic Programming)의 중복되는 하위 구조(Overlapping Substructure) 특성을 활용하면, 한 번 계산한 하위 문제의 결과를 테이블에 저장해 두었다가 이후 계산에 재활용할 수 있어 연산량을 크게 줄일 수 있습니다.

입력 및 출력 예시

입력:
문자나 기호로 이루어진 서로 다른 두 개의 문자열
string 1: AGGTAB
string 2: GXTXAYB

출력:
최장 공통 부분 수열의 길이 → 4
("G", "T", "A", "B" 네 글자가 두 문자열 모두에 같은 순서로 등장)

점화식 (Recurrence Relation)

dp[i][j]를 str1의 앞 i개 문자와 str2의 앞 j개 문자 사이의 LCS 길이라고 정의하면, 다음 점화식으로 표현할 수 있습니다.

  • i = 0 또는 j = 0인 경우: dp[i][j] = 0 (비교할 문자가 없으므로)
  • str1[i-1] == str2[j-1]인 경우: dp[i][j] = dp[i-1][j-1] + 1 (두 문자가 일치하면 LCS 길이가 1 증가)
  • 그 외의 경우: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (두 경우 중 더 큰 값 선택)

알고리즘

입력 − 최장 공통 부분 수열의 길이를 구하고자 하는 두 개의 문자열

출력 − 두 문자열의 LCS 길이

longestComSubSeq(str1, str2)

Begin
    m := str1의 길이
    n := str2의 길이
    (m+1) × (n+1) 크기의 longSubSeq 행렬 정의

    for i := 0 to m, do
        for j := 0 to n, do
            if i = 0 or j = 0, then
                longSubSeq[i, j] := 0
            else if str1[i-1] = str2[j-1], then
                longSubSeq[i, j] := longSubSeq[i-1, j-1] + 1
            else
                longSubSeq[i, j] := longSubSeq[i-1, j]와 longSubSeq[i, j-1] 중 최댓값
            done
        done

    return longSubSeq[m, n]
End

C++ 구현 예제

#include<iostream>
using namespace std;

int max(int a, int b) {
    return (a > b)? a : b;
}

int longestComSs(string str1, string str2) {
    int m = str1.size();
    int n = str2.size();

    int longSubSeq[m+1][n+1];

    // longSubSeq[i][j]에는 str1의 처음 i개 문자와 str2의 처음 j개 문자 사이의 LCS 길이가 저장됩니다.
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                longSubSeq[i][j] = 0;
            else if (str1[i-1] == str2[j-1])
                longSubSeq[i][j] = longSubSeq[i-1][j-1] + 1;
            else
                longSubSeq[i][j] = max(longSubSeq[i-1][j], longSubSeq[i][j-1]);
        }
    }
    return longSubSeq[m][n];
}

int main() {
    string str1 = "AGGTAB";
    string str2 = "GXTXAYB";

    cout << "Length of Longest Common Subsequence is: " << longestComSs(str1, str2);
}

실행 결과

Length of Longest Common Subsequence is: 4

시간 복잡도

두 문자열의 길이를 각각 m, n이라 할 때, 이 알고리즘은 모든 (i, j) 조합에 대해 테이블을 한 번씩 채우므로 시간 복잡도는 O(m × n), 공간 복잡도 역시 O(m × n)입니다. 지수 시간이 소요되는 단순 재귀 방식에 비해 훨씬 효율적이며, 이러한 차이는 입력 문자열이 길어질수록 더욱 두드러집니다.