가장 긴 회문(팰린드롬) 부분 문자열 찾기 – 동적 프로그래밍 완전 정리

주어진 문자열 안에서 회문(palindrome)이 되는 부분 문자열 중 가장 긴 것을 찾는 것이 이번 문제의 목표입니다.

가장 긴 회문 부분 문자열을 구하는 과정에서는 수많은 하위 문제(subproblem)를 풀게 되는데, 일부 하위 문제는 서로 겹쳐 있어(overlapping) 같은 계산을 여러 번 반복해야 할 수 있습니다. 바로 이런 경우 동적 프로그래밍(Dynamic Programming)이 큰 힘을 발휘합니다. 테이블을 활용해 이전에 계산한 하위 문제의 결과를 저장해 두면, 이후에는 저장된 값을 그대로 재사용하여 다음 결과를 빠르게 만들어 낼 수 있습니다.

입력 및 출력

입력:
문자열 하나. 예: "thisispalapsiti"

출력:
가장 긴 회문 부분 문자열과 그 길이.
가장 긴 회문 부분 문자열: ispalapsi
길이: 9

알고리즘

findLongPalSubstr(str)

입력 − 원본 문자열.

출력 − 가장 긴 회문 부분 문자열과 그 길이.

시작
   n := 주어진 문자열의 길이
   true/false 값을 저장할 n x n 크기의 테이블 palTab 생성
   palTab을 false 값으로 초기화
   maxLen := 1

   i := 0부터 n-1까지 반복
      palTab[i, i] = true   // 길이 1인 부분 문자열은 항상 회문
   종료

   start := 0
   i := 0부터 n-2까지 반복
      if str[i] = str[i+1], then
         palTab[i, i+1] := true
         start := i
         maxLen := 2
   종료

   k := 3부터 n까지 반복
      i := 0부터 n-k까지 반복
         j := i + k - 1
         if palTab[i+1, j-1]이 true이고 str[i] = str[j]이면
            palTab[i, j] := true
            if k > maxLen이면
               start := i
               maxLen := k
      종료
   종료
   str에서 start 위치부터 maxLen 길이만큼의 부분 문자열을 출력하고 maxLen 반환
끝

동작 원리 요약

이 알고리즘의 핵심은 dp[i][j]가 "부분 문자열 str[i..j]가 회문인가?"라는 질문에 대한 답을 저장한다는 점입니다. 각 단계는 다음과 같이 판단합니다.

• 길이 1: 한 글자짜리 문자열은 항상 회문입니다.
• 길이 2: 두 문자가 서로 같으면 회문입니다.
• 길이 3 이상: 양 끝 문자가 같고, 그 안쪽 부분 문자열(dp[i+1][j-1])이 이미 회문이라면 전체도 회문입니다.

이렇게 작은 문제부터 차례대로 해결하면서 테이블에 결과를 누적하므로, 시간 복잡도와 공간 복잡도는 각각 O(n²), O(n²)입니다.

C++ 예제 코드

#include<iostream>
using namespace std;

int findLongPalSubstr(string str) {
   int n = str.size();     // 입력 문자열의 길이
 
   bool palCheckTab[n][n];    // i~j 구간의 부분 문자열이 회문이면 true
 
   for(int i = 0; i<n; i++)
      for(int j = 0; j<n; j++)
         palCheckTab[i][j] = false;    // 모든 값을 false로 초기화

   int maxLength = 1;
 
   for (int i = 0; i < n; ++i)
      palCheckTab[i][i] = true;    // 길이 1인 부분 문자열은 모두 회문

   int start = 0;
   for (int i = 0; i < n-1; ++i) {
      if (str[i] == str[i+1]) {    // 길이 2: 두 문자가 같으면 회문
         palCheckTab[i][i+1] = true;
         start = i;
         maxLength = 2;
      }
   }
 
   for (int k = 3; k <= n; ++k) {    // 길이 3부터 n까지 검사
      for (int i = 0; i < n-k+1 ; ++i) {
         int j = i + k - 1;
         if (palCheckTab[i+1][j-1] && str[i] == str[j]) {   // 내부가 회문이고 양 끝이 같으면 회문
            palCheckTab[i][j] = true;
            if (k > maxLength) {
               start = i;
               maxLength = k;
            }
         }
      }
   }
   cout << "Longest palindrome substring is: " << str.substr(start, maxLength) << endl;
   return maxLength; // 길이 반환
}
 
int main() {
   char str[] = "thisispalapsiti";
   cout << "Length is: "<< findLongPalSubstr(str);
}

실행 결과

Longest palindrome substring is: ispalapsi
Length is: 9