백준 9252번 - LCS 2

문제

• 백준, 골드4, https://www.acmicpc.net/problem/9252
• 풀이 날짜: 2025.1.22., 2025.1.23
• 풀이 시간
  • 2025.1.22: 11:34~12:31, 20:31~21:09(38분, 포기),
  • 2025.1.23: 11:19~12:58(1시간 47분)
  • 총 3시간 22분
• 알고리즘 분류: 다이나믹 프로그래밍
• 사용 언어: C++

 

문제 해설

해당 문제는 LCS(Longest Common Subsequence, 최장 길이 부분 수열) 알고리즘을 통해 문제를 풀어야 한다.

LCS 알고리즘에 대해서는 전혀 몰랐는데, 이번 기회에 배우게 되어 정리해보았다.

(LCS에 대한 설명은 그림으로 정말 잘 정리해주신 분이 계셔서 공유하고자 합니다. 본 글은 해당 글을 참고하여 작성하였습니다: https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence)

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 

이때 최장 공통 문자열(Longest Common Substring)과 달리 문자가 떨어져 있어도 된다는 점에서 최장 공통 부분 수열(Longest Common Subsequence)은 좀 더 고려할 것이 많다.

부분수열은 연속된 값이 아닙니다. 때문에 현재의 문자를 비교하는 과정 이전의 최대 공통 부분수열은 계속해서 유지됩니다. '현재의 문자를 비교하는 과정' 이전의 과정이 바로 LCS[i - 1][j]와 LCS[i][j - 1]가 됩니다.

-위 블로그 참고

LCS 알고리즘은 2차원 배열을 이용하여 다이나믹 프로그래밍을 수행하는 알고리즘이다.

LCS는 다양한 경로가 존재할 수 있기 때문에, 그 모든 것을 기록해놓기보다 각 위치에서의 LCS 길이만을 기록해놓는 것이 좋다. 테이블을 모두 계산한 후 LCS를 계산할 때 규칙성을 이용하여 구성 문자를 역추적할 수 있기 때문이다.

예시

예시 문제로 주어진 ACAYKP와 CAPCAK이라는 문자열에 대해 각 문자별 LCS 값을 DP로 구해보자.

우선, CAPCAK의 첫 C에 대해 계산해보자면, ACAYKP는 두 번째의 C가 글자가 일치한다. 그러므로 LCS 길이를 1로 기록한다.

또, DP이기 때문에 해당 글자까지의 최대 길이를 기록할 것이다. 왜냐하면 연속된 부분 문자열만 고려하는 것이 아니라, 중간에 사용하지 않는 문자가 섞여 있어 불연속인 부분 수열을 구하는 문제이기 때문이다.

LCS	A	C	A	Y	K	P
C	0	1	1	1	1	1
A
P
C
A
K

다음 줄도 해보자.

A는 ACAYKP에서 첫 번째, 세 번째에 있다.

첫 번째 A에 대해서는 잘 채울 수 있다.

LCS	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	0	0	0	0
P
C
A
K

그런데 세 번째에 있는 A는 ‘CA’라는 공통 부분 문자열이 존재한다. 따라서 2가 되어야 하는데, 자신의 전 글자, 즉 C와 C가 일치하는 곳은 자신의 왼쪽 위에 존재한다. 그 점을 잘 보자.

LCS	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P
C
A
K

세 번째 줄에서만 마지막 P만 일치한다. 이때에도, 공통 문자열 CA가 앞에 있으므로 CAP가 되어 길이가 3이 되어야 한다. 이때에도, 자신의 좌상단 칸, 즉 (ROW - 1, COL - 1)의 lcs 값에 1을 더한 형태가 된다.

당연히 자기 문자보다 앞 문자에서 일치한 문자열에 새로운 문자 P를 추가하는 식이기 때문에 열(col)은 col - 1이 될 수밖에 없다.

또, 만약 6번째 자리보다 앞에 있는 문자 P가 일치한다 해도, 문자 하나는 최대 문자 하나와 일치할 수 있다. P와 PPP가 일치하여 최대 문자열이 PPP가 되어서는 안된다.

6번째 자리에서는 이번 문자 P에 대해 검사한 결과에 영향을 받으면 안된다. 그러므로, 직전(두번째 줄)에 검사했던 문자인 A를 기준으로 생각해야 하고, 따라서 조사하는 행(row)도 row - 1이 되어야 한다.

즉, 문자가 일치할 때 lcs[row][col] = (lcs[row - 1][col - 1] + 1)이다.

LCS	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C
A
K

이때 잘 보면, 3행 3열처럼 문자가 같지 않아도 같은 열의 값이 2여서 그 값을 물려받는 경우가 있다.

이렇게 해야, 이전 결과가 다음 줄에서 확인하기 쉽게 된다.

이런 식으로 모두 채우게 되면 다음과 같게 된다.

LCS	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

이때 가장 긴 부분 수열을 찾아야 하는데, 값은 6행 6열의 값이 가장 크지만 6행 6열의 문자는 P와 K로 같지 않다.

문자열이 같은 곳을 찾아야 하기 때문에 역추적을 위해 이동해주는 과정이 필요하다.

최장 공통 부분수열(Longest Common Subsequence) 찾기

1. LCS 배열의 가장 마지막 값에서 시작합니다. 결과값을 저장할 result 배열을 준비합니다.
2. LCS[i - 1][j]와 LCS[i][j - 1] 중 현재 값과 같은 값을 찾습니다.
   2.1 만약 같은 값이 있다면 해당 값으로 이동합니다.
   2.2 만약 같은 값이 없다면 result배열에 해당 문자를 넣고 LCS[i -1][j - 1]로 이동합니다.
3. 2번 과정을 반복하다가 0으로 이동하게 되면 종료합니다. result 배열의 역순이 LCS 입니다.

-[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

위 글에서 잘 정리해 놓았는데, 우리가 LCS를 계산할 때 문자가 같을 때 우측 하단(row + 1, col + 1)으로 이동하고, 문자가 다를 땐 위쪽(row - 1) 혹은 왼쪽(col - 1) 중 더 큰 값을 가져온다.

따라서 최대한 같은 값을 찾아서 이동해보다가 왼쪽, 위쪽 같으면 왼쪽 위 대각선으로 이동해보는 것이다.

그 과정을 정리하면 위와 같다는 점을 알 수 있다.

구현해보기

단순하게 구현하면 아래와 같이 구현할 수 있다.

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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    char str1[1001], str2[1001];

    cin >> str1;
    cin >> str2;

    int len1 = strlen(str1);
    int len2 = strlen(str2);

    // int lcs[1001][1001];
    vector<vector<int>> lcs(len2, vector<int>(len1, 0));

    for (int idx2 = 0; idx2 < len2; idx2++)
    {
        for (int idx1 = 0; idx1 < len1; idx1++)
        {
            // 같을 때
            if (str1[idx1] == str2[idx2])
            {
                if (idx1 > 0 && idx2 > 0)
                    lcs[idx2][idx1] = lcs[idx2-1][idx1-1] + 1;
                else
                    lcs[idx2][idx1] = 1;
            }
            // 다를 때: 위, 혹은 왼쪽 참조
            else
            {
                int upper = idx2 > 0 ? lcs[idx2-1][idx1] : 0;
                int left = idx1 > 0 ? lcs[idx2][idx1-1] : 0;
                lcs[idx2][idx1] = max(upper, left);
            }
        }
    }

    // 문자 찾기
    int idx2 = len2 - 1;
    int idx1 = len1 - 1;

    int lcs_cnt = idx1 >= 0 && idx2 >= 0 ? lcs[idx2][idx1] : 0;
    cout << lcs_cnt << '\n';
    if (lcs_cnt == 0)
    {
        cout << '\n';
        return 0;
    }

    vector<char> reversed;
    int upper, left;
    while (idx2 >= 0 && idx1 >= 0)
    {
        upper = idx2 > 0 ? lcs[idx2-1][idx1] : 0;
        left = idx1 > 0 ? lcs[idx2][idx1-1] : 0;

        if (str1[idx1] == str2[idx2])
        {
            reversed.push_back(str1[idx1]);
            idx1--;
            idx2--;
        }
        else if (upper > left)
            idx2--;
        else
            idx1--;
    }
    reverse(reversed.begin(), reversed.end());
    reversed.push_back('\0');

    cout << reversed.data() << "\n";

    return 0;
}

그러나 이렇게 구현하면 약간 구현이 어려운데, 왜냐하면 bound check 문제가 생기기 때문이다.

또한 알고리즘 명세와 달리 구현이 조금 잘못 되었는데, 여기에서는 문자가 같을 때 좌상단으로, 아니면 왼쪽 혹은 위쪽 중 같은 값으로 이동하는 식으로 구현하였다.

문자열을 뒤집을 땐 vector에 대해 reversed를 수행한 뒤 마지막에 null character를 붙여주었다. vector는 문자열을 처리하는 데에 적합하지 않으므로 이렇게 수동 처리가 필요하다.

GPT 구현 코드

풀던 도중 문제가 생겨 해결이 안되었을 때, GPT에게 도움받은 코드이다.

이 코드에서는 왼쪽, 위쪽에 하나의 열과 행을 더 넣어 Zero Padding을 넣었다.

이렇게 구현하면 boundary check가 필요 없어 훨씬 편리하다.

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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    char str1[1001], str2[1001];

    cin >> str1;
    cin >> str2;

    int len1 = strlen(str1);
    int len2 = strlen(str2);

    vector<vector<int>> lcs(len2 + 1, vector<int>(len1 + 1, 0));

    for (int idx2 = 1; idx2 <= len2; idx2++)
    {
        for (int idx1 = 1; idx1 <= len1; idx1++)
        {
            // 같을 때
            if (str1[idx1 - 1] == str2[idx2 - 1])
            {
                lcs[idx2][idx1] = lcs[idx2-1][idx1-1] + 1;
            }
            // 다를 때: 위, 혹은 왼쪽 참조
            else
            {
                lcs[idx2][idx1] = max(lcs[idx2-1][idx1], lcs[idx2][idx1-1]);
            }
        }
    }

    // 문자 찾기
    int idx2 = len2;
    int idx1 = len1;

    cout << lcs[idx2][idx1] << '\n';
    if (lcs[idx2][idx1] == 0)
        return 0;

    string reversed;

    while (idx1 > 0 && idx2 > 0)
    {
        if (str1[idx1 - 1] == str2[idx2 - 1])
        {
            reversed.push_back(str1[idx1-1]);
            idx1--;
            idx2--;
        }
        else if (lcs[idx2-1][idx1] > lcs[idx2][idx1-1])
            idx2--;
        else
            idx1--;
    }

    reverse(reversed.begin(), reversed.end());

    cout << reversed << "\n";

    return 0;
}

위 구현에서는 string을 사용하였는데, 이렇게 하면 reverse 함수를 사용하여 뒤집었을 때 추가 처리가 필요하지 않다는 장점이 있다.

그리고 해당 문제에서는 idx2, idx1보단 row, col과 같이 명세하는 게 더 직관적이다.

정확한 구현

알고리즘 명세를 잘 지켜 구현하면 다음과 같다.

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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    char str1[1001], str2[1001];

    cin >> str1;
    cin >> str2;

    int len1 = strlen(str1);
    int len2 = strlen(str2);

    vector<vector<int>> lcs(len2 + 1, vector<int>(len1 + 1, 0));

    for (int row = 1; row <= len2; row++)
    {
        for (int col = 1; col <= len1; col++)
        {
            // 같을 때
            if (str1[col - 1] == str2[row - 1])
            {
                lcs[row][col] = lcs[row-1][col-1] + 1;
            }
            // 다를 때: 위, 혹은 왼쪽 참조
            else
            {
                lcs[row][col] = max(lcs[row-1][col], lcs[row][col-1]);
            }
        }
    }

    // 문자 찾기
    int row = len2;
    int col = len1;

    cout << lcs[row][col] << '\n';
    if (lcs[row][col] == 0)
        return 0;

    string reversed;

    while (lcs[row][col] > 0)
    {
        if (lcs[row][col-1] == lcs[row][col])
            col--;
        else if (lcs[row-1][col] == lcs[row][col])
            row--;
        else
        {
            reversed.push_back(str1[col-1]);
            col--;
            row--;
        }
    }

    reverse(reversed.begin(), reversed.end());
    cout << reversed << "\n";

    return 0;
}

다만 메모리 사용량이 여전히 많은데, 이건 vector가 아니라 int 2차원 배열로 lcs dp를 저장하면 해결될 문제로 보인다.