최장 공통 부분 수열(LCS : Longest Common Subsequence)란?

최장 공통 부분순서란?

LCS란 Longest Common Subsequence의 약자로 최장 공통 부분 문자열이다. Subsequence는 부분 수열이라는 뜻으로 연속적이지 않아도 되는 부분 문자열이다. 한마디로 두 문자열을 비교할 때 공통적으로 나타나는 부분 순서들 중 가장 긴 것이다. 예를들어 "ABCBDAB"와 "BDCABA"의 LCS를 구하면 "BCBA"가 나오게 된다. 그리고 LCS는 최적화를 해야 하는 문제이기 때문에 동적계획법(DP)를 사용하여야 가장 효율적으로 구할 수 있다. 

 

 

그러면 간단하게 LCS를 구하는 예시를 보면서 어떤 느낌인지 생각해보자. 

 

 

문자열 "CAT"와 "CRAB"의 LCS를 구하여 보자. 위의 c[i][j]의 배열의 의미는 예를들어 c[1][2]라면 "CAT"에서는 C까지만(1개) "CRAB"에서는 CR까지(2개) 까지는 비교를 하겠다는 뜻이다. 그리고 구하는 방법을 정의해보려 한다.

예를들어 c[2][1] = 1, c[1][2] = 1을 봤을 때 c[2][2]에 들어가는 값을 어떻게 구해야할까? c[2][2]는 CAT에서 CA 까지, CRAB에서 CR까지 생각해서 각 문자열에서 2개까지만 생각해서 비교하는 것이다. 이때는 c[2][2]를 구하는 것이기 때문에 CAT에서 2번째 문자인 A, CRAB에서 2번째 문자인 R을 비교해서 두개가 같다면 c[1][1]에서 +1을 한 값을 넣어 주면 되고 위의 경우처럼 다르다면 c[2][1]와 c[1][2] 중에서 더 큰 값을 c[2][2]에 넣어주면 된다.

 

위의 사진을 보면서 다시 말하자면 if (i == 0 or j == 0) 이라면 겹치는 문자가 존재하지 않기 때문에 0이고 i, j > 0인데 위에서 말한 것처럼 x(i) = y(i)가 같다면 하나의 문자가 겹치는 것이기 때문에 c[i][j]는 c[i - 1][j - 1]에서 +1을 해주면 된다. 위의 표가 비어있다고 가정하고 표를 채워나가면 된다. 따라서 우리가 가장 원하는 LCS의 길이는 가장 오른쪽에 가장 아래에 있는 c[3][4] = 2인 부분이다. 

 

 

 

그러면 LCS 알고리즘에 분할정복 알고리즘을 사용하면 어떻게 될까?

public int LCS1(int m, int n) {
    if (m == 0 || n == 0) return 0;
    else if (X[m] == Y[n]) return LCS1(m - 1, n - 1) + 1;

    return Math.max(LCS1(m - 1, n ), LCS1(m, n - 1));
}

간단하게 문자열 X와 문자열 Y가 있다고 생각하고 LCS를 분할정복으로 구현했다고 간략한 코드로 생각해보자. 

이 때 LCS1(3, 4)를 호출하게 되면 LCS1(1, 1)을 10번 중복호출하게 된다. 이렇기 때문에 LCS 알고리즘은 분할정복이 아닌 동적계획법으로 풀어야 한다.

 

public class Test {

    public int LCS1(int m, int n) {
        int[][] C = new int[m + 1][n + 1];
        
        for (int i = 0; i <= m; ++i) {
            C[i][0] = 0;
        }
        for (int j = 0; j < n; ++j) {
            C[0][j] = 0;
        }
        
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (X[i] == Y[j]) {
                    C[i][j] = C[i - 1][j - 1] + 1;
                }
                else {
                    C[i][j] = Math.max(C[i - 1][j], C[i][j - 1]);
                }
            }
        }
        
        return C[m][n];
    }
}

위와 같이 반복문을 이용해서 동적프로그래밍을 구현해야 한다. 이러면 시간 복잡도는 O(mn)이 된다.

 

예를들어 X = "AAACCCTGAGTT" 이고 Y="CACCCTAAGGT" 의 문자열이 있다고 생각해보자.

 

위에서 설명한대로 표를 작성하면 위와 같이 작성이 된다. 따라서 c[12][12]를 보면 7이기 때문에 LCS의 길이는 7이라는 것을 알 수 있다. 그러면 LCS가 무엇인지를 찾고 싶을 때는 어떻게 해야할까? 역추적(backtrack)을 이용하면 된다.

위의 하늘색으로 색칠 된 것을 보면 C[12][12]에서 내가 어느 길을 통해서 왔는지 역추적을 해서 출발지점을 찾아가는 것이다. 따라서 백트래킹을 이용하면 하늘색이 칠해진 경로를 찾을 수 있다. 위에서 말했던 대로 X의 문자와 Y의 문자가 같다면 c[i][j] = c[i - 1][j - 1] + 1을 하면 된다고 했기 때문에 그렇게 1이 증가하는 부분만 찾으면 되기 때문에 그 문자를 연결해서 문자열을 만들면 그게 LCS가 된다. 

 

public class Test {

    public static String traceBack(int C[][], String X, String Y, int i, int j) {
        if (i == 0 || j == 0) return "";
        else if (X.charAt(i) == Y.charAt(j)) {
            return traceBack(C, X, Y, i - 1, j - 1) + X.charAt(i);
        }

        if (C[i][j - 1] >= C[i - 1][j]) {
            return traceBack(C, X, Y, i, j - 1);
        }

        return traceBack(C, X, Y, i - 1, j);
    }
}

최장 부분순서의 길이는 유일하지만(unique), 그 길이를 갖는 최장 부분순서는 여러 개 존재할 수 있다.

 

 

 

 

최장 부분순서 문제의 활용 사례

• DNA 시퀀스의 염기(AGGT)서열 비교를 통한 유사성 판정
• 유닉스 diff utility : 라인 기반의 파일비교(file comparison) 유틸리티