[DP]LCS

LCS

Longest Common Subsequence 또는 최장 공통 부분 수열, 문자열

최장 공통 부분 수열은 주어진 수열 모두의 부분 수열이 되는 수열 중 가장 긴 수열을 찾는 문제이다.

---

A = {1,2,3,4,5,6}

B = {1,3,5,4,3,6}

두 수열에 관한 최장 공통 부분 수열은 {1,3,4,6}이며 길이는 4이다.

주의! 두 수열은 다른 길이를 가질 수 있다.

문제를 푸는 핵심은 각 수열을 차례대로 검사하면서 같은 문자일 때 이를 공통 부분 수열로 넣고, 이전 공통 부분 수열들과 비교해서 나은 것으로 선택하는 것이다.

이는 다음과 같은 점화식을 가진다.

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

LCS[i][j] 가 0인 경우는 수열이 빈 String인 경우, 즉 초기 값

LCS[i][j]가 LCS[i-1][j-1]+1인 경우, A와 B에 같은 문자가 있어서 수열의 개수가 증가.

LCS[i][j]가 Max(LCS[i-1][j], LCS[i][j-1])인 경우, 현재 수열과 이전 수열들을 비교해 나은 것으로 선택.

이렇게 A 수열과 B 수열을 차례대로 비교하면서 공통 부분 수열을 선택하면 다음과 같이 결과가 나오게 된다.

	0	A	B	C	A	H
0	0	0	0	0	0	0
G	0	0	0	0	0	0
B	0	0	1	1	1	1
H	0	0	1	1	1	2
C	0	0	1	2	2	2
A	0	1	1	2	3	3

결과적으로 마지막 LCS[A.length][B.length]에 가장 긴 배열의 개수가 저장된다.

String A = br.readLine();
String B = br.readLine();

int[][] LCS = new int[A.length() + 1][B.length() + 1]; // 수열 개수 저장

for (int i = 0; i <= A.length(); i++) {
    for (int j = 0; j <= B.length(); j++) {
        if (i == 0 || j == 0) {
            LCS[i][j] = 0;
        } else {
            if (A.charAt(i - 1) == B.charAt(j - 1)) {
                LCS[i][j] = LCS[i - 1][j - 1] + 1;
            } else {
                LCS[i][j] = Math.max(LCS[i - 1][j], LCS[i][j - 1]);
            }
        }
    }
}

최장 공통 수열 찾아가기

두 수열의 공통 개수를 위와 같이 찾을 수 있다. 하지만, 간혹 공통 수열의 원소를 찾아야 하는 경우가 있다. 처음에는 서로 값이 같을 때 업데이트를 통해서 가능한 경우의 수를 찾는 방식으로 생각을 했는데, 더 쉬운 방식이 있었다. 위에서 본 테이블을 통해서 보면 된다.

	0	A	B	C	A	H
0	0	0	0	0	0	0
G	0	0	0	0	0	0
B	0	0	1	1	1	1
H	0	0	1	1	1	2
C	0	0	1	2	2	2
A	0	1	1	2	3	3

마지막에 위치한 테이블은 어디에서 파생되었을까? 바로 옆인 A,A 위치이다. LCS를 업데이트를 할때 왼쪽과 위에서 최대값을 찾거나, 대각선 방향에서 +1 을 하는 방식으로 진행된다. 최장 공통 수열에 추가되는 조건은 서로 값이 같을 때 즉, 대각선 방향에서 +1 하는 방식이다.

그러면 다음과 같이 생각할 수 있다.

현재 값과 왼쪽, 위 값을 비교한다.

= 왼쪽, 위 값이 현재 값과 같다. -> 왼쪽, 위 한쪽 방향으로 탐색
= 왼쪽, 위 값이 현재 값보다 1 정도 작다 -> 대각선으로 이동 (현재 위치가 추가된 수열 -> 업데이트)
= 왼쪽, 위 값이 같지 않고, 한쪽이 크거나 현재값과 같다. (해당 방향으로 이동)

이렇게 찾으면 LCS의 역순이기 때문에 실제로 이를 다시 reverse 해서 출력하면 된다.

이 방식을 코드로 나타내면… DP 방식이라는 걸 알 수 있을 것이다.

public static StringBuilder sb = new StringBuilder();
public static String A, B;

public static void FindLCS(int[][] lcs, int x, int y) {
    if (x == 0 || y == 0) {
        return;
    }
    if (lcs[x - 1][y] == lcs[x][y - 1]) {
        if (lcs[x][y] == lcs[x - 1][y]) {
            FindLCS(lcs, x - 1, y);
        } else if (lcs[x][y] - 1 == lcs[x - 1][y]) {
            sb.append(A.charAt(x - 1));
            FindLCS(lcs, x - 1, y - 1);
        }
    } else {
        if (lcs[x - 1][y] > lcs[x][y - 1]) {
            FindLCS(lcs, x - 1, y);
        } else {
            FindLCS(lcs, x, y - 1);
        }
    }
}

...
이후 System.out.println(sb.reverse()); 로 출력했다.

추천문제 9251번: LCS