이번 튜토리얼에서는 C++을 이용해 문자열 안에 포함된 회문(palindrome) 부분 문자열의 개수를 구하는 방법을 알아봅니다.
회문이란 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 문자열을 뜻합니다. 예를 들어 "aba", "aa", "baab"처럼 좌우 대칭을 이루는 문자열이 여기에 해당합니다. 프로그램은 하나의 문자열을 입력받아, 그 안에서 두 글자 이상으로 구성된 모든 회문 부분 문자열을 찾아 총 개수를 출력하는 것이 목표입니다.
동적 계획법(DP)을 활용한 접근
가능한 모든 부분 문자열을 일일이 검사하는 완전 탐색 방식은 비효율적일 수 있습니다. 반면 동적 계획법을 활용하면 O(n²)의 시간 복잡도로 문제를 해결할 수 있습니다.
핵심은 두 개의 2차원 배열을 함께 관리하는 것입니다.
- P[i][j] : 인덱스 i부터 j까지의 부분 문자열이 회문인지 여부를 저장하는 불리언 배열
- dp[i][j] : 인덱스 i부터 j 범위 안에 존재하는 회문 부분 문자열의 총 개수를 저장하는 배열
알고리즘은 다음 순서로 진행됩니다.
- 길이가 1인 부분 문자열은 항상 회문이므로 P[i][i]를 true로 초기화합니다.
- 인접한 두 문자가 같으면(예: "aa") P[i][i+1]을 true로 설정하고 dp[i][i+1]을 1로 기록합니다.
- 간격(gap)을 2부터 n-1까지 넓혀 가며, 양 끝 문자가 같고 내부 구간(P[i+1][j-1])이 회문일 때 현재 구간도 회문으로 판정합니다.
- 판정 결과를 바탕으로 포함-배제 원리에 따른 점화식으로 dp 값을 갱신합니다.
점화식은 다음과 같습니다.
· 구간이 회문인 경우 : dp[i][j] = dp[i][j-1] + dp[i+1][j] + 1 - dp[i+1][j-1]
· 그렇지 않은 경우 : dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]
C++ 구현 예제
#include<bits/stdc++.h>
using namespace std;
// 회문 부분 문자열 개수 세기
int count_pstr(char str[], int n){
int dp[n][n];
memset(dp, 0, sizeof(dp));
bool P[n][n];
memset(P, false , sizeof(P));
for (int i= 0; i< n; i++)
P[i][i] = true;
for (int i=0; i<n-1; i++) {
if (str[i] == str[i+1]) {
P[i][i+1] = true;
dp[i][i+1] = 1 ;
}
}
for (int gap=2 ; gap<n; gap++) {
for (int i=0; i<n-gap; i++) {
int j = gap + i;
// 현재 부분 문자열이 회문인 경우
if (str[i] == str[j] && P[i+1][j-1] )
P[i][j] = true;
if (P[i][j] == true)
dp[i][j] = dp[i][j-1] + dp[i+1][j] + 1 - dp[i+1][j-1];
else
dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];
}
}
return dp[0][n-1];
}
int main(){
char str[] = "abaab";
int n = strlen(str);
cout << count_pstr(str, n) << endl;
return 0;
}
실행 결과
3
결과 분석
입력 문자열이 "abaab"일 때 프로그램이 찾아내는 회문 부분 문자열은 다음과 같습니다.
- "aba" (인덱스 0~2)
- "aa" (인덱스 2~3)
- "baab" (인덱스 1~4)
세 개의 회문이 발견되므로 최종 출력값은 3이 됩니다.
복잡도 정리
이 알고리즘은 간격을 늘려 가며 두 개의 n×n 배열을 채우므로 시간 복잡도와 공간 복잡도가 모두 O(n²)입니다. 완전 탐색(O(n³))에 비해 훨씬 효율적이며, 길이가 수천 수준인 문자열까지도 실용적인 속도로 처리할 수 있습니다.