[BOJ] 9252번 : LCS 2(DP)

목차

접근

Ref:

[Velog] 그림으로 알아보는 LCS 알고리즘

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

[Wikipedia] Longest Common Subsequence

Longest common subsequence - Wikipedia

LCS 알고리즘은 너무 유명해서 알고리즘에 대한 개요는 설명할게 없을 것 같다.

영어 그대로 해석하자면 최장 길이 공통 부분수열이다.

공통 문자열과는 다르게, 연속적으로 등장하지 않고 순서만 맞다면 공통 부분수열로써 맞다고 볼 수 있다.

그렇기에 DP 테이블에 최대값을 저장해두는 방식으로 업데이트를 진행하면 어렵지 않게 해결할 수 있다.

해결

위의 두 레퍼런스를 참고하여, 알고리즘을 코드로 구현하면 그렇게 어렵지 않게 구현할 수 있을것이다.

예시를 들어 알고리즘에 대한 설명을 진행해보겠다.

문자열 `ACAYKP` , `CAPCAK`를 보자.

초기 LCS 테이블

LCS알고리즘 시작전에 각각의 문자열의 맨 앞에 빈 문자열을 대입해주고, 각각의 길이들은 0으로 초기화 시켜준다. 그 이유는 뒤의 알고리즘에서 보면 알 수 있겠지만, 만약 초기의 빈 수열과 비어있지 않은 수열이 비교되면, 그 둘 간의 LCS는 항상 빈 수열이기 때문에 해당 과정의 초기화가 필요하다. 

 

LCS는 딱 아래와 같이 세가지 조건을 만족하는 점화식을 수행하면 된다.

$ LCS(X_i, Y_j)=
\begin{cases}
0, & \mbox{if }i=0 \mbox{ or } j=0 \\
LCS(X_{i-1}, Y_{j-1})  {\hat {} } x_i, & \mbox{if  }i,j > 0\mbox{ and } x_i = y_j \\
max(LCS(X_i, Y_{j-1}), LCS(X_{i-1}, Y_j)), & \mbox{if }i,j >0 \mbox{ and } x_i \ne y_j \\
\end{cases} $

 

각각의 경우는 아래와 같다.

• 첫번째 경우는 빈 문자열에 대해서 초기화하는 경우
• 두번째 경우는 문자열이 같을 때 해당 문자열을 합쳐주는 경우
• 세번째 경우는 문자열이 다를 때 길이가 더 긴 길이의 LCS를 배정해주는 경우

처음의 경우는 설명할게 없으니까, 넘어가고 두번째와 세번째 경우를 인지하고 일단 실제 예시를 보면서 테이블 업데이트를 진행해보겠다.

CAPCAK의 C와 ACAYKP를 비교 갱신

• `i = 1, j = 1`

C(`i_1`)가 처음의 A(`j_1`)와 만났을 땐, 두 문자열이 같지 않기 때문에, 이전까지의 LCS에서 최댓값으로 갱신해준다.

이전까지의 LCS의 최댓값은 `max(LCS[i-1][j], LCS[i][j-1])`로 구하는데, 이 의미에 대한 내용을 해석해보자.

여기서의 `LCS[i-1][j]`는 이전의 빈 문자(∅)와 현재 문자A를 비교했던 LCS값, `LCS[i][j-1]`은 현재 문자C와 이전의 빈문자(∅)를 비교했던 LCS값이다.

그니까 의미로 보자면, LCS("", "A"), LCS("C", "") 의 값을 비교하는 과정이다.

이 과정은 이번에 문자가 같지 안다면, 이전 과정에서까지 갱신된 LCS를 가져와야한다.

 

• `i=1, j=2`

C(`i_1`)가 그 다음 C(`j_2`)와 만났을 땐, 두 문자열이 같기 때문에, ∅과 A문자열의 LCS(비교하고 있는 문자열들의 이전문자열까지의 LCS)에 현재 같은 C까지의 갯수 1을 더한다.

두 문자가 같지 않은, 위 과정과 더하는 LCS값이 다르다는 의문점이 들 수 있다.

위는 두 문자가 같지 않다면, 이번 문자를 포함하여 이전 과정에서의 LCS로 갱신하기 때문이고, 이번 두 문자가 같다면 이번 두 문자를 제외한 이전 과정에서의 LCS에 길이를 하나 더 늘려줘야하기 때문이다.

 

이 두 내용만 잘 인지하여, LCS 테이블을 업데이트하면 아래와 같은 결과가 나온다.

완성된 LCS 테이블

 

LCS길이 값은 다 구했는데, LCS 자체는 어떻게 구해야할까?

이 과정은 위에 표시한 화살표를 거꾸로 따라 가는 방법으로 구해낼 수 있다.

맨 마지막 LCS 길이(모든 업데이트가 끝났을 때 LCS길이)를 기준으로, 화살표를 거꾸로 따라 올라가면, LCS 길이가 업데이트 됐을 때를 유추해볼 수 있다. LCS 길이가 바뀌었다는건, LCS 원소가 늘어났다라는 것으로 유추할 수 있기 때문에 찾는 과정을 통해 이해해보자.

 

`LCS[i-1][j], LCS[i][j-1]`의 값 중 같은 값이 있다면, 거기서부터 유래된 것이기에 그쪽으로 탐색을 진행한다.

어디부터 탐색하는지는 상관없다.(LCS가 여러개가 나올 수 있기 때문에)

우리 테이블에선 (K,K) 쪽에서 유래했기 때문에 그쪽으로 탐색을 진행했다.(회색 배경)

 

근데 이번 (K,K)에서 탐색을 진행하려고 봤더니, `LCS[i-1][j], LCS[i][j-1]` 중 같은 값이 없다.

그렇다는건 업데이트가 진행이 되었던 곳이라는 것으로 유추할 수 있다. 그래서 그 다음 탐색은 `LCS[i-1][j-1]`로 탐색을 진행하고, 이번 탐색의 문자를 저장한다.(빨간 글자) => (K)

 

이제 쭉 이렇게 탐색을 진행하면서, 위와 같이 업데이트 되었던 위치의 문자를 저장하여 결과를 보자.

 

그럼 위와 같이 끝까지 업데이트가 진행이 되고, 수열은 (K, A, C, A) 로 들어온 것을 알 수 있다.

이 수열을 거꾸로 표시하면 우리가 찾는 LCS인 `ACAK`가 된다.

 

이렇게 DP 알고리즘을 활용해서 LCS 테이블을 구할 수 있고, 추적 알고리즘을 이용해서 LCS 자체를 구할 수 있다. 

코드

A = input()
B = input()
len_A = len(A)
len_B = len(B)

LCS = [[0] * (len_B+1) for _ in range(len_A+1)]
for i in range(len_A+1):
    for j in range(len_B+1):
        if i == 0 or j ==0:
            LCS[i][j] = 0
        elif A[i-1] == B[j-1]:
            LCS[i][j] = LCS[i-1][j-1] + 1
        else:
            LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
            
res = []
i = len_A
j = len_B
while i and j:
    if LCS[i-1][j] == LCS[i][j]:
        i -= 1
        continue
    elif LCS[i][j-1] == LCS[i][j]:
        j -= 1
        continue
    else:
        i -= 1
        j -= 1
        res.append(A[i])
        
print(LCS[-1][-1])
print("".join(res[::-1]))