[백준 9252] LCS2 C++

9252번: LCS 2

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

예제 입력 1

ACAYKP

CAPCAK

1. 접근 방법

동적 계획법을 통해 특정 범위까지의 값을 구해놓고 다른 범위의 값을 구할 때 이전에 구했던 값을 이용해 빠르게 구한다.

표는 0행 0열부터 시작한다고 가정

first 문자열은 세로 문자열이고, second 문자열은 가로 문자열을 의미

표의 0행과 0열은 문자열을 서로 비교하지 않았을 때를 의미하므로 모두 0을 넣어준다.

dp[7][7]의 일부

현재 두 문자가 같을 때

2행 4열을 보면 숫자 '2'가 있는데 이 의미는 'AC'와 'CAPC'의 LCS 길이를 의미한다. (LCS : 'AC')

first[1] ('C') 와 second[3] ('C') 를 비교하기 전의 LCS 길이는 'A'와 'CAP'까지 비교한 dp[1][3] = 1이다

여기에 서로 동시에 'C'가 추가되었으므로 dp[1][3]에 1을 더해준 값이 'AC'과 'CAPC'의 LCS 길이이다.

현재 두 문자가 다를 때

현재 비교하는 문자가 포함되기 직전의 LCS값 중 큰게 오게된다.

-> dp[3][6]의 값은 'ACA' 와 'CAPCA'의 LCS 길이(3), 'AC' 와 'CAPCAK'의 LCS길이(2) 중 큰 값인 3이 오게된다.

위와 같은 방식으로 표를 추가 해 주면 아래와 같은 표가 완성이 된다.

아래 표에서 우측 하단의 숫자가 LCS길이가 된다.

dp[7][7]

 

LCS값이 최초로 만들어진 곳을 탐색하고, 현재 행과 열이 경계가 되어 이전 숫자가 만들어진 곳을 탐색한다.

이 때 해당 숫자는 각각의 행과 열 중에서 가장 먼저 나타난 것을 찾아간다.

연속적이지 않아도 되기 때문에 서로다른 LCS 문자열이 나타날 수 있다

LCS 문자열 구하기

<code>

#include <iostream>
#include <cstring>
 
using namespace std;
 
string first, second, LCS = "";
int dp[1001][1001];
 
void findLCS(){
    // dp 배열을 모두 0으로 초기화
    memset(dp, 0, sizeof(dp));
    
    // LCS표를 구하는 과정
    for(int row = 1; row <= first.size(); row++){
        for(int col = 1; col <= second.size(); col++){
            if(first[row-1] == second[col-1]){
                // 만약 같은 문자가 나오면 두 문자열에서 
                // 해당 두 문자를 비교하기 전의 LCS의 길이에 1을 더한다
                dp[row][col] = dp[row-1][col-1] + 1;
            }
            // 문자가 다르다면 first[row-1]까지의 문자열 + second[col] 까지의 문자열 간의 LCS값과
            // first[row]까지의 문자열 + second[col+1] 까지의 문자열 간의 LCS값 중 큰값을 저장
            else dp[row][col] = max(dp[row-1][col], dp[row][col-1]);
        }
    }
    cout << dp[first.size()][second.size()] << "\n";
    
    int f_idx = second.size();
    for(int row = first.size(); row >= 1; row--){
        for(int col = f_idx; col >= 1; col--){
            if(dp[row][col] == dp[row-1][col]){
                // 바로 위 dp값이 같으면 현재 열 값을 유지한다
                f_idx = col;
                break;
            }
            else if(dp[row][col] == dp[row][col-1]) continue;
            else{
                LCS = first[row-1] + LCS;
            }
        }
    }
    cout << LCS;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> first >> second;
    findLCS();
    return 0;
}
 

2021 02 05

4ms