Longest Common Subsequence

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

테이블을 사용하는 해법은 O(n × m) 시간이 걸립니다. 여기서 n 과 m 은 두 문자열의 길이입니다. 각 접두사 쌍마다 셀 하나를 채웁니다. 전체 테이블에는 O(n × m) 메모리가 필요하고, 두 행만 사용하면 O(min(n, m)) 이 필요합니다. 테이블 없이 단순 재귀를 사용하면 시간 복잡도가 지수적입니다.

Q: 최장 공통 부분 수열 자체를 어떻게 출력하나요?

표 전체를 채운 다음, dp[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인 공통 부분 수열입니다. longest에서는 s와 t가 마지막에 오고, stone에서는 처음에 오므로, 이 문자들을 사용하는 공통 부분 수열은 st뿐이며, 이는 더 짧습니다.

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

제출 시 숨은 테스트 +19개

후속 질문

최장 공통 부분 수열의 길이만이 아니라, 최장 공통 부분 수열 자체를 반환할 수 있나요?

힌트

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

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번 호출하게 된다. 대규모 테스트에는 글자가 각각 1000개씩 있다. 하지만 서로 다른 쌍 (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이 빈 문자열을 의미하게 된다.

점화식. 두 접두사의 마지막 문자 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]). 이는 끝에서부터 살펴본 재귀와 같은 논리다. 기저 사례: 빈 접두사는 어떤 문자열과도 공통인 문자가 없으므로 0번째 행과 0번째 열의 값은 0이다. 순서: 각 셀은 위쪽 셀, 왼쪽 셀, 대각선 왼쪽 위 셀을 참조하므로, 행마다 왼쪽에서 오른쪽으로 채우면 언제나 필요한 값이 준비되어 있다. 정답은 dp[n][m]이다.

pear와 reap의 경우 pea에 해당하는 행은 [0, 0, 1, 2, 2]이다. rea에 해당하는 셀의 값은 2인데, a와 a가 같으므로 pe와 re에 해당하는 셀의 값 1에 1을 더한 것이다. 마지막 셀에서는 pear와 reap을 비교한다. r과 p는 다르므로 이웃한 두 셀 중 더 큰 값인 2를 선택한다.

표에는 (n+1) × (m+1)개의 셀이 있고 각 셀을 계산하는 데 일정한 시간이 걸린다. 따라서 길이가 1000인 두 문자열에는 약 10^6번의 연산이 필요하다. 메모이제이션을 적용한 재귀도 같은 셀을 채우지만, 최대 n + m번의 호출 깊이까지 재귀하므로 Python과 같은 언어에서는 기본 호출 스택이 넘칠 수 있다.

알고리즘

(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]

두 행만 유지

핵심 아이디어

표의 i번째 행은 i-1번째 행과 그 행에서 자신보다 앞선 셀만 읽습니다. 한 행의 처리가 끝나면 그 위의 행은 다시는 읽지 않습니다. 따라서 완료된 행을 위한 prev와 채우는 중인 행을 위한 cur, 두 배열을 유지하고 각 행이 끝난 뒤 서로 바꾸세요. 점화식과 순서는 정확히 그대로입니다.

두 문자열의 공통 부분 수열은 어느 문자열이 먼저인지 상관하지 않으므로, 문자열을 서로 바꿔 행이 더 짧은 문자열을 따라가게 할 수 있습니다. 그러면 각 행에는 min(n, m) + 1개의 숫자만 들어갑니다. 가장 큰 입력에서도 백만 개의 셀 대신 1001개만 사용하면서, 작업량은 동일하게 10^6단계입니다.

각 행의 첫 번째 항목은 더 짧은 문자열의 빈 접두사를 나타내므로 0으로 유지해야 합니다. 정답은 마지막으로 완료된 행의 마지막 항목입니다.

알고리즘

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]

함정과 경계 사례

점화식은 짧으며, 대부분의 버그는 인덱스가 1만큼 어긋나거나 잘못된 위치에 일치 항목을 더하는 데서 발생합니다.

테이블 인덱스와 문자열 인덱스를 혼동하는 경우입니다. 행 0은 빈 접두사이므로 셀 dp[i][j]는 text1[i-1]과 text2[j-1]를 비교합니다.
일치할 때 dp[i-1][j-1]에 1을 더하는 대신 max(dp[i-1][j], dp[i][j-1])에 1을 더하는 경우입니다. 이렇게 하면 같은 글자를 두 번 사용할 수 있습니다. aa와 a를 비교하면 1이 아니라 2를 반환합니다.
두 포인터로 탐욕적으로 일치시키는 경우입니다. cab와 abc를 비교하면 두 c가 짝을 이루어 1을 반환하지만, ab는 2를 반환합니다.
아직 읽고 있는 행에 값을 쓰는 경우입니다. 두 행을 사용할 때 위쪽 행의 모든 값은 prev에서 가져와야 하며, cur[0]은 0으로 유지해야 합니다.
실수로 최장 공통 부분 문자열을 구하는 경우입니다. 부분 수열은 글자를 건너뛸 수 있지만, 부분 문자열은 그럴 수 없습니다.
길이가 1000인 문자열에 재귀를 사용해 메모이제이션하는 경우입니다. 호출 깊이가 2000에 도달해 Python의 기본 제한인 1000을 초과합니다.

자주 묻는 질문4

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

테이블을 사용하는 해법은 O(n × m) 시간이 걸립니다. 여기서 n과 m은 두 문자열의 길이입니다. 각 접두사 쌍마다 셀 하나를 채웁니다. 전체 테이블에는 O(n × m) 메모리가 필요하고, 두 행만 사용하면 O(min(n, m))이 필요합니다. 테이블 없이 단순 재귀를 사용하면 시간 복잡도가 지수적입니다.

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

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

최장 공통 부분 수열 자체를 어떻게 출력하나요?

표 전체를 채운 다음, dp[n][m]에서부터 역으로 따라가세요. 현재 셀의 두 글자가 일치하면 그 글자가 정답에 포함됩니다. 그 글자를 기록하고 대각선 왼쪽 위로 이동하세요. 일치하지 않으면 위쪽이나 왼쪽 이웃 중 더 큰 값을 가진 쪽으로 이동하세요. 마지막에 기록한 글자들을 뒤집으세요. 두 행만 사용하는 버전으로는 이렇게 할 수 없습니다. 이전 행들을 버렸기 때문입니다.

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

파일의 두 버전 간 차이를 비교하면 각 버전의 줄에서 가장 긴 공통 부분 수열을 찾습니다. 그 밖의 모든 줄은 추가되거나 삭제된 것으로 표시됩니다. 마찬가지로 한 문자열을 다른 문자열로 바꾸는 데 필요한 최소 삽입 및 삭제 횟수는 n + m - 2 × LCS입니다. 편집 거리는 문자 교체도 허용하므로, 각 셀에서 세 번째 선택지를 사용하는 자체 표를 만듭니다.

Python

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

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

text1 = "stone"
text2 = "longest"

기대값

Longest Common Subsequence

함수

제약 조건

예제

힌트

풀이

재귀로 첫 글자 비교하기

접두사 표를 채우세요

두 행만 유지

함정과 경계 사례

자주 묻는 질문4

비슷한 문제