[CS기초] LCS(Longest common subsequence, 최장 공통 부분 수열)

LCS(Longest common subsequence, 최장 공통 부분 수열)

LCS는 두 수열이 주어졌을 때, 순서를 유지하면서 공통적으로 나타나는 가장 긴 부분 수열을 찾는 문제입니다. 보통 문자열 비교에서 많이 활용됩니다.

 

가장 큰 특징은 부분 수열이기 때문에 연속해서 등장할 필요가 없고, 중간에 다른 값이 있더라도 순서만 맞는다면 공통 수열로 인정된다는 점입니다.

 

 

LCS 길이 구하기

LCS는 DP(동적 계획법)으로 해결할 수 있는 대표적인 문제인데요. 아래와 같은 점화식을 세워 해결합니다.

점화식

두 문자열 A[1..i], B[1..j]의 LCS 길이를 dp[i][j] 라고 하면,

if A[i] == B[j]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

• 같은 문자가 나오면 → 이전 대각선 값에 1을 더해주고,
• 다르면 → 왼쪽 또는 위쪽 중 더 큰 값을 선택합니다.

이 규칙으로 "ACAYKP"와 "CAPCAK" 두 문자열의 LCS 길이를 구하는 DP 테이블을 채우면 다음과 같습니다.

길이가 같다면 이전 공통 수열에 현재 문자를 포함할 수 있기 때문에 dp[i-1][j-1] + 1, 곧 대각선 위의 값에 + 1을 해준 값이 해당 테이블의 값이 됩니다.

 

반면 만약 같지 않다면 현재 문자를 제외하고 더 긴 수열을 유지해야 하기 때문에 각 문자열에서 한 글자씩 줄인 상태에서 더 긴 공통 수열의 길이를 해당 테이블의 값으로 삼습니다.

 

파이썬에서 LCS 길이 구하기 구현

s1 = input()  # 첫 번째 문자열 입력
s2 = input()  # 두 번째 문자열 입력

# dp 테이블 초기화: (len(s1)+1) x (len(s2)+1) 크기, 모두 0으로 초기화
# d[i][j]는 s1의 처음 i개 문자와 s2의 처음 j개 문자의 LCS 길이를 의미
d = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]

# DP 테이블 채우기
for i in range(1, len(s1) + 1):           # s1의 각 문자에 대해
    for j in range(1, len(s2) + 1):       # s2의 각 문자에 대해
        if s1[i-1] == s2[j-1]:            # 문자가 같으면
            d[i][j] = d[i-1][j-1] + 1     # 대각선 값 + 1
        else:
            # 문자가 다르면 위쪽 또는 왼쪽 값 중 큰 값을 선택
            d[i][j] = max(d[i-1][j], d[i][j-1])

# 최종 결과 출력: 전체 문자열에 대한 LCS 길이
print(d[len(s1)][len(s2)])

 

DP테이블 역추적을 통해 LCS 찾기

LCS 길이를 구하는 DP테이블을 통해, LCS 배열 자체를 찾을 수도 있습니다. 먼저, LCS 결과를 담을 빈 배열을 만든 뒤 테이블의 가장 오른쪽 아래에서 시작해 역추적을 시작합니다.

 

이때 문자가 같으면 결과 배열에 추가하고 대각선 왼쪽 위로 이동합니다. 만약 문자가 다르다면 값이 더 큰 값 쪽을 향해 왼쪽 또는 위쪽으로 이동합니다. 이를 반복하면서 어느 행열 중 어느 한쪽이라도 인덱스 0에 도달하면 역추적을 종료합니다.

 

최종적으로 결과 배열을 거꾸로 뒤집은 뒤 반환하면 우리가 원하는 LCS를 찾을 수 있습니다.

 

파이썬에서 LCS 찾기 구현

 # 길이가 n, m인 두 문자열에 대한 LCS 길이를 구하는 DP테이블이 채워져 있다고 가정
i, j = n, m         # dp 테이블의 마지막 인덱스부터 시작
lcs = []            # LCS 문자를 뒤에서부터 쌓을 리스트

while i > 0 and j > 0:
    if a[i-1] == b[j-1]:         # 문자가 같으면 LCS에 포함, 대각선 이동
        lcs.append(a[i-1])
        i -= 1
        j -= 1
    elif dp[i-1][j] >= dp[i][j-1]:   # 위쪽이 더 크면 위로 이동
        i -= 1
    else:                           # 왼쪽이 더 크면 왼쪽으로 이동
        j -= 1

return ''.join(reversed(lcs))   # 역추적이므로 뒤집어서 반환