문제 개요
문자열 s가 주어졌을 때, s 안에서 가장 긴 회문 부분 수열(palindromic subsequence)의 길이를 찾는 것이 목표입니다. 문자열의 최대 길이는 1000이라고 가정할 수 있습니다. 예를 들어 입력이 "bbbab"라면 출력은 4이며, 이 경우 가능한 회문 부분 수열 중 하나는 "bbbb"입니다.
여기서 말하는 부분 수열(subsequence)은 문자열에서 일부 문자를 제거하여 얻을 수 있는 수열로, 원래 문자의 순서는 유지되지만 반드시 연속적일 필요는 없습니다.
해결 전략: 최장 공통 부분 수열(LCS) 활용
이 문제의 핵심 아이디어는 간단합니다. 원본 문자열과 그 역순 문자열 사이의 최장 공통 부분 수열(LCS)이 곧 가장 긴 회문 부분 수열입니다. 이 성질을 이용하면 널리 알려진 동적 계획법(DP) 기법으로 문제를 해결할 수 있습니다.
구체적인 풀이 단계는 다음과 같습니다.
x에s를 복사한 후x를 뒤집고,n은s의 길이로 설정합니다.n이 0이면 0을 반환합니다.- 1-based 인덱싱을 위해
s와x앞에 공백 한 칸씩 추가합니다. ret을 0으로 초기화합니다.- 크기가 (n+1) × (n+1)인 DP 행렬
dp를 생성합니다. - i를 1부터 n까지, j를 1부터 n까지 반복하며 다음을 수행합니다.
dp[i][j] = max(dp[i][j-1], dp[i-1][j])- 만약
x[i] == s[j]라면dp[i][j] = max(dp[i][j], 1 + dp[i-1][j-1])
- 최종적으로
dp[n][n]을 반환합니다.
시간 복잡도와 공간 복잡도 모두 O(n²)입니다. n이 최대 1000이므로 충분히 효율적인 범위 내에서 동작합니다.
C++ 구현 예제
더 나은 이해를 돕기 위해 다음 구현 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestPalindromeSubseq(string s) {
string x = s;
reverse(x.begin(), x.end());
int n = s.size();
if(!n) return 0;
s = " " + s;
x = " " + x;
int ret = 0;
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
if(x[i] == s[j]) {
dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
}
}
}
return dp[n][n];
}
};
main(){
Solution ob;
cout << (ob.longestPalindromeSubseq("bbbab"));
}입력
"bbbab"
출력
4
마무리
이처럼 문자열을 뒤집은 버전과의 LCS를 구하는 방식만으로도 가장 긴 회문 부분 수열 문제를 우아하게 해결할 수 있습니다. DP 테이블의 각 칸은 두 문자열의 접두사 쌍에서 얻을 수 있는 최장 공통 부분 수열의 길이를 저장하며, 두 문자가 일치할 때 대각선 왼쪽 위 값에 1을 더하는 점화식으로 구성됩니다. 이 패턴은 편집 거리, 최장 공통 부분 문자열 등 다른 문자열 DP 문제에도 그대로 응용할 수 있으므로 함께 익혀두면 좋습니다.