8 / 16강

두 문자열의 공통 순서 찾기

두 문서에서 글자 순서를 유지한 채 공통으로 남길 수 있는 부분을 찾으려 합니다. 부분 수열은 중간 글자를 건너뛸 수 있지만 순서는 바꿀 수 없습니다. 연속된 글자만 고르는 부분 문자열과는 구분해야 합니다.

예를 들어 ABC에서 AC는 부분 수열입니다. 하지만 B를 건너뛰었으므로 부분 문자열은 아닙니다. 두 문자열의 공통 부분 수열 중 가장 긴 것을 LCS라고 합니다.

두 위치를 상태로 씁니다

dp[i][j]를 첫 문자열의 앞 i글자와 둘째 문자열의 앞 j글자 사이의 LCS 길이라고 정합니다.

• 마지막 글자가 같으면 그 글자를 함께 씁니다. dp[i-1][j-1] + 1입니다.
• 다르면 한쪽 마지막 글자를 빼는 두 경우를 비교합니다. max(dp[i-1][j], dp[i][j-1])입니다.
• 한쪽이 빈 문자열이면 공통으로 고를 글자가 없으므로 0입니다.

a, b = "ABCD", "ACBD"
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 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])
print(dp[-1][-1])

결과는 3입니다. ABD나 ACD를 공통으로 고를 수 있습니다. 코드는 길이만 구합니다. 실제 글자까지 구하려면 어느 이전 칸에서 왔는지 따라가며 복원해야 합니다.

표를 만드는 작은 함정

[[0] * 너비] * 높이로 만들면 여러 행이 같은 리스트를 가리킵니다. 한 행을 바꿨는데 다른 행도 바뀔 수 있습니다. 위 코드처럼 행마다 새 리스트를 만들어야 합니다. 배열과 참조에서 본 공유 문제입니다.

두 문자열 길이가 n, m이면 표의 칸 수가 (n+1)(m+1)개입니다. 시간과 공간은 O(nm)입니다. 길이만 필요하다면 이전 행과 현재 행만 보관해 공간을 줄일 수 있습니다.

확인 문제

ABC와 AC의 LCS 길이와 최장 공통 부분 문자열 길이는 각각 얼마인가요?