LCS - 이차원 행렬을 이용한 다이나믹 프로그래밍

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

풀이

https://kbw1101.tistory.com/25
위 블로그에서 문제에 접근하는 방식이 설명되어 있다. 이차원 행렬 변수 dp에 대해서,

(1) 행과 열의 문자가 일치할 경우
= 좌 대각선 위의 값 + 1
→ 문자가 일치하므로, 이전까지의 LCS에 1을 더하기 위함이다. 즉, 이전까지의 LCS가 좌 대각선의 값임
(2) 행과 열의 문자가 일치하지 않을 경우
= 왼쪽 값, 위의 값 중 더 큰 값을 그대로 갖는다.
→ 문자가 불일치하므로, 비교한 문자가 포함되어 있는 직전 LCS의 값을 그대로 가져온다.

이러한 접근을 바탕으로 코드를 작성할 수 있다.
다이나믹 프로그래밍은 막상 문제에 대한 접근을 알면 코드가 간결한 경우가 많은 것 같다.

주의할 점은, for문이 중첩될 때 행과 열의 순서를 염두에 두고 코드를 작성해야 한다는 것이다.

다음의 코드는 정답이다.

import sys
input = sys.stdin.readline
str1 = list( map(str, input().rstrip()) )
str2 = list( map(str, input().rstrip()) )

dp = [ [0]*(len(str1)+1) for _ in range(len(str2)+1) ]  # str1(열) * str2(행)

for i in range(1, len(str2)+1): 			# str2(행)
    for j in range(1, len(str1)+1):			# str1(열)
        if str2[i-1]==str1[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max( dp[i][j-1], dp[i-1][j] )

print( dp[-1][-1] )

동기 민석이가 함께 이 부분에 대한 오류를 발견해주어 큰 산을 넘을 수 있었다~ 고맙습니다~