DP on Strings 문자열 문제에서의 동적계획법

문자열은 웹개발에서 가장 중요한 요소 중 하나이고 코딩테스트에서 단골로 출제되는 알고리즘이 Dynamic Programming(동적계획법)이기 때문에 가끔씩 DP를 사용하는 문자열 문제가 출제될 때가 있습니다. 어떤 문제든지 패턴을 파악하고 있으면 조금 더 쉽게 풀 수 있습니다. 오늘은 DP를 사용하면 문자열 문제 몇 개를 살펴보도록 하겠습니다.

 

가장 많이 출제되는 유형의 문제는 두 문자열에서 공통되는 문자의 개수를 찾아내거나 공통되는 문자열의 길이를 구하는 종류의 문제입니다. 

 

 

예를 들어 "XMJYAUZ”, “MZJAWXU” 두 문자열에서 공통된 글자의 수를 찾아내려고 할 때, 위와 같은 테이블을 만들 수 있을 것입니다. 표에서 인덱스는 각각 하나의 문자를 나타내고 만약 해당하는 인덱스의 문자열이 같은 경우 카운트를 시키는 방법으로 문자열의 길이를 구할 수 있습니다.

 

즉 D[i][j] = 첫번째 텍스트의 i 번째 문자와 두번째 텍스트의 j 번째 문자열 까지 비교했을 때 최대 공통 문자 개수 라고 정의 할 수 있고 두 문자열이 같으면 D[i-1][j-1] 에서 +1 한 값을 저장하게 됩니다. 코드를 보면 다음과 같습니다.

 

    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[text1.length()][text2.length()];
    }

 

또 등장할 수 있는 이런 유형의 문제중에는 팰린드롬(palindrome) 문자열을 찾는 문제입니다. 여기서 팰린드롬은 기러기, 스위스 처럼 뒤집어 읽어도 똑같은 문자열을 이야기 합니다.

 

그렇다면 주어진 문자열에서 팰린드롬한 substring의 의 개수를 반환하는 문제를 생각해 보겠습니다.

 

D[i][j] = i번째 문자부터 j번째 문자까지 팰린드롬여부(boolean)라고 정의하겠습니다. 만약 i번째 문자와 j번째 문자가 서로 같고 D[i + 1][j - 1] 이 TRUE 라면 D[i][j] 도 TRUE 가 될 것입니다. 코드로 구현해 보면 다음과 같습니다.

 

public int countSubstrings(String s) {
        int answer = 0;
        boolean[][] dp = new boolean[s.length()][s.length() + 1];
        for (int i = dp.length - 1; i >= 0; i--) {
            for (int j = i; j < dp.length; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && 
                    (j - i < 3 || dp[i + 1][j - 1]);
                answer += dp[i][j] ? 1 : 0;
            }
        }
        return answer;
    }

 

물론 위의 두 문제는 완전탐색을 통해 풀어도 괜찮습니다. 제가 모르는 다른 효율적인 알고리즘을 사용할 수도 있을 것입니다. 하지만 DP를 사용한 해법도 같이 기억하고 있으면 코테에서 분명히 도움이 되리라고 생각합니다.

 

오늘은 DP를 사용한 문자열 문제의 풀이를 소개해 봤습니다. 감사합니다.