최장 공통 부분 수열 (LCS; Longest common subsequence problem) - DP 해결법

 

 

 

최장 공통 부분 수열 (LCS; Longest common subsequence problem)

부분 수열(subsequence)은 시퀀스의 원소를 순서를 유지한 채 몇 개를 골라낸 것을 말한다.

최장 공통 부분 수열은 두 시퀀스(문자열 또는 배열)간 공통된 부분 수열 중 가장 긴 것을 찾아내는 문제이다.

 

예시) 문자열 `ABCBDAB`와 `BDCABA`의 LCS는 `BCBA`이다.

 

보통 LCS 문제를 해결하기 위해 주로 동적 계획법(DP;Dynamic Programming)을 사용한다.

이 글에서도 DP를 이용한 LCS 알고리즘을 설명하고자 한다.

 

 

LCS 길이 구하기

동작 원리

동적 계획법은 문제를 작은 부분 문제로 나누고 그 해를 이용해서 전체 문제를 해결하는 방식이다.

때문에 문제 정의와 점화식, 초기 조건을 설정해야 한다.

 

1. 문제 정의
   • 문자열(또는 배열) X의 길이를 n, Y의 길이를 m이라고 하자.
   • X와 Y의 LCS길이를 담는 배열 `L[n+1][m+1]`을 정의한다.
   • `L[i][j]`는 `X[0 ... i-1]`과 `Y[0 ... j-1]`의 LCS 길이를 나타낸다. 
2. 점화식
   • 만약 `X[i-1] == Y[j-1]`이면, `L[i][j] = L[i-1][j-1] + 1`
   • 그렇지 않으면 `L[i][j] = max(L[i-1][j], L[i][j-1])` : 길이가 가장 긴 것을 찾아야 하므로 max값을 저장.
3. 초기 조건
   • `L[0][j] = 0` (0 <= j <= m)
   • `L[i][0] = 0` (0 <= i <= n)

 

위의 내용을 기반으로 아래 예시를 살펴보자.

예시

예시 출처

Longest Common Subsequence (LCS) - GeeksforGeeks

 

문자열 `X = "AXYT"`와 `Y = "AYZX"`가 있다고 가정하자.

이 때 배열 `L`은 다음과 같다.

 

초기 배열 L

`i = 1` 일 때부터 탐색하여 보자.

`j = 1`일 때, X의 첫번째 문자`A` 와 Y의 첫번 째 문자 `A`가 같으므로 `L[1][1] = L[0][0] + 1`. 1을 저장.

`j = 2`일 때, X의 첫번째 문자`A` 와 Y의 두번 째 문자 `Y`가 다르므로 `L[1][2] = max(L[1][1], L[0][2])`. 1을 저장.

`j = 3`일 때, X의 첫번째 문자`A` 와 Y의 세번 째 문자 `Z`가 다르므로 `L[1][3] = max(L[1][2], L[0][3])`. 1을 저장.

`j = 4`일 때, X의 첫번째 문자`A` 와 Y의 네번 째 문자 `X`가 다르므로 `L[1][4] = max(L[1][3], L[0][4])`. 1을 저장.

 

위 과정을 통해 `i = 1`일 때 탐색을 마치면 아래와 같이 완성된다.

i=1일 때 탐색을 마친 후 배열 L

이제 `i = 2` 일 때를 탐색하여 보자.
`j = 1`일 때, X의 두번째 문자`X` 와 Y의 첫번 째 문자 `A`가 다르므로 `L[2][1] = max(L[2][0], L[1][1])`. 1을 저장.

`j = 2`일 때, X의 두번째 문자`X` 와 Y의 두번 째 문자 `Y`가 다르므로 `L[2][2] = max(L[2][1], L[1][2])`. 1을 저장.

`j = 3`일 때, X의 두번째 문자`X` 와 Y의 세번 째 문자 `Z`가 다르므로 `L[2][3] = max(L[2][2], L[1][3])`. 1을 저장.

`j = 4`일 때, X의 두번째 문자`X` 와 Y의 네번 째 문자 `X`가 같으므로 `L[2][4] = L[1][1] + 1`. 2를 저장.

 

위 과정을 통해 `i = 2`일 때 탐색을 마치면 아래와 같이 완성된다.

i=2일 때 탐색을 마친 후 배열 L

 

`i = 3`, `i = 4`일 때에도 앞의 과정과 똑같이 진행되므로 설명은 생략하겠다.

 

i=3일 때 탐색을 마친 후 배열 L

i=4일 때 탐색을 마친 후 배열 L

 모든 탐색을 마쳤을 때 최종 배열`L`에서 마지막 값인 `L[4][4]`는 LCS길이를 나타낸다.

 

 

 

LCS 문자열(배열) 찾기

동작 원리

LCS 길이를 찾는 방법을 알아보았다. 하지만 LCS길이가 아닌 LCS 자체를 찾아야 하는 문제도 있다.

그땐, 앞의 과정에서 길이를 저장하는 L배열과 이동 방향을 저장하는 direction배열을 함께 생성하여 문제를 해결한다.

 

1. 길이 저장을 위한 테이블 `L` 생성
   • 문자열 X의 길이가 n, Y의 길이가 m일 때 `L[n+1][m+1]`
2. 추적 테이블 `direction` 생성
   • 추가로 2차원 배열 `direction[n+1][m+1]`을 만든다. 이는 각 위치에서의 이동 방향을 저장하는 배열이다.
   • ↖︎ : 대각선 이동 (문자가 일치할 때)
   • ↑ : 위로 이동 (문자가 일치하지 않을 때 위에서 오는 값)
   • ← : 왼쪽으로 이동 (문자가 일치하지 않을 때 왼쪽에서 오는 값)
3. 테이블 채우기
   • DP 방법을 통해 `L`배열을 채우고, 각 단계에서의 방향을 `direction`배열에 기록한다.
4. LCS 추적
   • `direction`테이블을 이용하여 문자열을 역추적한다.
   • 마지막 위치`[n][m]`에서 시작하여 첫번째 위치`[0][0]`까지 이동하며 각 방향에 따라 문자를 추가한다.

 

 

예시

이미지를 통한 예시는 LCS 길이 찾기에서 했으므로, Java 코드 예시를 첨부하겠다.

위의 동작 원리를 그대로 구현한 코드이다.

public class LCS {
    public static String findLCS(String X, String Y) {
        int n = X.length();
        int m = Y.length();
        int[][] L = new int[n + 1][m + 1];
        int[][] direction = new int[n + 1][m + 1];

        // L 배열과 direction 배열 채우기
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (X.charAt(i - 1) == Y.charAt(j - 1)) {
                    L[i][j] = L[i - 1][j - 1] + 1;
                    direction[i][j] = 1; // ↖ 대각선 이동 : 1
                } else if (L[i - 1][j] >= L[i][j - 1]) {
                    L[i][j] = L[i - 1][j];
                    direction[i][j] = 2; // ↑ 위로 이동 : 2
                } else {
                    L[i][j] = L[i][j - 1];
                    direction[i][j] = 3; // ← 왼쪽으로 이동 : 3
                }
            }
        }

        // LCS 문자열 찾기
        StringBuilder lcs = new StringBuilder();
        int i = n, j = m; // [n][m]에서 부터 시작
        while (i > 0 && j > 0) { // [1][1] 까지 탐색
            if (direction[i][j] == 1) { // 대각선 이동
                lcs.append(X.charAt(i - 1)); // 해당 위치의 문자를 추가함.
                i--;
                j--;
            } else if (direction[i][j] == 2) { // 위로 이동
                i--;
            } else { // 왼쪽으로 이동
                j--;
            }
        }

        return lcs.reverse().toString(); // 뒤에서부터 탐색했으므로 reverse 필요
    }

    public static void main(String[] args) {
        String X = "AGGTAB";
        String Y = "GXTXAYB";
        System.out.println("LCS: " + findLCS(X, Y));
    }
}

 

 

 

 

* 참고

[백준/Gold V] LCS - 9251