Algorithm

[Algorithm] LCS(최장 공통 부분 수열)

박땅콩 2022. 9. 10.

728x90

LCS(최장 공통 부분 수열)에 대해서 공부하고 정리한 내용입니다.

잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적 부탁드립니다!

LCS(최장 공통 부분 수열)이란?

'두 문자열을 비교할 때 공통적으로 나타나는 부분 문자열 중 가장 긴 것'

이해를 위해 예를 들어 "ACAYKP" 문자열과 "CAPCAK" 문자열이 주어졌다면,

ACAYKP

CAPCAK

두 문자열을 비교할 때 공통적으로 나타나는 부분 문자들 중 가장 긴 것은 ACAK이고 길이는 4입니다.

LCS(최장 공통 부분 수열) 동작 과정(LCS 길이 구하기)

위에서 예를 든 "ACAYKP"와 CAPCAK" 문자열의 LCS 길이를 구한다면 어떻게 구해야할지 생각해봅시다.

↪ LCS는 다이나믹 프로그래밍을 이용하여 풀 수 있는데, 2차원 배열을 이용합니다.

그렇다면 2차원 배열은 아래와 같이 정의합니다.

ACAYKP 문자열을 A문자열, CAPCAK 문자열을 B문자열이라고 한다면

dp[i][j] = A문자열의 i번째 문자열과 B문자열의 j번째 문자열까지 공통적으로 나타나는 부분 문자열 중 가장 긴 것

알고리즘 구현시 편의상 LCS 테이블(2차원 배열)의 첫번째 행과 열은 모두 0으로 초기화 해줍니다.

그렇다면 이제 LCS 테이블(2차원 배열)을 채워봅시다.

아래와 같이 테이블을 채울 수 있는데 1이 도대체 무엇일까요?

A와 C를 비교했을 때의 LCS는 0이고

AC와 C를 비교했을 때의 LCS는 1

ACA와 C를 비교했을 때의 LCS는 1

ACAY와 C를 비교했을 때의 LCS는 1

ACAYK와 C를 비교했을 때의 LCS는 1

ACAYKP와 C를 비교했을 때의 LCS는 1

즉, AC와 C를 비교했을 때 공통적으로 나타나는 부분 문자열이 1개가 있다는 뜻입니다.

그렇다면 계속 LCS 테이블을 채워봅시다.

ACAYKP와 CA를 비교하면 공통적으로 나타나는 부분 문자열은 2개입니다.

(ACAYKP CA)

테이블을 채우다보니 LCS 테이블이 어떻게 채워지는지 더 정확히 알기 위해

테이블을 채우는 기준을 알아보려고합니다.

초록색으로 칠해진 부분을 보면

AC와 C를 비교했을 때 공통적인 부분 문자열이 C이기 때문에 1을 채웠습니다.

그런데 ACA와 C에서는 마지막 문자가 다른데 1로 채워져있습니다.

1로 채워진 이유는 이전 AC와 C를 비교했을 때 채워진 값인 1이 채워졌음을 알 수 있습니다.

이제 분홍색으로 칠해진 부분을 보면

ACA와 CA를 비교했을 때 공통적인 부분 문자열이 CA이기 때문에 2를 채웠습니다.

그렇다면 ACA와 CAP를 비교했을 때 마지막 문자가 다르지만 2로 채워져있습니다.

2로 채워진 이유는 이전 ACA와 CA를 비교했을 때 채워진 값인 2가 채워졌음을 알 수 있습니다.

이로서 서로 다른 문자열일 때 왼쪽과 위쪽 중 가장 큰 값을 가져오고 있음을 알 수 있습니다.

그렇다면 서로 같은 문자열일 때는 어떻게 채워지는 것일까요?

옥색(?)으로 칠해진 부분을 보면,

ACAYKP와 CAP를 비교했을 때 공통적인 부분이 CAP이기 때문에 3으로 채워지게 됩니다.

왼쪽에서 위인 2에서 1이 더해져 3으로 채워지게 됩니다.

ACAYK와 CA를 비교하고 ACAYKP와 CAP를 비교하는 것이 정확한 의미가 되기 때문에

왼쪽 위의 값에 + 1을 한 값으로 채워지게 됩니다.

최종적으로 LCS 테이블을 완성하면 아래와 같습니다.

LCS(최장 공통 부분 수열) 구현(C++)

아래의 코드는 백준 9251번 문제인 LCS를 기반으로 작성했습니다.

#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001];
string str1, str2;

void input() {
    str1 = " ";
    str2 = " ";
    string temp1, temp2;
    cin >> temp1 >> temp2;
    str1 += temp1;
    str2 += temp2;
}

void dpinitialize() {
    // dp 배열 0으로 초기화
    for(int i = 0; i < 1001; ++i) {
        fill(dp[i], dp[i] + 1001, 0);
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    dpinitialize();
    int str1len = str1.length();
    int str2len = str2.length();

    for(int i = 1; i < str1len; ++i) {
        for(int j = 1; j < str2len; ++j) {
            if(str1[i] == str2[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    cout << dp[str1len - 1][str2len - 1];
    return 0;
}

LCS(최장 공통 부분 수열) 문자열 찾기

LCS의 실제 문자열을 찾으려고 합니다.

빨간색으로 표시된 ACAK 문자열을 찾으려 하는데, 어떻게 해야할까요?

여기서 백트래킹이 필요합니다.

뒤에서부터 찾기 때문에 가장 끝자리부터 시작합니다.

1. 자신과 같은 숫자가 있는 곳까지 따라갑니다.

2. 왼쪽, 위쪽에 같은 수가 없다면 대각선 방향 값이 현재 값의 -1 인지 확인 하고 이동합니다.

1 ~ 2를 계속 반복하다가, 0을 만나게 되면 종료합니다.

LCS(최장 공통 부분 수열) 문자열 찾기 구현(C++)

백준 9252번 문제인 LCS 2를 기반으로 작성했습니다.

#include <bits/stdc++.h>
using namespace std;
int dp[4001][4001];

void dpinitialize() {
    for(int i = 0; i < 4001; ++i) {
        fill(dp[i], dp[i] + 4001, 0);
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    dpinitialize();
    string str1 = " ";
    string str2 = " ";
    string temp1, temp2;
    cin >> temp1 >> temp2;
    str1 += temp1;
    str2 += temp2;
    
    int str1len = str1.length();
    int str2len = str2.length();
    for(int i = 1; i < str1len; ++i) {
        for(int j = 1; j < str2len; ++j) {
            if(str1[i] == str2[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    // LCS 길이 출력
    cout << dp[str1len - 1][str2len - 1] << '\n';

    int i = str1len - 1;
    int j = str2len - 1;
    stack<int> st; // stack 활용 FILO 첫번째 넣은 것이 나중에 나옴
    while(dp[i][j] != 0) {
       if(dp[i][j] == dp[i][j - 1])  {
            j -= 1;
       } else if(dp[i][j] == dp[i - 1][j]) {
            i -= 1;
       } else if(dp[i][j] - 1 == dp[i - 1][j - 1]) {
            st.push(i);
            i -= 1;
            j -= 1;
       } else {
            // nothing
       }
    }
    
    while(!st.empty()) {
        cout << str1[st.top()];
        st.pop();
    }
    return 0;
}