문제 개요
두 문자열 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) 크기의 DP 테이블(2차원 행렬)을 생성합니다.
dp[0][0] := 1로 초기화하고, 모든 행의 0번째 열(dp[i][0])을 1로 설정합니다. 빈 문자열은 어떤 문자열에서든 항상 한 가지 방법(모든 문자를 제거하는 방법)으로 만들 수 있기 때문입니다.
i를 1부터 n까지 반복하면서, 각 i에 대해 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]을 반환합니다.
예제 코드
다음 구현 예제를 통해 더 잘 이해해 보겠습니다.
#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
복잡도 분석
이 알고리즘의 시간 복잡도는 두 문자열의 길이를 n, m이라 할 때 O(n × m)이며, 2차원 DP 테이블을 사용하므로 공간 복잡도 역시 O(n × m)입니다. 완전 탐색으로 모든 부분 수열을 확인하는 지수 시간 복잡도 방식과 비교하면, 동적 계획법을 활용하면 입력 크기가 커져도 실용적인 시간 안에 문제를 해결할 수 있다는 장점이 있습니다.