이번 글에서는 문자열 처리를 위한 동적 계획법(DP)의 세 가지 핵심 문제를 살펴보겠습니다. 각 문제는 이전 문제의 개념을 확장하여 최종적으로 편집 거리(Edit Distance) 문제를 해결합니다.

1. 서로 다른 서브시퀀스 개수

문자열 s와 t가 주어졌을 때, s의 서브시퀀스 중 t와 동일한 것의 개수를 구합니다. 편집 거리 개념에서 '삭제'는 긴 문자열의 문자를 제거하는 연산으로, 이 문제에서는 s에서 문자를 삭제하여 t를 만드는 방법의 수를 계산합니다.

DP 테이블을 dp[i][j]로 정의합니다. 여기서 i는 s의 처음 i개 문자, j는 t의 처음 j개 문자를 의미합니다. 핵심 점화식은 다음과 같습니다.

• 초기화: dp[i][0] = 1 (t가 빈 문자열이면 s를 모두 삭제하는 한 가지 방법), dp[0][j] = 0 (j > 0, s가 빈 문자열이면 불가능), dp[0][0] = 1.
• 점화식:
  • s[i-1] == t[j-1]이면 dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (마지막 문자를 매칭하거나 무시하는 두 경우)
  • 그렇지 않으면 dp[i][j] = dp[i-1][j] (s의 마지막 문자를 무시)

DP 값이 커질 수 있으므로 uint64_t 타입을 사용해야 오버플로우를 방지할 수 있습니다.

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.size(), m = t.size();
        vector<vector<uint64_t>> dp(n + 1, vector<uint64_t>(m + 1, 0));
        
        // 빈 t 문자열에 대한 초기화
        for (int i = 0; i <= n; ++i) dp[i][0] = 1;
        
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (s[i-1] == t[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][m];
    }
};

2. 두 문자열의 삭제 연산

이 문제에서는 두 문자열 word1과 word2에 대해 문자를 삭제할 수 있으며, 두 문자열을 동일하게 만드는 데 필요한 최소 삭제 횟수를 구합니다. 이전 문제와 달리 양쪽 문자열 모두에서 삭제가 가능합니다.

방법 1: 직접 DP

dp[i][j]는 word1의 처음 i개 문자와 word2의 처음 j개 문자를 동일하게 만드는 최소 삭제 횟수입니다. 점화식은 다음과 같습니다.

• 초기화: dp[i][0] = i, dp[0][j] = j
• 점화식:
  • 문자가 같으면 dp[i][j] = dp[i-1][j-1] (추가 삭제 불필요)
  • 다르면 dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1) (하나의 문자 삭제)

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        
        for (int i = 0; i <= n; ++i) dp[i][0] = i;
        for (int j = 0; j <= m; ++j) dp[0][j] = j;
        
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (word1[i-1] == word2[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1);
                }
            }
        }
        return dp[n][m];
    }
};

방법 2: 최장 공통 서브시퀀스(LCS) 활용

두 문자열의 최장 공통 서브시퀀스 길이를 lcs라고 하면, (word1.size() - lcs) + (word2.size() - lcs)가 최소 삭제 횟수입니다. 즉, 두 문자열의 전체 길이에서 LCS 길이의 두 배를 뺀 값입니다.

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (word1[i-1] == word2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        int lcs = dp[n][m];
        return (n - lcs) + (m - lcs);
    }
};

3. 편집 거리 (에디트 거리)

이 문제는 삭제 외에도 삽입과 교체 연산을 허용합니다. word1을 word2로 변환하는 최소 편집 횟수를 구합니다.

dp[i][j]를 word1의 처음 i개 문자를 word2의 처음 j개 문자로 변환하는 최소 편집 횟수라고 정의합니다.

• 초기화: dp[i][0] = i (모두 삭제), dp[0][j] = j (모두 삽입)
• 점화식:
  • 문자가 같으면 dp[i][j] = dp[i-1][j-1]
  • 다르면 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 (각각 삭제, 삽입, 교체)

이전 문제의 LCS 접근법을 사용할 수 없는 이유는 LCS는 순서를 유지한 공통 부분만 고려하지만, 편집 거리는 교체 연산을 통해 순서를 깨지 않고도 더 적은 연산으로 변환할 수 있기 때문입니다. 예를 들어, "abc"와 "abd"는 LCS 길이가 2("ab")이지만, 실제로는 'c'를 'd'로 교체하는 1회 연산으로 충분합니다.

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        
        for (int i = 0; i <= n; ++i) dp[i][0] = i;
        for (int j = 0; j <= m; ++j) dp[0][j] = j;
        
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (word1[i-1] == word2[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                }
            }
        }
        return dp[n][m];
    }
};

세 문제 모두 동적 계획법의 전형적인 패턴을 보여줍니다. 첫 번째 문제는 단방향 삭제만 허용하는 기본 형태이고, 두 번째 문제는 양방향 삭제로 확장되며, 마지막 문제는 세 가지 연산(삽입, 삭제, 교체)을 모두 포함하는 가장 일반적인 형태입니다. 이러한 점진적 확장을 통해 복잡한 문자열 편집 문제를 체계적으로 해결할 수 있습니다.