C++로 해결하는 고유 부분 수열(Distinct Subsequences) 개수 세기

두 개의 문자열 S와 T가 주어졌을 때, S의 부분 수열 중 T와 정확히 일치하는 서로 다른 경우가 몇 가지인지 세어야 합니다.

먼저 '부분 수열(subsequence)'의 개념부터 살펴보겠습니다. 부분 수열이란 원본 문자열에서 일부 문자(없을 수도 있음)를 제거하되, 나머지 문자들의 상대적인 순서는 그대로 유지한 채 만들어진 새로운 문자열을 의미합니다. 예를 들어 "ACE"는 "ABCDE"의 부분 수열이지만, "AEC"는 문자 순서가 바뀌었으므로 부분 수열이 아닙니다.

입력 문자열이 "baalllloonnn"과 "balloon"이라면, 두 번째 문자열을 만들 수 있는 서로 다른 선택 방법은 총 36가지입니다.

동적 계획법(DP) 접근 방식

이 문제는 동적 계획법을 활용하면 효율적으로 해결할 수 있습니다. 여기서 dp[i][j]는 "s의 첫 i개 문자로 만들 수 있으면서 t의 첫 j개 문자와 일치하는 부분 수열의 개수"를 의미합니다. 전체 알고리즘은 다음 단계로 진행됩니다.

알고리즘 단계

• n := s의 길이, m := t의 길이로 설정합니다. 인덱스 계산을 단순하게 만들기 위해 s와 t 앞에 공백을 하나씩 붙입니다.
• (n + 1) × (m + 1) 크기의 2차원 행렬(dp 테이블)을 생성합니다.
• dp[0][0] := 1로 설정하고, 모든 행의 0번째 열 값(dp[i][0])을 1로 초기화합니다. 빈 문자열은 어떤 문자열에서도 한 가지 방법(모든 문자를 제거)으로 만들 수 있기 때문입니다.
• i를 1부터 n까지 반복합니다.
  • j를 1부터 m까지 반복합니다.
  • 만약 s[i] == t[j]라면 dp[i][j] := dp[i-1][j-1]을 대입합니다.
  • 이후 항상 dp[i][j] := dp[i][j] + dp[i-1][j]를 더해 줍니다.
• 최종 결과값 dp[n][m]을 반환합니다.

점화식이 작동하는 원리

두 문자가 일치할 때는 현재 문자를 매칭에 사용하는 경우(dp[i-1][j-1])와 사용하지 않고 건너뛰는 경우(dp[i-1][j])를 모두 더해야 합니다. 반면 문자가 다르면 현재 위치의 t[j]를 새로 매칭할 수 없으므로 dp[i-1][j]만 반영하면 됩니다. 위 코드는 이 논리를 "조건에 따라 대입한 뒤 항상 덧셈을 수행"하는 간결한 형태로 구현했으며, 시간 복잡도는 O(n×m), 공간 복잡도 역시 O(n×m)입니다.

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int numDistinct(string s, string t) {
      int n = s.size();
      int m = t.size();
      s = " " + s;
      t = " " + t;
      vector < vector <lli> > dp(n + 1, vector <lli> (m + 1));
      dp[0][0] = 1;
      for(int i = 1; i <= n; i++)dp[i][0] = 1;
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= m; j++){
            if(s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1];
            dp[i][j]+= dp[i - 1][j];
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   cout << (ob.numDistinct("baalllloonnn", "balloon"));
}

입력

"baalllloonnn"
"balloon"

출력

36