[Algorithm] Dynamic Programming - Longest Common Sequence(LCS)

1. 개요 - LCS가 뭘까?

LCS(Longest Common Subsequence) 알고리즘은 공통부분 문자열 중 가장 길이가 긴 문자열을 찾는 알고리즘을 뜻한다.

여기서 Subsequnce와 Substring의 차이가 있는데 Substring은 연속된 부분 문자열이고, Subsequence는 연속되지 않는 부분 문자열이다.

String	Longest Common SubString	LongestCommon Subsequence
LEEJINHO	LEEJ	LEEJHO
LEEJAEHONG

같은 길이의 다른 해가 있을 수 있다.

String	Longest Common SubString
aaabbbccc	"aaa" or "ccc"
aaadefccc

String	Longest Common Subsequence
abcdefg	"aef" or "acd"
aefacd

막상 직접 만드려니 어렵네요;; 틀렸다면 댓글 부탁드립니다 ㅜ

---

2. LCS의 길이 구하기

LCS 알고리즘은 DP(Dynamic Programming)이므로 특정 범위까지의 LCS을 구하고 다음 범위의 LCS를 구할 때 이전에 구해 둔 값을 이용하여 문제를 해결한다.

점화식

점화식만 보면 이해가 잘 안 된다. 예시를 들어 설명하는 게 더 이해하기 쉬우니 예시를 들어보자.

문자열 "ABCBDAB"와 "ADCABA"를 표를 이용해서 비교해보자. 

1) 0부터

	0	A	B	C	B	D	A	B
0	0	0	0	0	0	0	0	0

0을 추가하는 이유는 공통 부분이 없다면 LCS가 길이가 0이기 때문이다.

 

2) B와 비교 

	0	A	B	C	B	D	A	B
0	0	0	0	0	0	0	0	0
A	0	1	1	1	1	1	1	1

표를 보는 방법은 열의 {A}와 행의 {A}, {AB}, {ABC}, {ABCB}.. 의 마지막 element를 비교하는 것이다.

점화식을 따라해보자.

• 우선 {A}와 {A}를 비교해보면 마지막 element는 "A"로 같다. 그러므로 두 문자열에서 "A"를 뺀 {}(empty)와, {}(empty)의 LCS길이인 0에 +1을 하여 표기한다. (점화식 2번 case)
• 그다음, {A}와 {AB}를 비교해 보자. 마지막 element는 "A"와 "B"로 다르다. 그러므로 {}(empty)와 {AB}의 LCS길이인 0과 {A}와 {A}의 LCS길이인 1중 더 큰 값인 1을 표기한다. (점화식 3번 case)
• 이번엔 {A}와 {ABC}를 비교해보자. 마지막 element는 "A"와 "C"로 다르다. 그러므로 {}(empty)와 {ABC}의 LCS길이인 0과 {A}와 {AB}의 LCS길이인 1중 더 큰 값인 1을 표기한다. (역시 점화식 3번 case)
• 계속 반복하면서 표기하다가 다시 {A}와 {ABCBDA}를 비교해보자. 마지막 element는 "A"로 같다. 그러면 두 문자열 마지막 element "A"가 없는 {}(empty)와 {ABCBD}의 LCS길이인 0에 +1을 하여 표기한다. (점화식 2번 case)

위에서 한 표기들을 DP측면에서 살펴보면

• {A}와 {A}의 LCS길이를 구하기 위해서 이전에 구해놓은 {}(empty)와 {}(empty)의 LCS길이인 0을 이용했다. 즉, 이전의 LCS길이값을 이용해서 현재 LCS길이값을 구할 수 있었다.
• {A}와 {AB}의 LCS길이는 공통부분이 "A"이기 때문에 1이다. 이것은 이전에 구해놓은 {}(empty)와 {AB}의 LCS길이, 그리고 {A}와 {A}의 LCS길이를 이용해서 구할 수 있었다. 

 

3) 몇 번 더 반복해보자

	0	A	B	C	B	D	A	B
0	0	0	0	0	0	0	0	0
A	0	1	1	1	1	1	1	1
D	0	1	1	1	1	2	2	2
C	0	1	1	2	2	2	2	2
A	0	1	1	2	2	2	3	3
B	0	1	2	2	3	3	3	4
A	0	1	2	2	3	3	4	4

역시 점화식을 따라 해보자

• {ADCA}와 {ABCBDA}를 비교해보면, 마지막 element는 "A"로 같다. 그러므로 "A"가 없는 {ADC}와 {ABCBD}의 LCS길이인 2에 +1을 하여 표기한다 (점화식 2번 case)
• {ABCBDAB}와 {ADCABA}를 비교해보자. 마지막 element는 "B"와 "A"로 서로 다르다. 그러므로 {ABCBDAB}와 {ADCAB}의 LCS길이 4와 {ABCBDA}와 {ADCABA}의 LCS길이 4 중 더 큰 값을 표기한다. (점화식 3번 case)

이것도 DP관점에서 보면

• {ADCA}와 {ABCBDA}의 LCS길이를 구하기 위해 이전에 구해놓은 {ADC}와 {ABCBD}의 LCS길이를 이용한다.
• {ABCBDAB}와 {ADCABA}의 LCS길이를 구하기 위해 이전에 구해놓은 {ABCBDAB} 와 {ADCAB}, {ABCBDA}와 {ADCABA} LCS길이를 이용한다.

 

따라서 점화식을 해석하면

• 문자열 X나 문자열 Y의 index가 0일 경우 0
• 문자열의 마지막 element를 비교하여 같을 경우 왼쪽 위 대각선의 값 +1을 표기
• 문자열의 마지막 element를 비교하여 다를 경우 왼쪽 값과 위쪽 값 중 더 큰 값을 표기

 

코드로는 어떻게 구현할까?

package algorithm.lcs;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

import org.junit.jupiter.api.Test;

public class LongestCommonSubsequence {

  @Test
  public void testLcsLength() {
    assertThat(lcsLength("ADCABA", "ABCBDAB"), is(4));
  }

  public int lcsLength(String x, String y) {
    int maxLength = 0;

    x = "0" + x;
    y = "0" + y;
    int[][] lcsTable = new int[x.length()][y.length()];

    for (int i = 1; i < x.length(); i++) {
      for (int j = 1; j < y.length(); j++) {
        if (x.charAt(i) == y.charAt(j)) {
          lcsTable[i][j] = lcsTable[i - 1][j - 1] + 1;
          maxLength = lcsTable[i][j];
        } else {
          lcsTable[i][j] = Math.max(lcsTable[i][j - 1], lcsTable[i - 1][j]);
        }
      }
    }
    return maxLength;
  }
}

자바의 경우 int 배열을 선언하면 0으로 초기화되기 때문에 "0"에 해당하는 0 값을 따로 넣어주지 않았다.

---

3. LCS 구하기

LCS 길이를 표기해 나갔던 표를 역추적하여 LCS를 구할 수 있다.

LCS 길이 점화식을 다시 생각해보면

문자열 마지막 element가 같을 경우 왼쪽 위 대각선 값 + 1

문자열 마지막 element가 다를 경우 왼쪽이나 위쪽 값 중 더 큰 값

이를 이용해서 표를 역추적하면 실제 LCS를 구할 수 있다.

역시 이해가 잘 안 되니까 표를 보자.

발퀄 ㅈㅅ..

우선 표의 끝(오른쪽 아래)에서 시작하자. ({6,8}("A", "B"))

시작 위치에서 위쪽, 대각선(왼쪽 위), 왼쪽 값을 비교하면 대각선 값 보다 크고 왼쪽, 위쪽 값과 같다. 이때 왼쪽 or 위쪽으로 이동할 수 있는데 위쪽을 선택

• 단, 왼쪽이나 위쪽을 선택했을 때, 선택한 방향으로만 이동해야 한다.

이동한 위치 ({5,8} ("B", "B"))에서 element 값이 같다. 그리고 왼쪽, 위쪽, 대각선 값보다 크다. 그러므로 대각선으로 이동한다. 이때 현재 위치 값 "B"를 기록해둔다.

• Output : B

이동한 위치 ({4,7}, ("A", "A"))에서 element 값이 "A"로 같다. 역시 왼쪽, 위쪽, 대각선 값보다 크기 때문에 "A"를 기록하고 대각선으로 이동한다.

• Output : AB

이동한 위치 ({3,6}, ("C", "D")}에서 element 값이 다르다. 그리고 대각선 값보다는 크고, 왼쪽 위쪽 값과는 같다. 처음에 이럴 경우 위쪽으로 이동하는 것을 선택했기 때문에 위쪽으로 이동한다.

이동한 위치 ({2,6}, ("D", "D")}에서 element 값이 "D"로 같다. 역시 왼쪽, 위쪽, 대각선 값보다 크기 때문에 "D"를 기록하고 대각선으로 이동한다.

• Output : DAB

이동한 위치 ({1,5}, ("A", "B")}에서 element 값이 다르다. 대각선과 위쪽 값보다는 크고, 왼쪽 값과는 같다. 그러므로 왼쪽으로 이동한다.

왼쪽으로 계속 이동하다가 ({1,1}, ("A", "A"))에서 element 값이 "A"로 같다. "A"를 기록하고 대각선으로 이동한다.

• Output : ADAB

이동한 위치가 {0,0}이므로 종료, 그러므로 LCS는 "ADAB"이다.

 

왼쪽과 위쪽 모두 같을 때 왼쪽을 선택한 경우도 있다.

이럴 경우 LCS는 "ACBA"이다.

즉, 같은 LCS 길이에 다른 LCS값이 나올 수 있다.

 

소스 코드

package algorithm.lcs;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

import org.junit.jupiter.api.Test;

public class LongestCommonSubsequence {

  @Test
  public void testLcsLength() {
    assertThat(lcs("ADCABA", "ABCBDAB"), is("ADAB"));
  }

  public String lcs(String x, String y) {
    x = "0" + x;
    y = "0" + y;
    int[][] lcsTable = getLcsTable(x, y);

    StringBuilder lcs = new StringBuilder();
    backTracking(lcs, x.length() - 1, y.length() - 1, lcsTable, x);

    return lcs.toString();
  }

  private void backTracking(StringBuilder lcs, int m, int n, int[][] lcsTable, String x) {
    if (m == 0 || n == 0) {
      return;
    }
    //위쪽, 왼쪽, 대각선(왼쪽 위) 값보다 클 때 👉 문자 기록하고 대각선으로 이동
    if (lcsTable[m][n] > lcsTable[m - 1][n - 1]
        && lcsTable[m][n] > lcsTable[m][n - 1]
        && lcsTable[m][n] > lcsTable[m - 1][n]) {
      lcs.insert(0, x.charAt(m));
      backTracking(lcs, m - 1, n - 1, lcsTable, x);
    }
    //왼쪽 값과 같고, 위쪽 값보다 클 때 👉 왼쪽으로 이동
    else if (lcsTable[m][n] > lcsTable[m - 1][n]
        && lcsTable[m][n] == lcsTable[m][n - 1]) {
      backTracking(lcs, m, n - 1, lcsTable, x);
    } 
    //왼쪽, 위쪽 값과 같을 때 👉 위쪽으로 이동
    else {
      backTracking(lcs, m - 1, n, lcsTable, x);
    }
  }
}

 

마지막 두 조건문 순서를 바꾸면 LCS는 "ACBA"이다.

 

---

4. 예제

• Longest Common Subsequence - www.codewars.com/kata/52756e5ad454534f220001ef
• 문제 풀 때마다 추가 예정