← All Articles

[BAEKJOON] 9251. LCS

Posted on

문제 :

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

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


입력 :

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


출력 :

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



풀이 :

대표적인 이차원 DP 배열을 활용하는 문제였다.

우선 DP 알고리즘이 굉장히 어렵게 느끼는 나로서는 점화식을 세우는데 조금 많은 시간이 소요되었다.

문제는 간단하다. 입력받은 str1, str2 두개의 문자열의 각 인덱스 위치에서 최장 공통 배열 길이를 저장하는 dp 배열을 구현하면 해결할 수 있다.

즉 dp[i][j]에는 str1[j] 위치와 str2[i] 위치에서 각 문자열 끝까지의 문자들 중에서 가장 긴 최장 공통 배열의 길이를 저장해 둔다.

점화식

  • str1[j]와 str2[i]가 같을 경우 : dp[i][j] = max(dp[i+1][j+1] + 1, max(dp[i + 1][j], dp[i][j + 1]))
  • `str1[j]와 str2[i]가 다를 경우 : dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])`


코드 :

코드 보기/접기 
#include <iostream>
#include <string>

using namespace std;
int dp[1000][1000];

int main() {
    string str1, str2;
    cin >> str1 >> str2;
    int size1 = str1.length() - 1, size2 = str2.length() - 1, i, j;
    dp[size2][size1] = str1[size1] == str2[size2];
    for (i = size2 - 1; i >= 0; i--)
        dp[i][size1] = max(dp[i + 1][size1], ((str1[size1] == str2[i]) ? 1 : 0));
    for (i = size1 - 1; i >= 0; i--)
        dp[size2][i] = max(dp[size2][i + 1], ((str1[i] == str2[size2]) ? 1 : 0));
    for (i = size2 - 1; i >= 0; i--)
        for (j = size1 - 1; j >= 0; j--) {
            dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
            if (str2[i] == str1[j]) dp[i][j] = max(dp[i][j], dp[i + 1][j + 1] + 1);
        }
    cout << dp[0][0] << '\n';
    return 0;
}

AlgorithmalgorithmbaekjoonC++