C++로 두 문자열의 최장 공통 부분 수열(LCS) 길이 구하는 프로그램

두 개의 문자열 text1과 text2가 주어졌을 때, 두 문자열의 최장 공통 부분 수열(Longest Common Subsequence, LCS)의 길이를 구해야 합니다.

여기서 부분 수열(subsequence)이란 원본 문자열에서 일부 문자를 삭제하되, 나머지 문자들의 상대적인 순서는 그대로 유지한 채 만들어진 새로운 문자열을 의미합니다. 예를 들어 "abe"는 "abcde"의 부분 수열이지만, 순서가 뒤바뀌었기 때문에 "adc"는 부분 수열이 아닙니다. 공통 부분 수열은 두 문자열 모두에 존재하는 부분 수열을 말하며, 만약 공통 부분 수열이 존재하지 않는다면 0을 반환하면 됩니다.

예를 들어 입력이 "abcde"와 "ace"라면, 공통 부분 수열은 "ace"이므로 결과는 3이 됩니다.

문제 해결 접근 방법

이 문제는 대표적인 동적 계획법(Dynamic Programming) 문제로, 다음 단계를 따라 해결할 수 있습니다.

n := 문자열 s의 길이, m := 문자열 x의 길이
n 또는 m 중 하나라도 0이면 0을 반환
인덱스 계산을 편하게 하기 위해 s와 x 앞에 빈 문자 하나를 붙임 (1-based 인덱싱)
ret := 0으로 초기화
(n + 1) × (m + 1) 크기의 dp 행렬 정의
i를 1부터 n까지 반복
- j를 1부터 m까지 반복
  - dp[i][j] := max(dp[i][j-1], dp[i-1][j])
  - 만약 s[i] == x[j]라면
    - dp[i][j] := max(dp[i][j], 1 + dp[i-1][j-1])
최종적으로 dp[n][m] 반환

핵심 아이디어는 다음과 같습니다. 두 문자가 서로 다르면, 한쪽 문자를 제외했을 때의 최댓값(dp[i][j-1] 또는 dp[i-1][j])을 가져오고, 두 문자가 같다면 이전 상태(dp[i-1][j-1])에 1을 더한 값과 비교하여 더 큰 값을 저장합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int longestCommonSubsequence(string s, string x) {
      int n = s.size();
      int m = x.size();
      if(!n || !m) return 0;
      s = " " + s;
      x = " " + x;
      int ret = 0;
      vector < vector <int> > dp(n + 1, vector <int>(m + 1));
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= m ; j++){
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            if(s[i] == x[j]) {
               dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
            }
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   cout << (ob.longestCommonSubsequence("abcde", "ace"));
}

입력

"abcde"
"ace"

출력

시간 복잡도 분석

이 알고리즘은 두 중첩 반복문을 사용하므로 시간 복잡도는 O(n × m)입니다. 공간 복잡도 역시 dp 테이블 크기만큼인 O(n × m)이며, 필요에 따라 이전 행만 유지하는 방식으로 O(min(n, m))까지 최적화할 수도 있습니다.