[백준 9251] 알고리즘 111일차 : LCS

https://www.acmicpc.net/problem/9251

9251번: LCS

C++ DP

최장 공통 부분 수열

두 문자열 ACAYKP CAPCAK가 있으면 공통된 부분수열의 최장길이를 출력하는 문제

ACAYKP CAPCAK의 경우 ACAYKP CAPCAK 로 ACAK이므로 4이다.

 

접근방법

부분수열이 양 문자열에서 시작하는 위치도 끝나는 위치도 문자열의 처음부터 끝부분까지 고려되어야 하기 때문에

2차원배열을 사용하여 DP로 풀어야한다.

 

2차원배열은 (첫번째 문자열 길이 + 1) * (두번째 문자열 + 1)로 구성된다.

1열과 1행은 각각 0으로 채우고 인덱스번호 1번부터 문자열이 할당된다. 그래야 Out of bound가 발생하지 않는다.

2차원배열(이하 dp)의 각 원소가 나타내는 값은 아래와 같다.

dp[i][j]는 첫번째 문자열(이하 a)을 i번째까지 보고 두번째 문자열(이하 b)를 j번째까지 봤을때의 LCS(최장 공통 부분 수열)길이를 나타낸다.

예를들어, ACAYKP CAPCAK의 경우 dp[2][3]의 값은 ACAYKP와 CAPCAK의 LCS길이 이므로 AC CAP -> 1이 된다.

 

각 요소는 그 지점까지의 최장 길이를 갖고 있는 것이므로 dp의 마지막 원소(표 상으로 최우측하단 원소)가 최종 결과가 된다.

dp의 마지막 원소는 두 문자열을 모두 끝까지 봤을때 LCS길이를 나타내는 것이기 때문이다.

 

이 부분이 나누어진 작은 문제를 해결하는 방법과 하나의 큰 문제를 해결하는 방법이 같다는 DP원리가 적용되는 부분이다.

 

코드설명

2중 반복문을 돌면서 dp배열의 원소 값을 채운다.

이때 해당 지점의 두 문자열의 문자가 같으면

두 문자는 포함하지 않는 상태에서의 LCS길이(= dp[i-1][j-1] )에 본인들을 포함하여 +1해준다.

따라서 dp[i][j] = dp[i-1][j-1] + 1이 된다.

->표 상으로는 지금 위치의 왼쪽 대각선 원소 + 1 

 

반면 해당 지점의 두 문자열의 문자가 다르면

둘 중 하나의 문자열을 포함하지 않은 상태에서의 LCS길이 중 큰 값을 대입한다.

이때 둘 중 하나의 문자열을 포함하지 않은 상태에서의 LCS길이는

1. a의 해당지점 문자를 포함하지 않은 상태에서의 LCS길이 = dp[i-1][j]

2. b의 해당지점 문자를 포함하지 않은 상태에서의 LCS길이 = dp[i][j-1]

1. 2. 중 큰 값을 dp[i][j]에 대입한다.

-> 표 상으로는 지금 위치의 왼쪽값, 위쪽값을 비교하여 큰값을 대입하는 것.

 

소스코드

#include <iostream>
#include <string>
using namespace std;

int main(){
    //init & input
    string a, b;
    cin >> a >> b;
    
    //process
    int dp[1001][1001];
    dp[0][0] = dp[0][1] = dp[1][0] = 0;
    
    for(int i = 1 ; i-1 < a.size() ; i++){
        for(int j = 1 ; j-1 < b.size() ; j++){
            if(a[i-1] == b[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
            }else{
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    
    //output
    cout << dp[a.size()][b.size()] << "\n";
    
    return 0;
}