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

in Blog / 알고리즘 on 공통, 부분, 수열, Lcs, Longest, Common, Subsequence

최장 공통 부분 수열(Longest Common Subsequence)이란?

LCS (최장 공통 부분 수열)은 두 개의 시퀀스(문자열 또는 리스트)에서 순서를 유지하면서 공통으로 등장하는 가장 긴 부분 수열을 찾는 문제야.

  • 여기서 “부분 수열”은 일부 문자를 삭제만 가능하고, 순서는 유지하는 형태야.

예시

A = "ABCDGH"
B = "AEDFHR"

  • 가능한 공통 부분 수열 : “ADH”

  • 이게 가장 긴 공통 부분 수열이기 때문에, LCS = “ADH”, 길이는 3

부분 수열 vs 부분 문자열 [예시(“ABCDEF”)]

용어의미예시(“ABCDEF”)
부분 문자열연속된 문자“BCD”, “ABC”
부분 수열순서만 지킴, 연속 X“ACE”, “ADF”

LCS는 부분 수열로서 연속되지 않아도 됨

알고리즘 설명 (DP 방식)

LCS는 작은 문제들을 쪼개서 푸는 전형적인 동적 계획법(DP) 문제야

점화식(Recurrence Relation)

for i in range(1, m+1):
    for j in range(1, n+1):
        if A[i-1] == B[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1 # dp[i][j]는 A의 앞 i개, B의 앞 j개를 비교했을 때의
        else:                           # 최장 공통 부분 수열 길이를 저장
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

DP 테이블 구조

  • 크기: (len(A)+1) x (len(B)+1)

  • dp[i][j]는 A의 앞 i개, B의 앞 j개를 비교했을 때의 LCS 길이

LCS 자체 구하기 (문자열 복원)

def lcs_string(A, B):
    m, n = len(A), len(B)
    dp = [[0]*(n+1) for _ in range(m+1)]

    for i in range(1, m+1):
        for j in range(1, n+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # 문자열 복원
    i, j = m, n
    lcs_result = []
    while i > 0 and j > 0:
        if A[i-1] == B[j-1]:
            lcs_result.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_result))

실전에서의 활용

분야활용 예시
버전 비교Git, diff 명령어
텍스트 비교문서 유사도 비교, 표절 검사
생물 정보학DNA, 단백질 서열 분석
에디터변경 사항 하이라이트
추천 시스템사용자 행동 시퀸스 비교

시각화 (예시 테이블)

A = "ABCBDAB"
B = "BDCAB"

      B D C A B
    0 0 0 0 0 0
A 0 0 0 0 1 1
B 0 1 1 1 1 2
C 0 1 1 2 2 2
B 0 1 1 2 2 3
D 0 1 2 2 2 3
A 0 1 2 2 3 3
B 0 1 2 2 3 4

LCS : BCAB (길이 : 4)

알아두면 좋은 팁

  • LCS는 시간복잡도 O(m*n) (문자열 길이가 커지면 느려짐)

  • LCS 길이를 활용해서 문자열 유사도 계산 가능(유사도 = (LCS 길이) / (최대 문자열 길이))

  • LCS를 3개 이상 문자열로 확장한 문제도 존재함 (난이도 ↑)

© 2022 JeongHwan Yun.