C++ 동적 프로그래밍으로 두 문자열의 공통 부분 시퀀스 개수 구하기

두 문자열 str1과 str2가 주어졌을 때, 두 문자열에 공통으로 존재하는 부분 시퀀스(subsequence)의 개수를 계산하는 것이 이번 글의 목표입니다. 여기서는 동적 프로그래밍(Dynamic Programming) 기법을 활용하여 문제를 해결합니다.

동적 프로그래밍이란?

동적 프로그래밍은 분할 정복(Divide and Conquer)과 마찬가지로 하나의 큰 문제를 더 작고 단순한 하위 문제로 나누어 해결하는 방식입니다. 다만 분할 정복과 달리, 하위 문제들을 서로 독립적으로 풀지 않는다는 점이 특징입니다. 대신 작은 하위 문제들의 결과를 저장해 두었다가, 유사하거나 서로 겹치는 하위 문제를 풀 때 그 결과를 재활용합니다.

동적 프로그래밍은 문제를 비슷한 형태의 하위 문제들로 분해할 수 있고, 각 하위 문제의 결과를 재사용할 수 있는 경우에 적합합니다. 주로 최적화(optimization) 문제에 활용되며, 새로운 하위 문제를 풀기 전에 먼저 이전에 계산해 둔 결과들을 살펴본 뒤, 이들을 조합하여 최적의 해답을 도출합니다.

입출력 예시

입력 − string str1 = "abc"
      string str2 = "ab"
출력 − count is 3

설명 − 주어진 두 문자열에서 만들 수 있는 공통 부분 시퀀스는 { 'a', 'b', 'ab' }로 총 3개입니다.

입력 − string str1 = "ajblqcpdz"
      string str2 = "aefcnbtdi"
출력 − count is 11

공통 부분 시퀀스 − { "a", "b", "c", "d", "ab", "bd", "ad", "ac", "cd", "abd", "acd" }

문제 해결 접근 방식

두 문자열 str1과 str2를 입력받습니다.
length() 함수를 사용하여 각 문자열의 길이를 계산합니다. 이 함수는 문자열에 포함된 문자 수에 해당하는 정수값을 반환하며, str1의 길이는 len1에, str2의 길이는 len2에 저장합니다.
동적 프로그래밍을 구현하기 위해 2차원 배열 arr[len1+1][len2+1]을 생성합니다.
i가 0부터 len1 미만까지 반복하는 외부 루프를 시작합니다.
외부 루프 안에서 j가 0부터 len2 미만까지 반복하는 내부 루프를 시작합니다.
내부 루프에서 str1[i-1]과 str2[j-1]이 같다면 arr[i][j] = 1 + arr[i][j-1] + arr[i-1][j]로 설정합니다.
같지 않다면 arr[i][j] = arr[i][j-1] + arr[i-1][j] - arr[i-1][j-1]로 설정합니다.
최종적으로 arr[len1][len2] 값을 반환합니다.
결과를 출력합니다.

C++ 예제 코드

#include <iostream>
using namespace std;
// 문자열 내 공통 부분 시퀀스의 개수를 세는 함수
int countsequences(string str, string str2){
    int n1 = str.length();
    int n2 = str2.length();
    int dp[n1+1][n2+1];
    // DP 테이블 초기화
    for (int i = 0; i <= n1; i++){
       for (int j = 0; j <= n2; j++){
          dp[i][j] = 0;
       }
    }
    // str의 각 문자에 대해
    for (int i = 1; i <= n1; i++){
       // str2의 각 문자에 대해
       for (int j = 1; j <= n2; j++){
          // 두 문자열에서 문자가 같은 경우
          if (str[i - 1] == str2[j - 1]){
             dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j];
          }
          else{
             dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1];
          }
       }
    }
    return dp[n1][n2];
}
int main(){
    string str = "abcdejkil";
    string str2 = "bcdfkaoenlp";
    cout <<"count is: "<<countsequences(str, str2) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.

count is: 51