LCS(최장 공통 부분 수열) 알고리즘

알고리즘

LCS(최장 공통 부분 수열) 알고리즘 :: 마이구미

mygumi 2017. 2. 17. 15:09

이번 글은 LCS(Longest Common Subsequence) 알고리즘은 다뤄본다.

최장 공통 부분 수열(LCS)은 LIS 최장 증가 부분 수열과 비슷하게 생각하면 된다.

LCS 또한 LIS와 같이 DP(동적 계획법)을 기반으로 한다.

LCS 알고리즘을 통해 두개의 문자열을 비교하여 공통 부분 수열의 길이를 구할 수 있다.

주의할 점은 LCS는 Longest Common Substring과 Longest Common Subsequence이 존재한다.

공통 부분 문자열(Longest Common Substring), 공통 부분 수열(Longest Common Subsequence)이라고 말할 수 있다.

2개는 다른 의미를 가지고 있기 때문에 구분해야한다.

차이점은 연속 여부이다.

최장 공통 문자열의 길이는 3, 최장 공통 부분 수열의 길이는 5가 나오게 된다.

LCS 알고리즘의 접근법을 알아보자.

먼저 Longest Common Substring을 보자.

${\mathit {LCSuff}}(S_{{1..p}},T_{{1..q}})={\begin{cases}{\mathit {LCSuff}}(S_{{1..p-1}},T_{{1..q-1}})+1&{\mathrm {if}}\;S[p]=T[q]\\0&{\mathrm {otherwise}}.\end{cases}}$

크게 설명할 게 없을만큼 간단하다.

코드를 보며 살펴보자.

for (int i = 1; i <= A.length; i++) {

    for (int j = 1; j <= B.length; j++) {

        if (A[i - 1] == B[j - 1]) {
            LCS[i][j] = LCS[i - 1][j - 1] + 1;

            if (ans < LCS[i][j]) {
                ans = LCS[i][j];
            }
        }

    }

}

String A = "ABCD"
String B = "AEBD"

LCS("ABCD","AEBD") = 1 + LCS("ABC","AEB")

LCS("ABC", "AEB") = 0;

D문자가 같을 경우 이전 문자에 대해 최장 공통 부분 문자열의 길이 + 1을 한다.

비교 문자가 다를 경우 연속적인 문자열을 구하기 때문에 무시하면 된다.

Longest Common Subsequence를 보자.

X,Y는 비교할 각 문자열이고, i, j는 문자열의 각 인덱스에 해당하는 문자이다.

집합을 보면 3가지 경우를 볼 수 있다.

첫번째는 구현에 있어 편의를 위한 것이다.

두번째는 X, Y의 문자를 비교하여 같은 경우를 뜻한다.

String A = "ABCD"
String B = "AEBD"

LCS("ABCD","AEBD") = 1 + LCS("ABC","AEB")

(ABCD와 AEBD의 길이) = (ABC, AEB를 비교했을 때의 길이 + 1)이 된다.

세번째는 X, Y의 비교 문자가 다를 경우를 뜻한다.

LCS("ABC","AEB") = MAX(LCS("AB","AEB"), LCS("ABC", "AE")

(AB, AEB 길이)와 (ABC,AE 길이) 중 큰 값을 (ABC, AEB 길이) 에 넣어준다.

세가지를 코드와 그림으로 나타내면 아래와 같다.

for(int i=1;i<=A.length;i++) {

    for(int j=1;j<=B.length;j++) {

        if (A[i-1] == B[j-1]) {
            LCS[i][j] = LCS[i-1][j-1] + 1;
        } else {
            LCS[i][j] = Math.max(LCS[i][j-1], LCS[i-1][j]);
        }

    }

}

두 문자열의 각 문자를 비교하는 것처럼 보이지만 위 그림을 보다시피 그렇지 않다.

예를 들어 A문자열의 B와 B문자열의 E를 비교한다고 가정하자.

그렇다면 단순히 B와 E를 비교하는 것이 아닌 A문자열 중 AB, B문자열 중 AE를 비교하는 것이다.

결과적으로 LCS 배열 마지막에는 LCS의 길이를 볼 수 있다.

그렇다면, 길이가 아닌 LCS에 해당하는 부분 수열을 알고 싶다면 어떻게 해야할까?

그림을 보면 쉽게 이해를 할 수 있다.

길이가 변하는 시점이 공통 부분인 것은 이미 알고 있다.

그렇기에 그림와 같이 대각선인 시점을 체크하면 된다.

for (int i = 1; i <= A.length; i++) {

    for (int j = 1; j <= B.length; j++) {

        if (A[i - 1] == B[j - 1]) {
            LCS[i][j] = LCS[i - 1][j - 1] + 1;

            solution[i][j] = "diagonal";
        } else {
            LCS[i][j] = Math.max(LCS[i][j - 1], LCS[i - 1][j]);

            if (LCS[i][j] == LCS[i - 1][j]) {
                solution[i][j] = "top";
            } else {
                solution[i][j] = "left";
            }
        }

    }

}

int a = A.length;
int b = B.length;

while(solution[a][b] != null) {

    if (solution[a][b] == "diagonal") {
        sb.append(A[a-1]);

        a--;
        b--;
    } else if (solution[a][b] == "top") {
        a--;
    } else if (solution[a][b] == "left") {
        b--;
    }

}

sb.reverse.toString(); // 최장 공통 부분 수열 리스트

이제껏 2개의 문자열을 비교하였다.

3개의 문자열을 통해 LCS를 구해야한다면 동일하다.

2차원 배열에서 3차원 배열로 바꿔주는 작업만 하면 된다.

자세한 건 아래 링크를 참고하자.

아래 관련 문제들과 문제들의 전체 소스가 있는 Github URL을 참고하길바란다.

참고 URL

http://algorithms.tutorialhorizon.com/dynamic-programming-longest-common-subsequence/

Longest Common Substring 문제 5582번 "공통 부분 문자열"

https://www.acmicpc.net/problem/5582

https://github.com/hotehrud/acmicpc/blob/master/LCS/5582.java

Longest Common Subsequence 문제 9251번 "LCS"

https://www.acmicpc.net/problem/9251