가장 긴 회문 부분 수열이란?
가장 긴 회문 부분 수열(Longest Palindromic Subsequence)은 주어진 문자열에서 순서를 유지한 채 일부 문자를 선택해 만들 수 있는 부분 수열(subsequence) 중, 앞에서 읽으나 뒤에서 읽으나 같은 회문(palindrome)이 되는 것 중 가장 긴 것을 찾는 문제입니다.
여기서 중요한 점은 부분 수열은 반드시 연속적일 필요가 없다는 것입니다. 예를 들어 "ABCDEEAB"라는 문자열이 주어졌다면, 문자를 건너뛰어 선택해도 되므로 'A', 'E', 'E', 'A'를 골라 "AEEA"라는 길이 4의 회문을 만들 수 있습니다.
재귀 관계식
이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
L(0, n-1)을 전체 문자열의 가장 긴 회문 부분 수열의 길이라고 할 때:
- 첫 번째 문자와 마지막 문자가 같다면 → L(0, n-1) = L(1, n-2) + 2
- 같지 않다면 → 양쪽 끝 중 하나를 제외한 경우 중 더 큰 값을 선택합니다.
입력 및 출력 예시
입력:
알파벳 또는 기호로 이루어진 문자열. 예: "ABCDEEAB"
출력:
가장 긴 회문 부분 수열의 길이. 이 예제에서는 4입니다.
ABCDEEAB → 회문은 "AEEA"
알고리즘 설계
palSubSeqLen(str)
입력 − 주어진 문자열
출력 − 가장 긴 회문 부분 수열의 길이
Begin
n = 문자열의 길이
n x n 크기의 테이블 lenTable을 생성하고 모든 값을 1로 초기화
for col := 2 to n, do
for i := 0 to n – col, do
j := i + col – 1
if str[i] = str[j] 그리고 col = 2, then
lenTable[i, j] := 2
else if str[i] = str[j], then
lenTable[i, j] := lenTable[i+1, j-1] + 2
else
lenTable[i, j] := lenTable[i, j-1]과 lenTable[i+1, j] 중 최댓값
done
done
return lenTable[0, n-1]
End
동작 원리 상세 설명
- 테이블 초기화: 길이가 1인 문자열은 항상 회문이므로 대각선(lenTable[i][i])을 1로 설정합니다.
- 부분 문제 확장: 길이가 2인 구간부터 시작해 점차 전체 문자열까지 범위를 넓혀가며 해를 구합니다.
- 양 끝 문자 비교: 두 문자가 같으면 안쪽 구간의 답에 2를 더하고, 다르면 한쪽 끝을 제외한 두 경우 중 큰 값을 취합니다.
시간 복잡도는 O(n²), 공간 복잡도 역시 O(n²)입니다.
C++ 구현 예제
#include<iostream>
using namespace std;
int max(int x, int y) {
return (x > y)? x : y;
}
int palSubseqLen(string str) {
int n = str.size();
int lenTable[n][n]; // 부분 문제의 결과를 저장할 테이블 생성
for (int i = 0; i < n; i++)
lenTable[i][i] = 1; // 길이가 1인 문자열은 항상 회문
for (int col=2; col<=n; col++) {
for (int i=0; i<n-col+1; i++) {
int j = i+col-1;
if (str[i] == str[j] && col == 2)
lenTable[i][j] = 2;
else if (str[i] == str[j])
lenTable[i][j] = lenTable[i+1][j-1] + 2;
else
lenTable[i][j] = max(lenTable[i][j-1], lenTable[i+1][j]);
}
}
return lenTable[0][n-1];
}
int main() {
string sequence = "ABCDEEAB";
int n = sequence.size();
cout << "가장 긴 회문 부분 수열의 길이: " << palSubseqLen(sequence);
}
실행 결과
가장 긴 회문 부분 수열의 길이: 4
마무리
가장 긴 회문 부분 수열 문제는 동적 계획법의 대표적인 활용 사례입니다. 문자열의 양 끝을 비교하며 작은 부분 문제부터 차근차근 해를 쌓아 올리는 방식은, LCS(최장 공통 부분 수열) 등 다른 문자열 DP 문제를 학습할 때도 큰 도움이 됩니다. 위 코드를 직접 실행해 보며 테이블이 채워지는 과정을 추적해 보면 개념을 더욱 확실히 이해할 수 있습니다.