최장 공통 부분 수열

부분 수열은 문자의 순서는 유지하지만 일부 문자를 건너뛸 수 있습니다. 'abcde'에서 'ace'는 만들 수 있지만 'aec'는 만들 수 없습니다.

두 문자열이 주어졌을 때, 최장 공통 부분 수열은 두 문자열에 모두 나타나면서 상대적인 순서가 같은 가장 긴 수열입니다.

두 문자열의 접두사들을 비교하세요. 두 문자열의 길이를 기준으로 만든 2차원 표를 사용하면 익숙한 격자 DP 문제로 바뀝니다.

dp[i][j]를 A의 처음 i개 문자와 B의 처음 j개 문자로 만들 수 있는 LCS의 길이라고 하겠습니다.

A[i-1]이 B[j-1]과 같다면, 그 공통 문자가 LCS를 한 글자 늘립니다. 대각선 값인 dp[i-1][j-1]에 1을 더하세요.

문자가 다르면 어느 한 문자열에서 문자 하나를 제거하고 더 나은 결과를 유지하세요. 두 이웃 값 중 최댓값을 선택합니다.

빈 접두사에는 공통된 문자가 없으므로 LCS의 길이는 0입니다. 0번 행과 0번 열은 모두 0으로 유지합니다.

n+1 x m+1 크기로 표를 만들면 0으로 된 경계 행과 열을 얻을 수 있습니다. 덕분에 가장자리에서 번거로운 범위 확인을 하지 않아도 됩니다.

i와 j를 1부터 증가시키며 반복하세요. 각 칸에는 위쪽, 왼쪽, 대각선의 값만 필요하며, 이 값들은 이미 계산되어 있습니다.

전체 LCS의 길이는 모서리에 있습니다. 모든 칸을 채운 뒤 정답은 dp[n][m]입니다.

모든 칸을 한 번씩 확인하므로 시간과 메모리 사용량은 O(n 곱하기 m)입니다. 문자열 길이가 수천 자 정도인 경우에도 충분히 처리할 수 있습니다.

현재 문자 A[i-1]과 B[j-1]이 같습니다. 어떤 갱신이 올바를까요?

n+1 x m+1 표를 만드세요. 문자가 일치하면 대각선 값에 1을 더하고, 그렇지 않으면 이웃 값 중 최댓값을 선택합니다. 모서리에 길이가 있습니다. 🔗