LCS 알고리즘

LCS는 최장 공통 부분 수열(Longest Common Subsequence)을 뜻하나, 부분 수열이 연속되어야 한다는 조건이 추가된 최장 공통 문자열(Longest Common Substring)을 뜻하기도 한다.

LCS에 대한 그림을 통한 풀이는 여기서 확인할 수 있다.

문제

문제는 메뉴 조작을 나타내는 수열 두 개 사이의 최장 공통 문자열을 찾는 문제이다. 문제에서의 공통 문자열(수열)은 수열 내에서 연속되어야 한다. 처음 연속되어야 한다는 조건을 한번에 찾지 못해 틀린 바 주의가 필요했다.

코드

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

using namespace std;

int N, M, K, temp;
vector<int> one, two;
int D[3001][3001];
int answer;

int main(int argc, char** argv)
{
    cin >> N >> M >> K;

    one.push_back(0);
    two.push_back(0);
    for (int n = 0; n < N; n++) {
        cin >> temp;
        one.push_back(temp);
    }
    for (int m = 0; m < M; m++) {
        cin >> temp;
        two.push_back(temp);
    }

    for (int m = 1; m <= M; m++) {
        for (int n = 1; n <= N; n++) {
            
            if (one[n] == two[m]) {
                D[n][m] = max(D[n][m], D[n - 1][m - 1] + 1);
            }

            if (D[n][m] > answer)
                answer = D[n][m];
        }
    }

    cout << answer;
    return 0;
}

연속되어야 한다는 조건이 없을 때(Longest Common Subsequence) 코드는 아래와 같다.

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

using namespace std;

int N, M, K, temp;
vector<int> one, two;
int D[3001][3001];
int answer;

int main(int argc, char** argv)
{
    cin >> N >> M >> K;

    one.push_back(0);
    two.push_back(0);
    for (int n = 0; n < N; n++) {
        cin >> temp;
        one.push_back(temp);
    }
    for (int m = 0; m < M; m++) {
        cin >> temp;
        two.push_back(temp);
    }

    for (int m = 1; m <= M; m++) {
        for (int n = 1; n <= N; n++) {
            // 👇[차이점]
            D[n][m] = D[n - 1][m];
            D[n][m] = max(D[n][m], D[n][m - 1]);

            if (one[n] == two[m]) {
                D[n][m] = max(D[n][m], D[n - 1][m - 1] + 1);
            }

            if (D[n][m] > answer)
                answer = D[n][m];
        }
    }

    cout << answer;
    return 0;
}