[알고리즘] 9251번 LCS

---

코드

import sys

str1 = sys.stdin.readline().strip()
str2 = sys.stdin.readline().strip()
dp = [0] * (len(str2))

for i in range(len(str1)):
    temp = 0
    for j in range(len(str2)):
        if dp[j] > temp:
            temp = dp[j]

        elif str1[i] == str2[j]:
                dp[j] = temp + 1
print(max(dp))

다이나믹 프로그래밍의 유명한 예제 LCS이다.
dp 배열을 하나 생성하여 LCS의 길이를 해당 배열에 저장하도록 하였다.
temp라는 변수에 str1의 문자 순서의 LCS의 길이를 저장한다.

동작은 위와 같다. 길이가 커져도 한 문자에 하나씩 길어지는 것을 유의하고 코드를 작성하였다.
각 반복문마다 temp를 0으로 초기화하고 기존 dp 테이블에서 temp보다 큰 값이 있다면 그 값을 temp에 저장하고 해당 값을 이용하여 Common Character가 있는 경우 temp보다 1 큰 값을 저장한다.
문자가 같은 지를 확인하는 코드를 temp 변수의 값을 변경하는 것보다 위에 두게 되면 똑같은 문자가 연속해서 오는 경우 오류가 발생하기 때문에 이에 유의해야 한다.