[c++] BOJ 9251번 :: LCS (풀이 및 설명 + 더 나은 코드)

LCS

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	19827	8068	6050	41.148%

문제

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

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

입력

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

출력

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

알고리즘 분류

• 다이나믹 프로그래밍

나의 답

생각의 흐름

1. 완전탐색

   조건 줘도 시간 초과

2. 다이나믹 프로그래밍

우선 완전탐색을 구현할 때는 s1의 길이만큼 순회하면서 각 index마다 s2의 길이만큼을 순회하고 해당 부분 문자열들의 LCS 길이를 구해야한다.

하지만 부분문제로 놓고 본다면 두가지 경우로 나눌 수 있다.

 

1. 현재 포인터가 가리키고 있는 변수 값이 다르다면

   현재의 LCS 길이는 2번째 그림(s1의 포인터 1증가)과 3번째 그림(s2의 포인터 1증가) 중에 큰 값과 같다.

   현재 index에서 A, C는 같지 않기 때문에 s1, s2의 LCS가 될 수 없기 때문이다.

 

2. 현재 포인터가 가리키고 있는 변수 값이 같다면

   현재의 LCS 길이는 s1과 s2의 포인터를 1씩 증가한 2번째 그림의 LCS 길이 값과 같다.

   현재 index에서 A, A가 같기 때문에 LCS가 될 수 있어서 길이는 1증가하며 이를 제외한 다음부분부터 검사하면 된다.

 

코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;
string s1, s2;
int memorize[1001][1001];

int LCS(int p1, int p2) {
    if (memorize[p1][p2] != -1)
        return memorize[p1][p2];
    if (p1 >= s1.length() || p2 >= s2.length())
        return 0;
    if (p1 == s1.length() - 1 && p2 == s2.length() - 1) {
        memorize[p1][p2] = (s1[p1] == s2[p2]);
        return memorize[p1][p2];
    }

    int max_result;
    if (s1[p1] == s2[p2])
        max_result = LCS(p1 + 1, p2 + 1)+1;
    else
        max_result = max(LCS(p1 + 1, p2), LCS(p1, p2 + 1));

    memorize[p1][p2] = max_result;
    return max_result;
}


int main() {
    getline(cin, s1);
    getline(cin, s2);

    fill(&memorize[0][0], &memorize[1000][1001], -1);

    int answer =  LCS(0,0);
    cout << answer;
}

 

테스트 케이스

1000개짜리

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

ACAYKP
CAKPAB

4

CBCBCBCB
BCBCBCA

6

APPLEY
APALPEY

5

PPPPP
PPPPPPPPPP

5

PPPPP
PPAPPAAP

5

ABCABC
CBACBA

3

ABCABC
ACBACB

4

BCDEFGHA
ACDEFGHB

6

1000개의 testcase를 돌려보았는데 생각보다 시간이 오래 걸리지 않아 바로 제출했다.

 

다른 답

#include <iostream>
#include <string>

using namespace std;

int dp[1001][1001];

int main() {
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);

    for (int j = 0; j < s2.length(); j++) {
        dp[0][j] = 0;
    }
    for (int i = 0; i < s1.length(); i++) {
        dp[i][0] = 0;
    }

    for (int i = 1; i <= s1.length(); i++) { // s1
        for (int j = 1; j <= s2.length(); j++) { // s2
            if (s1[i-1] != s2[j-1]) {
                dp[i][j] = dp[i-1][j] > dp[i][j - 1] ? dp[i-1][j] : dp[i][j - 1];
            }
            else {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
        }
    }
    cout << dp[s1.length()][s2.length()];
}

http://melonicedlatte.com/algorithm/2018/03/15/181550.html

사람들은 너무 똑똑하다 :>

여기서 위와 왼쪽 중에 큰 값을 택하는 부분은 본인의 코드에서 요소의 값이 다를 때 2가지 LCS 재귀함수를 호출한 부분이고, 대각선의 값 + 1을 한 부분은 요소의 값이 같을 때 다음 index의 LCS 값에 1을 더한 부분이다.

본인과 다른점

1. 완전탐색

   본인은 조건을 줘서 같은 요소가 나올 경우 2가지 경우는 실행 안해도 되게끔 만들었다. 하지만 위의 코드는 i를 s1의 길이만큼, j를 s2의 길이만큼 돌리면서 완전 탐색하였다.

2. 메모이제이션

   본인은 2차원 arr 메모이제이션을 사용하여 이미 구한 값일 경우 return 하는 방식으로 구현했다. 하지만 위의 코드는 메모이제이션 array를 직접 사용하는 형태로써 재귀함수를 탈 필요가 없어서 시간이 많이 단축되었다.

 

위쪽이 본인의 코드, 아래쪽이 위 링크의 코드이다.