LCS 최장 공통 부분 수열 DP

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

---

두개의 문자열이 주어졌을 때 공통으로 들어 있는 부분 수열 중 가장 긴 수열을 말한다.

예를 들어

ABCDE와 ACDFG이 주어졌다면 두 문자열의 공통 부분 수열은 

{A}, {C}, {D}, {AC}, {AD}, {ACD} 이고 LCS는 바로 {ACD}를 말한다. 

 

- LCS와 LCS (최장 공통 부분 수열과 최장 공통 부분 문자열)

사실 LCS는 뜻이 두가지다 ..! 

LCS( Longest Common Subsequence) 이 있고

최장 공통 부분 문자열LCS( Longest Common Substring) 이 있다. 

위 두 문자열 ABCDE와 ACDFG에 대해서 최장 공통 부분 수열는 {ACD}지만 최장 공통 부분 문자열은 연이어져야 한다. 

따라서 {CD} 이다. 

 

 

 

☑️ 접근 방법

---

이 문제는 DP(dynamic programming)으로 접근하여 점화식으로 풀면 간단하게 풀 수 있다고 한다. 

여기서 바로

DP로 문제 풀기 위한 조건

 

1. 작은 문제가 반복적으로 일어난다.
2. 같은 문제는 구할 때마다 정답이 같다.

 

 

 

즉 큰 문제를 풀 때 작은 문제로 나눠서 푸는데 작은 문제와 큰 문제 푸는 방법이 같다는 것이다. 

 

 

 

👁‍🗨LCS 점화식

---

LCS의 점화식은 다음과 같다.

 

 

예를 들어 

ABCDE와 ACDFG 두 문자열이 있다고 하자

 

X : ABCDE

Y : ACDFG

 

X의 마지막 문자(E)를 하나 지워보자 그러면 ABCD가 될 것이다. 그래도 LCS에는 상관이 없다. 

X의 마지막 문자(D)를 하나 더 지우면 ABC가 되고 이번에는 LCS 길이가 하나 줄어든다. 

 

즉 수열의 마지막 문자를 제거하면  1. LCS 길이가 그대로다 2. LCS 길이가 줄어든다. 두가지 경우를 가진다. 

 

c[i, j]를 Xi와 Yi의 최장 공통 부분 순열이라고 하자. i와 j는 문자열을 가리키는 인덱스다.

 

i의 범위  1 <= i <= 5

j의 범위 1<= j <=5

 

1) i = 0 or j = 0 인경우 

문자열 길이가 0 이면 LCS 도 0이 될 수 밖에 없다.

 

2) i != 0 and j !=0 이고  Xi != Yj 인 경우

 

예를 들어 

X : ABCDE, Y : ACDFG 일 때

X의 마지막 문자 E와 Y의 마지막 문자 G가 다르다. 

그러면 두가지 경우로 나눠 생각 해 볼 수 있다.

1) LCS가 E로 끝나는 경우

2) LCS가 G로 끝나는 경우 

 

1) LCS가 E로 끝나는 경우 G는 최장 공통 수열에 영향을 미치지 않는다. 그러므로 

c[i, j] = c[i, j - 1]로도 생각 할 수 있을 것이다.  

 

1) LCS가 G로 끝나는 경우 반대로 E가 최장 공통 수열을 만드는데 영향을 미치지 않으므로 지워도 상관 없다.

따라서 c[i -1, j] = c[i, j]

 

우리는 최장 공통 수열을 원하므로 c[i, j] = max(c[i, j - 1], c[i -1, j] )의 값을 가질 것이다.

 

 

2) i != 0 and j !=0 이고  Xi == Yj 인 경우

예를 들어 ASC 와 AEC 두 문자열의 마지막 값(C)이 같다면 C는 이미 최장 길이 문자열의 원소로 확보해 두고 C를 제외한 

AS와 AE의 비교 과정을 거치고 싶을 것이다.

그러므로 c[i, j] = c[i - 1][j - 1] + 1 이 된다. 

 

 

🔳 행렬을 이용한 값 계산 

---

 

사실 알고리즘 시간에 이렇게 배웠었다 박영훈 교수님의 버벅거림과 함께 말이다.

그래서 이 방식이 더 익숙하고 이를 dp 점화식 손 대기 어렵다 느껴지면 행렬로 먼저 친근해지는 것이 더 좋을 듯 하다.

 

예시로 들었던 ABCDE와 ACDFG를 행렬에 값으로 넣어주었다.

 

 

이차원 행렬로 만들고 0번째 인덱스들은 0으로 초기화 시켜준다. 

 

X 문자열에 대해 검사를 시작하는데 A 문자열이 같다!! 그러면 좌측값 0과 위쪽 값 0 중 큰 값 (결국 0)에 +1을 해준다.

 

 

X의 i =1 일때 즉 A 원소에 대해 수행해주면 

 

이렇게 한 줄이 완성이 되겠다 

 

B도 마친가지로 해주고 C를 보게 되면 

처음 A 한 것 처럼 C 역시 자신의 좌측값(1)과 우측 값(1) 중 큰 값에 +1을 한다. 그러면 2가 된다 

 

반복적인 일들을 +1씩 증가시키면서 (DP의 조건) 마지막까지 행렬을 완성하게 되면 

이렇게 행렬이 완성되고 행렬의 마지막 값이 LCS의 길이 즉 3이 도출된다. 

 

➰ c++ 코드 : 

//
//  9251_LCS.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/03/01.
//

#include <cstdio>
#include <cstring>
#include <algorithm>

char X[1010];
char Y[1010];
int C[1010][1010];

using namespace std;

int main()
{
    scanf("%s", &X);
    scanf("%s", &Y);
    
    int lenX = (int)strlen(X);
    int lenY = (int)strlen(Y);
 
    for (int i = 1; i <= lenX; i++) {
        for (int j = 1; j <= lenY; j++) {
            if (X[i - 1] == Y[j - 1])
                C[i][j] = C[i - 1][j - 1] + 1;
            else
                C[i][j] = max(C[i - 1][j], C[i][j - 1]);
        }
    }
    printf("%d\n", C[lenX][lenY]);
    
    return 0;
}