회문 분할(Palindrome Partitioning): 최소 컷으로 문자열을 회문 단위로 나누는 알고리즘

회문 분할(Palindrome Partitioning) 알고리즘은 하나의 문자열을 입력으로 받아, 분할된 모든 부분 문자열이 회문(palindrome)이 되도록 문자열을 나누는 방법을 다룹니다.

여기서 우리가 구해야 할 것은 주어진 문자열을 회문 단위로 분할하기 위해 필요한 최소 컷(cut)의 개수입니다.

입력과 출력

입력:
하나의 문자열. 예: "ababbbabbababa"
출력:
회문으로 분할하기 위한 최소 컷의 개수. 이 예제에서는 3번의 컷이 필요합니다.
분할 결과: a | babbbab | b | ababa

알고리즘

이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 두 개의 n×n 행렬을 사용하는데, 하나는 부분 문자열이 회문인지 여부를 저장하는 pal 행렬이고, 다른 하나는 각 구간을 회문으로 만들기 위한 최소 컷 수를 저장하는 cut 행렬입니다.

minPalPart(str)

입력: 주어진 문자열.

출력: 해당 문자열에 대한 회문 분할의 최소 컷 수.

Begin
    n := length of str
    define cut matrix and pal matrix each of order n x n

    for i := 0 to n, do
        pal[i, i] := true
        cut[i, i] := 0
    done

    for len in range 2 to n, do
        for i in range 0 to n – len, do
            j := i + len – 1
            if len = 2, then
                if str[i] = str[j]
                    pal[i, j] := true
            else
                if str[i] = str[j] and pal[i+1, j-1] ≠ 0
                    pal[i, j] := true

            if pal[i, j] is true, then
                cut[i, j] := 0
            else
                cut[i, j] := ∞
                for k in range i to j-1, do
                    cut[i, j] := minimum of cut[i, j] and (cut[i, k] + cut[k+1, j+1] + 1)
                done
        done
    done
    return cut[0, n-1]
End

동작 원리

길이가 1인 부분 문자열은 항상 회문이므로 pal[i][i]를 true로 설정하고, 컷 수는 0으로 초기화합니다.
길이가 2인 경우 두 문자가 같으면 회문입니다.
길이가 3 이상인 경우 양 끝 문자가 같고, 그 사이의 부분 문자열(pal[i+1][j-1])이 회문일 때 전체가 회문이 됩니다.
부분 문자열이 회문이라면 컷 수는 0이고, 그렇지 않다면 가능한 모든 분할 지점 k에 대해 cut[i][k] + cut[k+1][j] + 1의 최솟값을 구합니다.

C++ 구현 예제

#include <iostream>
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);
}

실행 결과

Min cuts for Palindrome Partitioning is: 3

위 예제에서 문자열 "ababbbabbababa"는 a | babbbab | b | ababa와 같이 3번의 컷으로 모두 회문인 부분 문자열로 분할할 수 있습니다. 이 알고리즘의 시간 복잡도는 O(n³)이며, 공간 복잡도는 O(n²)입니다.