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

LCS 문제는 두 문자열이 주어졌을 때 두 문자열이 공통으로 가지는 문자의 가장 긴 길이를 구하는 문제입니다.

이 때, 공통으로 가지는 문자의 순서가 바뀌어선 안됩니다.

 

예시는 다음과 같습니다.

 

해당 문제는 동적계획법을 이용해 O(N^2)의 시간 복잡도로 해결할 수 있습니다.

 

동적계획 방법입니다.

1. 각 문자열 별로 dp 테이블을 만들기 위해 2차원 배열을 선언합니다.

2. dp 테이블의 인덱스 0은 문자열이 0개일 때이므로 모두 0으로 초기화합니다.

3. 이후 테이블을 초기화 할 때 해당 자리의 문자열(Xi, Yj)을 비교합니다.

    3-1. 문자열이 다르면 i 또는 j를 줄인 것 중 큰 값으로 테이블을 초기화합니다.

    3-2. 문자열이 같으면 i와 j 모두 줄인 값에서  +1 하여 초기화합니다.

4. LCS의 길이는 테이블의 가장 마지막 인덱스 입니다. (c[N][M])

 

 

파이썬으로 구현한 코드는 다음과 같습니다.

X = input()
Y = input()

N = len(X)
M = len(Y)
c = [[0]*(M + 1) for i in range(N + 1)]

for i in range(1, N+1):
    for j in range(1, M+1):
        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])

print(c[N][M])