[알고리즘] LCS(Longest Common Subsequence)

LCS (Longest Common Subsequence_최장 공통 부분 수열)이란?

---

먼저, Subsequence가 무엇인지 이해해야 한다. 

 

일반적으로 부분 문자열을 다룰 때 사용하는 Substring이라는 개념을 살펴보자.

가나다라마바사

가파나카마바사

 

위의 예시로 든 두 문자열 간의 Substring은 "마바사" 이다.

그렇다면 Subsequence는?

가나다라마바사

가파나카마바사

 

위의 예시로 든 두 문자열 간의 가장 긴 Subsequence는 '가', '나', '마', '바', '사'  이다.

즉, Substring은 연속된 부분 문자열이고, Subsequence는 연속되지 않은 부분 문자열이다.

 

개념을 확실히 하기 위해 마지막으로 하나 더 해보자. 아래의 문자열에서 LCS(가장 긴 Subsequence)는?

ACAYKP            <---- 답: ACAK

CAPCAK

 

 

 

LCS 알고리즘 동작 방식

---

예시로 들 두 문자열은 다음과 같다. (https://www.acmicpc.net/problem/9252 <--- 해당 문제의 예시랑 같다.)

ACAYKP

CAPCAK

 

[그림 1] ACAYKP와 C의 Subsequence

 

일단 첫 번째 행과 열은 편의상 0으로 둔다.

그런 다음 위 테이블의 해석은 다음과 같다.

A와 C의 Subsequence는 0개

AC와 C의 Subsequence는 1개

ACA와 C의 Subsequence는 1개

ACAY와 C의 Subsequence는 1개 ...

 

마찬가지 방법으로 CA 문자열까지 비교해보자.

[그림 2] ACAYKP와 CA의 Subsequence

 

마찬가지 방법으로 CAP 문자열까지 비교해보자.

[그림 3] ACAYKP와 CAP의 Subsequence

 

 

 

테이블에 값을 넣는 원리

---

위의 테이블에서 컴퓨터는 어떤 기준에 따라 값을 넣는지 살펴보자.

[그림 4] 테이블에 값을 넣는 원리

 

위의 테이블에서 살구색으로 칠해진 셀을 보자.

먼저, 2로 채워진 셀을 보면 ACA와 CA를 비교하는데 가장 마지막 문자인 'A'가 같다. 즉 두 문자열의 LCS는 최소 1이다.

두 문자열에서 마지막 문자가 같다는걸 확인했으니, 이전 문자열인 AC와 C의 LCS를 알아낸다음 +1을 하면 된다. 

 

 

 

코드

---

위의 테이블을 채우는 과정을 코드로 살펴보자. 이전의 값을 활용하니 DP를 활용하면 된다.

class Main {

    private static int[][] fillTable(String s1, String s2) {
        int[][] table = new int[s2.length() + 1][s1.length() + 1];
        
        for (int i = 1; i < s2.length() + 1; i++) {
            for (int j = 1; j < s1.length() + 1; j++) {
                if (s1.charAt(j - 1) == s2.charAt(i - 1)) // 마지막 문자가 같다면 
                    table[i][j] = table[i - 1][j - 1] + 1;
                else
                    table[i][j] = table[i - 1][j] > table[i][j - 1] ? table[i - 1][j] : table[i][j - 1];
            }
        }
        
        return table;
    }
}

 

 

 

참고자료

---

[1] https://www.crocus.co.kr/787