Computer Science & Engineering

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

문제

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

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

풀이

LCS문제는 DP를 이용한다. 2차원 배열 DP에서 dp[i][j]가 의미하는 것은 두 문자열 s1, s2에 대하여 s1의 i번째 문자와 s2의 j번째 문자까지 공통되는 부분 수열의 길이를 나타낸다. 배열은 다음과 같다.

만약 s1[i]와 s2[j]가 같다면 dp[i-1][j-1]에 1을 더한 값을 넣는다. 이전 길이에서 하나 더 늘어났기 때문이다. 그렇지 않고 만 약 s1[i]와 s2[j]가 같지 않다면 dp[i-1][j]와 dp[i][j-1] 중에 더 큰 값을 넣는다. 이전 문자까지 이루어진 공통 부분 수열 중 가장 큰 값을 넣어야하기 때문이다. 코드를 짜면 다음과 같다.

소스 코드

#include <iostream>
#include <string>
#include <vector>
#include <deque>

using namespace std;

const int MN = 1001;

int dp[MN][MN];

int main() {
    string s1, s2; //두 문자열
    cin >> s1 >> s2;

    s1 = ' ' + s1; //1번 인덱스부터 사용하기 위해 앞에 공백을 추가
    s2 = ' ' + s2;

    for(int i = 1; i < s1.size(); i++) {
        for(int j = 1; j < s2.size(); j++) {
            if(s1[i] == s2[j]) //같은 경우
                dp[i][j] = dp[i-1][j-1] + 1; //이전 문자까지 중에 가장 큰 값에 1을 추가
            else //같지 않을 경우
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]); //이전 문자까지 중 가장 큰 값으로 설정
        }
    }

    cout << dp[s1.size()-1][s2.size()-1];
}

앞에 공백을 추가하는 이유는 1번 인덱스부터 사용하기 위해서이다. 대각선 값을 가져오는데 만약 첫 문자가 같은 경우 -1이 되므로 (1, 1)부터 인덱스를 시작하기 위하여 앞에 공백을 넣었다.

채점 결과