Longest Common Subsequence

Q: 최장 공통 부분 수열의 시간 복잡도는 얼마인가요?

표를 사용하는 방법은 접두사 쌍마다 한 칸씩 계산하므로 O(n × m) 시간이 걸립니다. 전체 표를 사용하면 O(n × m) 메모리가 필요하고, 두 행을 사용하면 O(min(n, m)) 메모리가 필요합니다. 표 없이 단순 재귀를 사용하면 지수 시간이 걸립니다.

보통동적 계획법

+10

두 문자열 text1과 text2가 주어집니다. 문자열의 부분 수열은 일부 문자를 원래 순서대로 유지하고 나머지는 제외한 것입니다. 유지한 문자들이 서로 이웃할 필요는 없습니다. 두 문자열 모두의 부분 수열인 가장 긴 문자열의 길이를 반환하세요. 두 문자열에 공통된 문자가 없으면 0을 반환하세요.

함수

longestCommonSubsequence(text1: string, text2: string) → integer

text1string: 첫 번째 문자열
text2string: 두 번째 문자열
반환값integer: 최장 공통 부분 수열의 길이

제약 조건

1 ≤ text1.length ≤ 1000
1 ≤ text2.length ≤ 1000
두 문자열 모두 소문자 영어 문자만 포함합니다.

예제

입력: text1 = "stone"text2 = "longest"
출력: 3
설명: o, n, e는 두 단어 모두에서 이 순서로 나타나므로 one은 공통이며 길이는 3입니다. 문자 s와 t는 longest에서는 마지막에 오지만 stone에서는 처음에 오므로, 이를 사용하면 최대 st까지 가능합니다.

입력: text1 = "pear"text2 = "reap"
출력: 2
설명: 두 단어 모두에 ea가 나타납니다. 두 단어에서 p와 r은 ea의 서로 반대쪽에 있으므로 어느 쪽도 ea와 결합할 수 없으며, 답은 2입니다.

후속 질문

가장 긴 공통 부분 수열 중 하나와 그 길이를 함께 반환할 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

탐욕적 매칭은 실패합니다. cab의 c를 abc의 마지막 c와 짝지으면 a와 b에 남는 것이 없지만, 이를 건너뛰면 ab를 찾습니다. 두 접두사의 답은 더 짧은 접두사의 답에 따라 달라지므로, (n+1) × (m+1) 표를 사용하면 모든 쌍을 한 번씩 해결할 수 있습니다. 각 행은 바로 위 행만 읽으므로 두 행이면 충분합니다.

재귀를 사용해 첫 글자 비교하기

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

lcs(i, j)를 접미사 text1[i:]와 text2[j:]에 대한 답이라고 하자. 두 접미사의 첫 글자가 같으면 그 글자들을 짝지어라. 이 짝을 건너뛰는 최장 공통 부분 수열이 있다면, 첫 번째 짝을 이 짝으로 바꾸어도 길이는 줄어들지 않는다. 따라서 답은 1 + lcs(i+1, j+1)이다.

두 글자가 다르면 둘 다 사용할 수 없다. 그렇게 하면 두 글자의 짝이 서로 교차하기 때문이다. 따라서 둘 중 하나를 제외할 수 있다. max(lcs(i+1, j), lcs(i, j+1)). 빈 접미사의 답은 0이다.

글자가 일치하지 않을 때마다 두 번의 호출이 시작된다. 공통 글자가 없는 20글자 문자열 두 개만으로도 이미 약 2.8 × 10^11번의 호출이 필요하지만, 서로 다른 쌍 (i, j)는 (n+1) × (m+1)개뿐이므로 거의 모든 호출은 이전 호출을 반복한다.

알고리즘

i와 j에서 시작하는 접미사에 대해 lcs(i, j)를 작성합니다.
i 또는 j가 해당 문자열의 끝을 지나면 0을 반환합니다.
text1[i] == text2[j]이면 1 + lcs(i+1, j+1)을 반환합니다.
그렇지 않으면 max(lcs(i+1, j), lcs(i, j+1))을 반환합니다.
정답은 lcs(0, 0)입니다.

def longestCommonSubsequence(text1, text2):
    def lcs(i, j):
        # The longest common subsequence of text1[i:] and text2[j:]
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + lcs(i + 1, j + 1)
        return max(lcs(i + 1, j), lcs(i, j + 1))

    return lcs(0, 0)

접두사 표를 채우세요

핵심 아이디어

dp[i][j]를 text1의 처음 i개 문자와 text2의 처음 j개 문자에 대한 답이라고 하자. 따라서 인덱스 0은 빈 접두사를 의미하며, 0번째 행과 0번째 열의 값은 0이다. 두 접두사의 마지막 문자 text1[i-1]과 text2[j-1]을 비교한다. 문자가 같으면 짝을 이루므로 dp[i-1][j-1] + 1이고, 다르면 둘 중 하나를 제외하므로 max(dp[i-1][j], dp[i][j-1])이다. 이는 끝에서부터 읽는 재귀식이다.

각 셀은 위쪽, 왼쪽, 왼쪽 위 대각선의 셀을 참조하므로, 행마다 왼쪽에서 오른쪽으로 채우면 항상 필요한 값이 준비되어 있다. pear와 reap의 경우 pea에 해당하는 행은 [0, 0, 1, 2, 2]이다. 이 행에서 rea에 해당하는 셀의 값은 2인데, a와 a가 일치하여 pe와 re에 해당하는 셀의 값에 1을 더하기 때문이다.

문자 1000개로 이루어진 두 문자열을 처리하는 데는 상수 시간 단계가 약 10^6번 필요하다.

알고리즘

(n+1) × (m+1)개의 0으로 이루어진 dp 테이블을 만듭니다.
i가 1부터 n까지, j가 1부터 m까지일 때 text1[i-1]과 text2[j-1]을 비교합니다.
일치하면 dp[i][j] = dp[i-1][j-1] + 1로 설정합니다.
그렇지 않으면 dp[i][j] = max(dp[i-1][j], dp[i][j-1])로 설정합니다.
dp[n][m]을 반환합니다.

def longestCommonSubsequence(text1, text2):
    n, m = len(text1), len(text2)
    # dp[i][j]: the longest common subsequence of text1[:i] and text2[:j].
    # Row 0 and column 0 stay 0: an empty prefix has nothing in common.
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if text1[i - 1] == text2[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[n][m]

두 행만 유지

핵심 아이디어

한 행이 완료되면 그 위의 행은 다시 읽지 않습니다. 완료된 행에는 prev를, 채우고 있는 행에는 cur를 사용하고, 각 행이 끝난 뒤 둘을 교환합니다. 점화식과 순서는 그대로 유지됩니다.

답은 어떤 문자열이 먼저 오는지에 따라 달라지지 않으므로, 더 짧은 문자열을 따라 행을 진행합니다. 그러면 각 행에는 min(n, m) + 1개의 숫자만 들어갑니다. 가장 큰 입력에서도 백만 개의 셀 대신 1001개만 사용하며, 단계 수는 동일하게 10^6입니다.

알고리즘

text2가 text1보다 길면 서로 바꾸세요.
각각 m + 1개의 0으로 이루어진 prev와 cur를 만들고, 여기서 m은 더 짧은 길이입니다.
text1의 각 문자에 대해 표와 같은 규칙을 사용해 cur[1..m]을 채우세요. 위 행에 해당하는 값은 prev에서 읽습니다.
prev와 cur를 서로 바꾸세요.
prev[m]을 반환하세요.

def longestCommonSubsequence(text1, text2):
    if len(text2) > len(text1):
        text1, text2 = text2, text1  # keep the rows as short as the shorter string
    m = len(text2)
    # prev[j]: the answer for the previous prefix of text1 and text2[:j]
    prev = [0] * (m + 1)
    for ch in text1:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if ch == text2[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[m]

함정과 경계 사례

테이블 인덱스와 문자열 인덱스를 혼동하는 것. 셀 dp[i][j]은 text1[i-1]과 text2[j-1]을 비교합니다. 행 0은 빈 접두사이기 때문입니다.
일치할 때 dp[i-1][j-1]에 1을 더하는 대신 max(dp[i-1][j], dp[i][j-1])에 1을 더하는 것. 그러면 문자 하나를 두 번 사용할 수 있습니다. aa와 a를 비교하면 1이 아니라 2를 반환합니다.
아직 읽고 있는 행에 값을 쓰는 것. 두 개의 행을 사용할 때는 위쪽 행의 모든 값을 prev에서 가져와야 하며, cur[0]은 0으로 유지되어야 합니다.
길이가 1000자인 문자열에서 Python 재귀를 메모이제이션하는 것. 호출 깊이가 2000까지 도달해 기본 제한인 1000을 초과합니다.

자주 묻는 질문3

최장 공통 부분 수열의 시간 복잡도는 얼마인가요?

표를 사용하는 방법은 접두사 쌍마다 한 칸씩 계산하므로 O(n × m) 시간이 걸립니다. 전체 표를 사용하면 O(n × m) 메모리가 필요하고, 두 행을 사용하면 O(min(n, m)) 메모리가 필요합니다. 표 없이 단순 재귀를 사용하면 지수 시간이 걸립니다.

최장 공통 부분 수열과 최장 공통 부분 문자열의 차이는 무엇인가요?

부분 수열은 순서만 유지된다면 글자를 건너뛸 수 있지만, 부분 문자열은 서로 이웃한 글자들의 연속된 구간입니다. stone과 longest의 최장 공통 부분 수열은 one(3)이지만, 최장 공통 부분 문자열은 on(2)입니다. 부분 문자열 표는 일치하지 않을 때 이웃한 값을 복사하는 대신 셀을 0으로 초기화합니다.

LCS는 diff 도구 및 편집 거리와 어떤 관련이 있나요?

파일의 두 버전 간 차이(diff)는 두 버전의 줄에서 가장 긴 공통 부분 수열을 유지하고, 그 밖의 모든 줄을 추가되거나 삭제된 것으로 표시합니다. 한 문자열을 다른 문자열로 바꾸는 데 필요한 최소 삽입 및 삭제 횟수는 n + m - 2 × LCS입니다. 편집 거리는 문자 교체도 허용하므로 별도의 표가 필요합니다.

def longestCommonSubsequence(text1, text2):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

text1 = "stone"
text2 = "longest"

예상 출력

Longest Common Subsequence

함수

제약 조건

예제

힌트

풀이

재귀를 사용해 첫 글자 비교하기

접두사 표를 채우세요

두 행만 유지

함정과 경계 사례

자주 묻는 질문3

비슷한 문제