LCS (Longest Common Subsequence)

개념 및 정의

Longest Common Subsequence(LCS)는 두 개의 문자열이나 순열에서 가장 긴 공통의 부분 순열을 찾는 문제입니다. 여기서 부분 순열이란 어떤 문자열에서 몇몇 문자를 제거하여 얻을 수 있는 새로운 문자열을 말합니다.

예를 들어, "ABCBDAB"와 "BDCAB"의 LCS는 "BDAB" 또는 "BCAB" 등이 될 수 있습니다.

장점

1. 다양한 응용 분야: 텍스트 비교, 유전자 분석 등 다양한 분야에서 활용됩니다.
2. 최적해 보장: 다이나믹 프로그래밍을 사용하면 항상 최적해를 찾을 수 있습니다.

단점

1. 계산 복잡성: 일반적으로 시간 복잡도가 O(nm)이므로 두 문자열이 길어질수록 계산이 복잡해집니다.

구현방법

LCS 문제는 다이나믹 프로그래밍(Dynamic Programming)을 이용해 효율적으로 해결할 수 있습니다.

1. 2차원 배열 초기화: 두 문자열의 길이를 각각 n, m이라 할 때, (n+1) x (m+1) 크기의 2차원 배열을 생성합니다.
2. DP 점화식 설정: LCS의 길이를 구하기 위한 점화식을 설정합니다.
3. 배열 채우기: 배열을 채우며 최적해를 찾습니다.

예시 코드 (Python)

def lcs(X , Y): 
    m = len(X) 
    n = len(Y) 
  
    L = [[0] * (n+1) for i in range(m+1)] 
  
    for i in range(m+1): 
        for j in range(n+1): 
            if i == 0 or j == 0 : 
                L[i][j] = 0
            elif X[i-1] == Y[j-1]: 
                L[i][j] = L[i-1][j-1] + 1
            else: 
                L[i][j] = max(L[i-1][j], L[i][j-1]) 
    return L[m][n] 

X = "ABCBDAB"
Y = "BDCAB"
print("Length of LCS is ", lcs(X, Y))

LCS 알고리즘은 문자열이나 시퀀스의 유사도를 측정하는 데 유용하므로, 이를 알고 있으면 문자열 관련 문제나 시퀀스 정렬 등에 활용할 수 있습니다.