C++로 문자열 내 모든 회문 부분 수열 개수 구하기

개요

이 튜토리얼에서는 C++를 사용하여 주어진 문자열에 포함된 모든 회문(팰린드롬) 부분 수열의 개수를 구하는 프로그램을 작성하는 방법을 알아봅니다.

여기서 회문 부분 수열이란, 원본 문자열에서 문자들을 임의로 선택해 만든 수열 중 앞에서 읽으나 뒤에서 읽으나 동일한 수열을 의미합니다. 예를 들어 "abcb"라는 문자열이 주어지면, 만들 수 있는 회문 부분 수열은 a, b, c, b, bb, bcb로 총 6개입니다.

알고리즘 원리

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 2차원 배열 cps를 선언하고, cps[i][j]에는 인덱스 i부터 j까지의 부분 문자열에서 만들 수 있는 회문 부분 수열의 개수를 저장합니다.
• 길이가 1인 부분 문자열은 항상 회문이므로 cps[i][i] = 1로 초기화합니다.
• 구간의 양 끝 문자가 같은 경우(str[i] == str[k]): 양쪽 끝 문자를 함께 묶은 새로운 회문이 하나 더 생기므로 cps[i][k-1] + cps[i+1][k] + 1을 계산합니다.
• 양 끝 문자가 다른 경우: 두 하위 구간의 결과를 더한 뒤 중복으로 계산된 부분을 제거하기 위해 cps[i+1][k-1]을 빼줍니다.

예제 코드

#include<iostream>
#include<cstring>
using namespace std;

// 전체 회문 부분 수열의 개수를 반환하는 함수
int count_palin(string str){
    int N = str.length();
    // 2차원 DP 배열 생성
    int cps[N+1][N+1];
    memset(cps, 0, sizeof(cps));
    // 길이가 1인 부분 문자열은 모두 회문
    for (int i=0; i<N; i++)
        cps[i][i] = 1;
    // 부분 문자열의 길이를 늘려가며 계산
    for (int L=2; L<=N; L++){
        for (int i=0; i<N; i++){
            int k = L+i-1;
            if (str[i] == str[k])
                cps[i][k] = cps[i][k-1] + cps[i+1][k] + 1;
            else
                cps[i][k] = cps[i][k-1] + cps[i+1][k] - cps[i+1][k-1];
        }
    }
    return cps[0][N-1];
}

int main(){
    string str = "abcb";
    cout << "Total palindromic subsequence are : " << count_palin(str) << endl;
    return 0;
}

실행 결과

Total palindromic subsequence are : 6

정리

이 알고리즘은 시간 복잡도 O(N²)으로 문자열 내 모든 회문 부분 수열의 개수를 구할 수 있으며, 완전 탐색 방식보다 훨씬 효율적입니다. 동적 계획법 테이블을 채워 나가는 점화식 구조만 이해하면, 다양한 문자열 조합 문제에도 같은 패턴을 응용할 수 있습니다.