문제 설명
두 개의 문자열 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 := 빈 문자열(공백) + s — 인덱스 계산을 편하게 하기 위해 앞에 공백을 붙임
x := 빈 문자열(공백) + x
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]는 s의 처음 i개 문자와 x의 처음 j개 문자 사이의 최장 공통 부분 수열 길이를 저장합니다. 두 위치의 문자가 서로 같다면 직전 상태(dp[i-1][j-1])에 1을 더한 값과 비교하여 더 큰 값을 취하고, 같지 않다면 한쪽 문자열에서 마지막 문자 하나를 제외한 경우(dp[i][j-1] 또는 dp[i-1][j]) 중 더 큰 값을 선택합니다.
이제 실제 구현 코드를 통해 더 자세히 이해해 보겠습니다.
예제 코드
#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"
출력
3
복잡도 분석
위 알고리즘은 두 문자열의 모든 문자 조합을 한 번씩만 확인하므로 시간 복잡도는 O(n × m)입니다. 또한 (n + 1) × (m + 1) 크기의 2차원 배열을 사용하기 때문에 공간 복잡도 역시 O(n × m)입니다. 필요하다면 롤링 배열 기법을 활용해 공간 복잡도를 O(min(n, m))까지 줄일 수 있습니다.