팰린드롬인 부분수열 개수 구하기

팰린드롬인 부분수열 개수 구하기(Counting All Palindromic Subsequences) 알고리즘에 대하여 포스팅을 해 보도록 하겠습니다.

일단 각각의 정의에 대해서 한번 설명을 간단하게 해 보겠습니다.

팰린드롬(Palindrome)은 앞에서부터 읽으나, 뒤에서부터 읽으나 같은 내용인 단어를 뜻합니다. 예를들어 '토마토'라던지 '바밤바', 'level', 'racecar' 등등이 있겠죠.

부분수열(Subsequence)은 원래 수열이나 배열에서 순서는 그대로 두고 일부 원소를 제거한 수열을 뜻합니다. 예를들어 abcdefg 라는 수열(Sequence)가 있다고 할 떄 abc와 bcd 와 같은 녀석들도 부분수열이 되지만, adg와 같은 녀석도 부분수열이 됩니다. 하지만 순서가 바뀌는 cba 같은 녀석은 부분 수열이 안됩니다.

그러면 이제 어떠한 문자열(String)에 대하여 팰린드롬인 부분수열(Palindromic subsequence)의 개수를 세 보도록 하겠습니다. 

일단은 부분수열이 중복이라도, 위치가 다르면 다른 것으로 세는 경우부터 따져보도록 하겠습니다.

즉, 예시로 'aab'의 팰린드롬 부분수열은 { 'a', 'a', 'b', 'aa' }가 되며, 'a'가 2개이지만 문자열의 첫번째 원소와 두번째 원소로 각각 샌 경우입니다.

일단 이 문제에 대해서 풀이법을 스스로 한번 생각해보는 것을 추천한다고 합니다.

다음 GeeksforGeeks 포탈에서 문제를 한번 풀어볼 수 있습니다. 로그인이 필요하긴 합니다만 별도의 개발환경 설정 없이 문제를 풀어볼 수 있습니다.

http://practice.geeksforgeeks.org/problems/count-palindromic-subsequences/1

이 문제 답안의 특징을 살펴보면, 일단 길이가 1인 문자열에 대해서는 팰린드롬 부분수열이 무조건 1개입니다. 그 보다 긴 경우를 고려를 해야 하는데 부분문제로 나누어서 풀이할 수 있습니다. 즉 다이나믹 프로그래밍으로 해결을 할 수 있지요. 아래와 같은 recurrence가 나타납니다.

classic dynamic programming problem, which can be solved using the following recurrence:

• Let $P(L, R)$ be the number of palindromic subsequences in $S[L...R]$, then
• $P(L, R) = \begin{cases} 1 &\text{if } L = R \\P(L + 1, R) + P(L, R - 1) - P(L +1, R - 1) &\text{if } S(L) \neq S(R) \\ P(L + 1, R) + P(L, R - 1) + 1 &\text{if } S(L) = S(R)\end{cases}$

< 출처: csacademy.com >

P(L,R)은 부분문자열 S[L...R]에서 나타나는 팰린드롬 부분수열이고, L과 R은 부분문자열의 시작과 끝 인덱스 번호입니다. L=R인 경우는 길이가 1인 부분 문자열입니다.

S(L) != S(R)인 경우는 왼쪽에서 범위가 1만큼 줄어든 P(L+1, R)과 오른쪽에서 범위가 1만큼 줄어든 P(L, R-1)의 개수를 더한 뒤, 중복으로 더해진 P(L+1, R-1)를 빼 줍니다. P(L+1, R)와 P(L, R-1) 둘 다 P(L+1, R-1)의 범위에서 나타난 정답값을 중복으로 포함하기 때문에 빼 준 것이죠.

S(L) = S(R)의 경우에는 위 경우와 달리 중복으로 더해준 P(L+1, R-1)을 빼지 않고 또 1을 더해줍니다. 

 { P(L+1, R-1)에 해당하는  개수 } = { P(L+1, R-1) 부분수열의 양 끝에 S(L)과 S(R)을 붙인 새로운 팰린드롬 부분수열 개수 }

이기 때문이죠. 그리고 추가적으로 1을 더한 값은 S(L)과 S(R)로만 이루어진 길이가 2인 부분수열의 개수입니다.

이렇게 재귀적인 방법으로 문제를 풀 수 있으며, 재귀 트리를 그려보면 겹치는 부분문제들이 있으므로 이를 메모이제이션(memoization)한 다이나믹 프로그래밍을 이용하여 효율적으로 문제를 해결할 수 있습니다.

Top-Down 방식으로 작성한 DP 솔루션 코드입니다.

 
/*
Please note that it's Function problem i.e.
you need to write your solution in the form of Function(s) only.
Driver Code to call/invoke your function would be added by GfG's Online Judge.*/
int** cps;

int get(int start, int end, string& str);
/*You are required to complete below method */
int countPS(string str)
{
    int ans;
    int len = str.length();
    cps = (int**) calloc(sizeof(int*) , (len+1));
    for (int i=0; i < len+1; i++) {
        cps[i] = (int*) calloc(sizeof(int), (len+1));
    }
    
    
    ans = get(0, len-1, str);
    //free allocated memory
    for(int i=0; i <len+1; i++) {
        free(cps[i]);
    }
    free(cps);
    return ans;
   //Your code here
}

int get(int start, int end, string& str) {
    if (start > end) return 0;
    if (start == end) return 1;
    if (cps[start][end]) return cps[start][end];
    
    if (str[start] == str[end]) {
        cps[start][end] = get(start, end-1, str) + get(start+1, end, str) + 1;
    } else {
        cps[start][end] = get(start, end-1, str) + get(start+1, end, str) - get(start+1, end-1, str);
    }
    return cps[start][end];
}
 

그리고 이제 중복을 허용하지 않는 팰린드롬 부분수열의 개수를 세는 경우를 따져보도록 하겠습니다.

앞선  예시에서 'aab'의 팰린드롬 부분수열은 중복을 허용하는 경우{ 'a', 'a', 'b', 'aa' }가 되며, 중복을 허용하지 않는 경우는 { 'a', 'b', 'aa' } 가 됩니다.

중복을 허용하지 않는 경우 중복을 허용하는 경우 보다 조금 더 까다로운데, dynamic programming의 점화식의 인자가 2개에서 3개로 늘어나게 됩니다. 3번째 인자는 가장 바깥에 감싸고 있는 알파뱃을 나타내는 시그마입니다.

• Let $DP(L, R, \sigma)$ be the number of distinct palindromic subsequences in $S[L..R]$ which are bordered with $\sigma$.
• $DP(L, R, \sigma) = \begin{cases} 0 &\text{if } L > R \\ 1 &\text{if } L = R \ \text{and} \ S(L) = \sigma \\DP(L + 1, R, \sigma) + DP(L, R - 1, \sigma) - DP(L +1, R - 1, \sigma) &\text{if } S(L) \neq \sigma \ \text{or} \ S(R) \neq \sigma \\ 2 + \sum_{\theta \in \{a, b, .., z\}} DP(L + 1, R - 1, \theta) &\text{if } S(L) = S(R) = \sigma \end{cases}$

S(L)=S(R)=sigma 의 경우는 DP(L+1, R-1, *)를 모두 더하는데, 원래 있던 각각의 부분수열들의 가장 바깥에 σ 글자로 패딩을 입힌 글자들을 셉니다. 그리고 더해주는 2의 경우는 { 'σ' , 'σσ' }의 경우가 됩니다. 기존의 팰린드롬 문자열들은 σ 패딩을 입혔기 때문에 모두 길이가 3 이상이므로, 중복이 될 일은 없습니다.

그러면 약간 헷갈릴 수 있는 부분이, 글자가 σ가 아닌 길이가 1인 팰린드롬 문자열들의 경우는 어떻게 하냐고 할 수 있는데, 해당 항목들은 DP(L, R, σ)가 아닌 닌 곳에서 세고있기에 상관이 없습니다. 

예를 들어서 'aba' 문자열에 대하여 팰린드롬 부분수열은 다음과 같습니다.

{ a, b, aa, aba }

위 Recurrence를 적용해보면

DP(1, 3, a) = DP(2, 2, *) + 2

DP(2, 2, *) = { b }

입니다. 따라서 DP(2, 2, *)에 a로 패딩을 입힌 새로운 팰린드롬 부분수열 { aba } 과, +2에 해당하는 { a, aa }를 합집합 한 결과인 { a, aa, aba }가 DP(1, 3, a)에 해당되고, { b }는 DP(1, 3, b)에 포함됩니다.

따라서 DP(1,3,a) = { a, aa, aba } 이고 / DP(1,3,b) = { b } 이됩니다. 

따라서 글자가 σ가 아닌 길이가 1인 팰린드롬 문자열들의 경우는 DP(L, R, σ)에서 세고 있지 않기에 위의 의문은 해결이 되었습니다.

제가 해당 솔루션을 보고 이해가 가지 않은 부분들을 고심하면서 해결한 내용을 블로그에 포스팅 해 보았는데, 혹시나 궁금하신점이나 의견있으시면 댓글로 달아주시면 내용에 반영하도록 하겠습니다.

[참고]

http://www.geeksforgeeks.org/count-palindromic-subsequence-given-string/

https://csacademy.com/contest/round-57/task/distinct-palindromes/solution/