C++ 회문 분할(Palindrome Partitioning) 알고리즘: 최소 컷 횟수 구하기

C++ 회문 분할(Palindrome Partitioning)이란?

회문 분할은 하나의 입력 문자열을 여러 부분으로 나누었을 때, 분할된 모든 부분 문자열이 회문(팰린드롬)이 되도록 하는 것을 의미합니다. 이 글에서는 주어진 문자열을 회문으로 분할하기 위해 필요한 최소 컷(cut) 횟수를 구하는 방법을 다룹니다.

예를 들어 문자열이 "ababbbabbababa"라고 가정해 보겠습니다. 이 문자열을 아래와 같이 분할하면 딱 3번의 컷만으로 모든 조각을 회문으로 만들 수 있습니다.

a | babbbab | b | ababa

해결 알고리즘: 동적 계획법(Dynamic Programming)

이 문제는 동적 계획법을 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 두 개의 2차원 행렬을 활용하는 것입니다.

pal[i][j]: 인덱스 i부터 j까지의 부분 문자열이 회문인지 여부를 저장
cut[i][j]: 인덱스 i부터 j까지의 구간을 회문으로 분할하는 데 필요한 최소 컷 수를 저장

구체적인 알고리즘 단계는 다음과 같습니다.

n := 문자열 str의 길이
cut 행렬과 pal 행렬을 각각 n × n 크기로 정의
i := 0부터 n-1까지 반복:
- pal[i][i] := true, cut[i][i] := 0 (길이 1인 부분 문자열은 항상 회문)
len을 2부터 n까지 반복:
- i를 0부터 n-len까지 반복:
  - j := i + len - 1 (부분 문자열의 끝 인덱스)
  - len == 2라면: str[i] == str[j]일 때 pal[i][j] := true
  - 그 외에는: str[i] == str[j] && pal[i+1][j-1]일 때 pal[i][j] := true
  - pal[i][j]가 true이면 cut[i][j] := 0
  - 그렇지 않으면:
    - cut[i][j] := ∞ (무한대로 초기화)
    - k를 i부터 j-1까지 반복하며 cut[i][j] = min(cut[i][j], cut[i][k] + cut[k+1][j] + 1)로 갱신
최종 결과로 cut[0][n-1]을 반환

여기서 pal[i][j]의 계산 원리는 직관적입니다. 양 끝 문자가 서로 같고(str[i] == str[j]), 그 사이 구간(i+1 ~ j-1)이 이미 회문이라면 전체 구간도 회문이 됩니다.

C++ 구현 예제

아래 코드를 통해 실제 구현을 살펴보겠습니다.

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

int min(int a, int b) {
    return (a < b) ? a : b;
}

int minPalPartion(string str) {
    int n = str.size();
    int cut[n][n];
    bool pal[n][n]; // i~j 구간이 회문이면 true
    for (int i = 0; i < n; i++) {
        pal[i][i] = true; // 길이 1인 부분 문자열은 항상 회문
        cut[i][i] = 0;
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) { // 길이가 len인 모든 부분 문자열 탐색
            int j = i + len - 1; // 끝 인덱스 설정
            if (len == 2) // 두 글자짜리 문자열인 경우
                pal[i][j] = (str[i] == str[j]);
            else // 세 글자 이상인 경우
                pal[i][j] = (str[i] == str[j]) && pal[i+1][j-1];
            if (pal[i][j] == true)
                cut[i][j] = 0;
            else {
                cut[i][j] = INT_MAX; // 초기값을 무한대로 설정
                for (int k = i; k <= j - 1; k++)
                    cut[i][j] = min(cut[i][j], cut[i][k] + cut[k+1][j] + 1);
            }
        }
    }
    return cut[0][n-1];
}

int main() {
    string str = "ababbbabbababa";
    cout << "Min cuts for Palindrome Partitioning is: " << minPalPartion(str);
}

실행 결과

입력

ababbbabbababa

출력

Min cuts for Palindrome Partitioning is: 3

시간 및 공간 복잡도

위 구현은 세 겹의 중첩 반복문을 사용하므로 시간 복잡도는 O(n³), 두 개의 n × n 행렬을 사용하므로 공간 복잡도는 O(n²)입니다. 참고로, 회문 판별을 컷 계산과 함께 한 번의 순회로 처리하도록 최적화하면 시간 복잡도를 O(n²)까지 줄일 수 있습니다.