최장공통부분수열(Longest Common Subsequence - LCS)

1. 개념 🐢

  최장공통부분수열(Longest Common Subsequence)이란 주어진 수열의 부분 수열에서 가장 긴 것을 의미한다. 위의 그림에서 알 수 있는 것처럼 부분 수열이 연속적일 필요는 없다.

 

2. 동작방식 🦎

  동작 방식은 DP를 이용한다. 문자열 A와 문자열 B가 주어졌다고 하자.

1. 문자열 A와 문자열 B를 한 글자씩 비교한다.
2. 비교하는 문자가 같다면 DP[i][j] = DP[i - 1][j - 1] + 1이 된다.
   비교하는 문자가 다르다면 DP[i][j]는 DP[i-1][j]와 DP[i][j-1] 중에 큰 값으로 설정한다.
3. 1번과 2번 과정을 반복한다.

  여기서 말하는 DP[i][j]는 문자열 A는 i번째까지 문자열 B는 j번째까지 고려하였을 경우에 얻을 수 있는 최장공통부분수열의 길이이다. i와 j는 1부터 문자열의 길이까지 순회하고 i 또는 j가 0인 장소의 DP 값은 0으로 설정한다.

• 비교하는 문자가 같을 때 'DP[i][j] = DP[i - 1][j - 1] + 1'인 이유
    이전 상황까지의 최장공통부분수열에 현재 비교된 같은 문자를 추가하는 과정이다.
• 비교하는 문자가 같을 때 'DP[i][j] = max(DP[i-1][j], DP[i][j-1])'인 이유
    해당 과정을 이해하기 위해서는 최장공통부분수열에서의 부분수열은 연속적일 필요가 없다는 것을 다시 인지해야 한다. 연속적일 필요가 없으므로 비록 지금 비교하는 문자가 다르더라도 이전까지의 상황에서 얻은 최장공통부분수열을 계속해서 사용하면 된다.
    여기서 말하는 이전까지의 상황은 DP[i-1][j]와 DP[i][j-1]을 의미한다. (최장공통문자열의 동작방식과 비교해 본다면 더 쉽게 이해할 수 있을 것이다.)

  'ABCDEF'와 'GBCDFE'를 이용하여 LCS를 구하는 방법을 그림을 이용하여 이해하여 보자.

  위의 과정을 통해 'ABCDEF'와 'GBCDFE'의 최장공통부분수열은 'BCDF', 'BCDE'라는 것을 알 수 있다.

  위의 과정을 활용한다면 최장공통부분수열의 길이뿐만 아니라 최장공통부분수열인 'BCDF'와 'BCDE'를 알 수 있다. 그 과정은 위의 동작방식을 역순으로 해주면 된다. 최장공통부분수열을 저장할 배열을 LCS라고 하자.

1. DP의 마지막 값부터 시작한다.
2. DP[i-1][j]와 DP[i][j-1] 중 현재 값과 같은 것을 찾는다.
3. 같은 값이 있다면 해당 값으로 이동한다.
   같은 값이 없다면 LCS에 해당 문자를 넣고 DP[i-1][j-1]로 이동한다.
4. 2번과 3번 과정을 0을 만날 때까지 반복한다.

• DP[i-1][j]와 DP[i][j-1] 중 현재 값과 같은 값이 있는 경우
    이전 상황과 현재 상황을 비교하였을 때 같은 문자를 찾지 못한 경우이다. 그래서 LCS에 값을 저장하지 않는다.
• DP[i-1][j]와 DP[i][j-1] 중 현재 값과 같은 값이 없는 경우
    이전 상황과 현재 상황을 비교하였을 때 같은 문자를 찾아서 DP값에 변화가 있었던 경우이다. 그러므로 해당 값을 LCS에 저장해주어야 한다.

  위의 과정을 마치게 된다면 LCS에 최장공통부분수열이 담기게 된다.

 

3. 구현(JAVA) 🐍

  DP의 마지막 값이 주어진 수열의 최장공통부분수열의 길이를 저장하고 있으므로 최장공통문자열에서 처럼 최대길이를 저장할 필요가 없다.

public static void main(String[] args) {
    String A = "ABCDEF";
    String B = "GBCDFE";
    int aStrLen = A.length();
    int bStrLen = B.length();
    int[][] DP = new int[aStrLen + 1][bStrLen + 1];

    for(int i = 1; i <= aStrLen; i++) {
        for(int j = 1; j <= bStrLen; j++) {
            // 비교하는 문자가 같은 경우
            if(A.charAt(i - 1) == B.charAt(j - 1)) {
                DP[i][j] = DP[i - 1][j - 1] + 1;
            }
            // 비교하는 문자가 다른 경우
            else {
                DP[i][j] = Math.max(DP[i - 1][j], DP[i][j - 1]);
            }
        }
    }

    System.out.println(DP[aStrLen][bStrLen]);
}

 

해당 글은 emplam27 님의 '그림으로 알아보는 LCS 알고리즘'을 참고하였습니다.