[DP] Palindrome, 팰린드롬(회문) 만들기 - 2부

DP 연습문제 : Palindrome, 팰린드롬(회문) 만들기

문제

문자열이 하나 주어집니다. 회문을 만들기 위해서 문자열에 삽입해야 하는 최소의 문자 갯수를 찾으세요.

예제

ab : 회문을 만들려면 1개의 문자가 필요합니다.bab
aa : 이미 회문이기 때문에 문자가 필요없습니다. 0개
abcd : 회문을 만들려면 3개의 문자가 필요합니다. dcbabcd
abcda : 회문을 만들려면 2개의 문자가 필요합니다. adcbcda

• 여기서 재밌는점은 abcda 를 회문으로 만드는데 필요한 문자 갯수와 bcd 를 회문으로 만드는데 필요한 문자갯수는 같다는 점입니다. (왜그럴까요?)

abcde : 회문을 만들려면 4개의 문자가 필요합니다. edcbabcde

---

문제는 여기서 연습하실 수 있습니다. 정답을 보시기전에 문제를 먼저 풀어보시는것을 추천드립니다.

정답

1부에서 솔루션을 구할때 문자열에 문자를 더하는것보다 지우는 방식으로 정답을 찾은 것처럼, 여기서도 문자를 지우면서 접근해 나가겠습니다.

입력 문자열이 $str[1 \dotsc h]$ 라고 한다면, 이번 문제에서는 제일 끝 또는 앞에 위치한 문자 뿐만 아니라 어떤 위치의 문자든 지울 수 있기 때문에, 이 문제는 3개의 서브 문제로 다시 쪼개지게 됩니다.

1. 부분문자열 $str[l+1 \dotsc h]$ 의 최소 문자 입력 갯수 찾기. (맨 처음 문자를 지움)
2. 부분문자열 $str[l \dotsc h-1]$ 의 최소 문자 입력 갯수 찾기. (제일 끝의 문자를 지움)
3. 부분문자열 $str[l+1 \dotsc h-1]$ 의 최소 문자 입력 갯수 찾기. (양쪽의 문자가 서로 같아서 회문을 이루기 때문에 고려할 필요가 없음)

재귀적 솔루션

위의 예제에서 abcda 이 회문이 되기위해 필요한 최소 문자 갯수는 bcd 가 회문이 되기 위해 필요한 최소 문자 갯수와 같다는 사실을 기억하시나요?
그 이유는 해당 문자열의 처음과 끝의 문자가 'a'로 서로 같기 때문에 이미 부분적으로 회문을 이루고 있어서 회문인지 아닌지 고려할 필요가 없어졌기 때문입니다.
이제 우리는 이와같은 사실을 이용해서 재귀적 솔루션을 작성하려 합니다.

문자열 $str[1 \dotsc h]$ 이 주어졌을때 회문을 만들기 위해 삽입해야되는 최소의 문자 갯수를 찾는 함수를 $findMinInsertions(str[l \dotsc h])$ 라 정의하겠습니다. 문자열의 처음과 끝이 문자가 같다면 이미 부분적으로 회문을 이루고 있기 때문에 처음과 끝의 문자를 제외한 문자열 $str[l+1 \dotsc h-1]$ 만 고려하면 됩니다. 만약, 처음과 끝의 문자가 서로 같지 않다면, 문자열의 처음 또는 끝의 문자를 제거한 $str[l+1 \dotsc h]$ 이나 $str[l \dotsc h-1]$ 의 문자열을 고려하면 됩니다. (이때는 삽입 문자가 하나 추가된다고 고려되기 때문에 +1 을 잊지마세요!)
코드로 표현하면 다음과 같습니다.

if(str[l] == str[h]) { 
    findMinInsertions(str, l + 1, h - 1);
   } else {
       min(findMinInsertions(str, l, h - 1),
        findMinInsertions(str, l + 1, h)) + 1);
    }

다음은 위의 알고리즘을 이용해 만든 솔루션입니다.

// 주어진 문자열을 회문으로 만들기 위해 삽입 해야되는 최소 문자
// 개수 찾기 (단순 접근 솔루션)
#include <stdio.h>
#include <limits.h>
#include <string.h>

// 두 숫자중 최소값을 구하는 함수
int min(int a, int b)
{  return a < b ? a : b; }

// 최소 문자 삽입 갯수를 찾는 재귀 함수
int findMinInsertions(char str[], int l, int h)
{
    // Base Cases
    if (l > h) return INT_MAX;
    if (l == h) return 0;
    if (l == h - 1) return (str[l] == str[h])? 0 : 1;

    // 마지막과 첫번째 문자가 같은지 확인합니다.
    // 비교 결과에 따라서 위에 언급했듯이 서브문제가 호출되는 결과가 달라집니다.
    return (str[l] == str[h])? 
                     findMinInsertions(str, l + 1, h - 1):
                     (min(findMinInsertions(str, l, h - 1),
                     findMinInsertions(str, l + 1, h)) + 1);
}

// 위의 함수를 테스트하기위한 드라이버 프로그램
int main()
{
    char str[] = "geeks";
    printf("%d", findMinInsertions(str, 0, strlen(str)-1));
    return 0;
}

출력값

3

동적 계획법을 이용한 솔루션 (1)

이 문제는 DP 를 이용해서 푸는것이 좋습니다. '중복되는 서브문제'의 성질을 가지고 있기 때문입니다.
예를 들어, 위의 프로그램을 사용해서 "abcde" 를 회문으로 만들기 위해 삽입해야 하는 최소 문자개수를 찾겠습니다. 그렇다면 재귀 트리는 아래와 같습니다.

                   abcde
              /             \      
             /               \       
          bcde               abcd     
       /        \          /     \
      /          \        /       \
    cde           bcd    bcd      abc 
   /  \          /    \     
  de  cd        cd     bc ...

살펴보시면 문자열 'bcd' 와 'cd' 가 중복되서 사용되는것을 보실 수 있습니다. 이 문제 역시 DP 를 사용해야겠군요. 한번 계산된 서브 문제는 따로 저장해 놓았다가 다음에 다시 쓸 필요가 있겠습니다. 여기서는 다시 재귀를 쓰지말고 tabulation 을 이용해보도록 하겠습니다.

어떻게 서브 문제의 솔루션을 다시 사용할까요?
서브 문제의 솔루션을 저장하기 위한 2차원 테이블을 만들고 다시 같은 서브 문제를 만나면 푼 값을 바로 사용하도록 하겠습니다.

문자열 abcde 를 이용한다면 테이블의 값은 다음과 같이 저장됩니다.

a b c d e
----------
0 1 2 3 4
0 0 1 2 3 
0 0 0 1 2 
0 0 0 0 1 
0 0 0 0 0

2차원 테이블은 무슨 정보를 담고 있는걸까요? 2차원 list 를 dp라 정하겠습니다. dp[i][j] 의 의미는 j-i+1 의 길이를 가지고 있는 문자열이 회문이 되기 위해 삽입해야할 최소 문자 갯수를 의미합니다.
예를 들어서 "abcde" 는 0부터 4까지의 문자열 index 로 표시될 수 있습니다. 그렇기 때문에 최종적으로 우리는 dp[0][4] 를 찾으면 됩니다. 다른 예를 들자면, "bcd" 는 dp[1][3] 으로 표시되겠네요.

이제 위에 적힌 값을 자세히 따져보기로 하겠습니다.
일단 i <= j 인 경우만 dp[i][j] 의 값이 저장됩니다. 왜일까요? 문자열의 길이는 항상 양수 이기 때문에 그렇습니다.
테이블을 자세히 살펴보면 대각선 모양으로 값이 같은것을 볼 수 있습니다. 0의 값을 가진 dp[0][0], dp[1][1], dp[2][2], dp[3][3], dp[4][4] 는 각각 a, b, c, d, e 로써 단 하나의 문자를 나타냅니다. 하나의 문자는 그 자체로 회문이 되므로 더이상 값을 추가할 필요가 없습니다. 그렇기 떄문에 0 이 됩니다.
하나만 더 살펴볼까요? 1 의 값을 가진 dp[0][1], dp[1][2], dp[2][3], dp[3][4] 는 각각 ab, bc, cd, de 를 나타냅니다. 각 문자열들은 단 하나의 문자만 추가하면 회문이 되므로 1의 값을 가지겠네요.
다음은 생각 가능한 경우의 수를 써봤습니다.

Gap = 0:
(0, 0) (1, 1) (2, 2) (3, 3) (4, 4)

Gap = 1:
(0, 1) (1, 2) (2, 3) (3, 4)

Gap = 2:
(0, 2) (1, 3) (2, 4)

Gap = 3:
(0, 3) (1, 4)

Gap = 4:
(0, 4)

여기서 Gap 은 각 문자열의 길이 - 1 을 의미하죠. 솔루션에서 유용하게 쓰이는 모습을 보실 수 있습니다.

이런식으로 0 에서 출발해서 문자열의 길이가 n 이라면 n-1 까지 대각선 방향으로 값을 쭉 추가해주시면 됩니다. 물론 지금의 예제는 abcde 라서 가장 단순한 형태이기 때문에 저런식으로 채워지지만, 맨 처음 언급한 알고리즘을 잊어서는 안되겠습니다.

if(str[l] == str[h]) { 
    findMinInsertions(str, l + 1, h - 1);
   } else {
       min(findMinInsertions(str, l, h - 1),
        findMinInsertions(str, l + 1, h)) + 1);
    }

이것을 반복문 형태로 바꾸게 된다면,

table[l][h] = (str[l] == str[h])?
           table[l+1][h-1] : (min(table[l][h-1], table[l+1][h]) + 1);

이렇게 되겠네요.

// 동적 계획법을 이용한 
// 주어진 문자열이 회문이 되기 위한 
// 최소 삽입 문자 갯수를 찾는 프로그램 
#include <stdio.h>
#include <string.h>

 // 두 숫자중 최소값을 구하는 함수
int min(int a, int b)
{  return a < b ? a : b; }

// 최소 삽입 문자 갯수를 저장하는 DP 함수
int findMinInsertionsDP(char str[], int n)
{
    // n*n 사이즈의 테이블(2차원 배열)을 만듭니다. table[i][j]
    // 은 str[i..j] 가 회문이 되기 위한 최소 삽입 문자 갯수를 저장합니다.
    int table[n][n], l, h, gap;

    // 모든 테이블 값을 0 으로 설정합니다.
    memset(table, 0, sizeof(table));

    // 위의 설명대로 테이블을 대각선 방식으로 채웁니다.
    // gap 이 0 일때는 정답은 0 이니까 채울 필요가 없습니다.
    for (gap = 1; gap < n; ++gap)
        for (l = 0, h = gap; h < n; ++l, ++h)
            table[l][h] = (str[l] == str[h])?
                          table[l+1][h-1] :
                          (min(table[l][h-1], 
                           table[l+1][h]) + 1);

    // 우리가 원하는 답인 str[0..n-1] (전체 문자열) 의
    // 최소 삽입 문자 갯수를 요청합니다.
    return table[0][n-1];
}

// 함수를 테스트 하기위한 드라이버 프로그램
int main()
{
    char str[] = "geeks";
    printf("%d", findMinInsertionsDP(str, strlen(str)));
    return 0;
}

출력값

3

시간 복잡도 : $O(N^2)$ 공간 복잡도 : $O(N^2)$

동적 계획법을 이용한 솔루션 (2)

이 문제를 풀 수 있는 방법이 또 있습니다. 바로 LCS 를 이용한 방법인데요.
혹시 LCS 를 잘 모르신다면 아래의 내용을 이해하기 위해 이 포스팅을 필수로 보고오시는것을 추천드립니다.

LCS 를 잘 아신다는 가정하에 말씀드리겠습니다. 회문이라는것은 그 문자열을 거꾸로해도 기존의 문자열과 같은 문자열을 가지는 문장을 말합니다. 이 점을 이용해서 최소 삽입 문자 갯수를 찾는것입니다.

"adbb" 를 예로 들어보겠습니다. 이 문자열에 "da" 만 넣으면 회문이 됩니다. ("adbbda") 그렇다면 정답은 2 일텐데, 과연 진짜 그런지 알아봅시다. 이 문자열을 거꾸로하면 "bbda"가 되네요. "adbb"와 "bbda" 의 LCS는 "bb" 이므로 정답은 2가 됩니다. 여기서 문자열의 총 길이 4 에서 2를 빼주면 2 가 나오므로 정답 2와 일치합니다.

여기서 왜 문자열의 총 길이에서 LCS 의 길이를 빼줄까요? 거꾸로한 문자열과 기존의 문자열의 LCS 는 회문이라는 의미이므로, 처음에 맨 처음 문자와 끝 문자가 같으면 부분적으로 회문이라서 고려하지 않는다는 언급을 드린것처럼, 이 역시도 고려하지 않고 회문이 아닌 문자들만 추가하면 전체 문자열이 회문이 됩니다. 그렇기 때문에 전체 문자열의 길이에서 LCS 의 길이를 빼주면 됩니다. 정리하자면 다음과 같습니다.

1) 주어진 문자열과 거꾸로된 문자열, 이 둘의 LCS 의 길이를 찾는다. 이 길이를 L 이라 가정.
2) 주어진 문자열의 길이 - L 은 주어진 문자열이 회문이 되기위한 최소 삽입 문자 갯수.

// LCS 을 이용한 
// 주어진 문자열이 회문이 되기 위한 
// 최소 삽입 문자 갯수를 찾는 프로그램 
#include<stdio.h>
#include <string.h>

/* 두 정수중 가장 큰것을 고릅니다 */
int max(int a, int b)
{   return (a > b)? a : b; }

/* X[0..m-1] 와 Y[0..n-1] 의 LCS 의 길이를 반환합니다.*/
int lcs( char *X, char *Y, int m, int n )
{
   int L[n+1][n+1];
   int i, j;

   /* L[m+1][n+1] 의 테이블을 bottom up 방식으로 채웁니다.
         참고로 L[i][j] 은 X[0..i-1] 와 Y[0..j-1] 의 LCS 길이를 저장하고 있습니다.*/
   for (i=0; i<=m; i++)
   {
     for (j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;

       else if (X[i-1] == Y[j-1])
         L[i][j] = L[i-1][j-1] + 1;

       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }

   /* L[m][n] 은 X[0..n-1] 와 Y[0..m-1] 의 LCS 길이를 저장하고 있습니다. */
   return L[m][n];
}

// LCS 를 이용한 
// 최소 삽입 문자 갯수를 찾기 
int findMinInsertionsLCS(char str[], int n)
{
   // 주어진 문자열 'str'의 거꾸로된 문자열을 만듭니다.
   char rev[n+1];
   strcpy(rev, str);
   strrev(rev);

   // 최종 답을 찾습니다.
   // 즉, 주어진 문자열의 총 길이 'n' - lcs 의 길이 = 답
   return (n - lcs(str, rev, n, n));
}

// 위의 함수를 테스트하기위한 드라이버 프로그램
int main()
{
    char str[] = "geeks";
    printf("%d", findMinInsertionsLCS(str, strlen(str)));
    return 0;
}

출력값

3

위의 시간복잡도와 공간복잡도도 역시나 $O(n^2)$ 가 됩니다.

---

이정도 까지만 아셔도 회문 문제가 나온다면 쉽게 풀어내실 수 있을것이라 생각합니다.

이 포스팅은 Aashish Barnwal 가 작성한 글을 참고해서 만들었습니다.