LCS 알고리즘

LCS(Longest Common Subsequence, 최장 공통 부분 수열)

보통 최장 공통 부분 수열(공통적으로 일치하는 수열 중 가장 긴 부분)을 나타내지만 최장 공통 문자열을 말하기도 한다.

• 최장 공통 부분 수열은 문자열이 떨어져 있어도 상관없다. ACAYKP CAPCAK
• 최장 공통 문자열은 부분 문자열이 연결된 형태여야 한다. ACAYKP BACAED

이처럼 LCS 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

 

백준 9251번 LCS

import sys

def lcs_length(X, Y):
    m, n = len(X), len(Y)
    
    # dp 테이블 초기화
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # dp 테이블 채우기
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:  # 같은 문자가 발견되면
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:  # 다른 문자인 경우
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    return dp[m][n]

# 표준 입력을 받음
input = sys.stdin.read
data = input().split()
X = data[0]
Y = data[1]

# 결과 출력
print(lcs_length(X, Y))

 

LCS 알고리즘의 구체적 원리

1. DP 테이블 초기화: 문자열 X의 길이를 m, 문자열 Y의 길이를 n으로 두고, (m+1) x (n+1) 크기의 2차원 리스트 dp를 생성한다. dp[i][j]는 문자열 X의 처음 i 문자와 문자열 Y의 처음 j 문자 간의 LCS의 길이를 저장하고 초기값은 0으로 설정한다.
2. DP 테이블 채우기: 이중 반복문을 사용하여 각 문자열의 모든 문자를 비교한다. 반복문의 범위는 1부터 m 또는 n까지이다.
   • 문자 일치: 만약 X[i-1]와 Y[j-1]이 일치한다면, dp[i][j]를 dp[i-1][j-1] + 1로 설정한다. 이는 현재 문자가 LCS의 일부가 되므로, 이전 문자까지의 LCS 길이에 1을 추가한 것이다.
   • 문자 불일치: 만약 두 문자가 서로 다르다면, dp[i][j]는 dp[i-1][j]와 dp[i][j-1] 중 큰 값을 선택한다. 이는 현재 문자를 포함하지 않고, 이전 문자에서 더 긴 LCS를 유지하기 위함이다.
3. 결과 추출: DP 테이블의 마지막 셀 dp[m][n]에 두 문자열 전체의 LCS 길이가 저장되어 있다. 이 값을 출력하면 최장 공통 부분 수열의 길이를 얻을 수 있다.

예제 설명

예를 들어, 문자열 "ACAYKP"와 "CAPCAK"에 대해 LCS를 계산하는 경우:

• 'A'와 'C', 'A'와 'A' 등을 비교하면서 DP 테이블을 채워나간다.
• 각 단계에서 문자가 일치하면 대각선 값에 1을 더하고, 일치하지 않으면 왼쪽 혹은 위쪽의 최댓값을 가져온다.
• 최종적으로 dp[6][6]은 4가 되며, 이는 "ACAK"의 길이와 일치한다.