[백준] LCS(최장 공통 부분 수열)

핵심 알고리즘(dp)

이중 for 문으로 모든 문자열을 비교하면서

 

first[i]==second[j] 이면 dp[i-1][j-1]+1

→ 두 문자열에서 같은 문자가 추가 됐으므로 (이전 최장 공통 부분 수열)+1

 

first[i]!=second[j] 이면 max(dp[i-1][j],dp[i][j-1])

→ 이전의 최대 공통 부분 수열 유지

 

first=input()
second=input()
dp=[[0]*(len(second)+1) for _ in range(len(first)+1)]
for i in range(1,len(first)+1):
    for j in range(1,len(second)+1):
        if first[i-1]==second[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])

# 최장 공통 (연속)수열
#     A C A Y K P
#   0 0 0 0 0 0 0
# C 0 0 1 0 0 0 0
# A 0 1 0 2 0 0 0
# P 0 0 0 0 0 0 1
# C 0 0 1 0 0 0 0
# A 0 1 0 2 0 0 0
# K 0 0 0 0 0 1 0


# 최장 공통 부분 수열
#     A C A Y K P
#   0 0 0 0 0 0 0
# C 0 0 1 1 1 1 1
# A 0 1 1 2 2 2 2  -> C와 AC의 최장 공통 부분 수열 +1 = CA와 ACA의 최장 공통 부분 수열
# P 0 1 1 2 2 2 3  
# C 0 1 2 2 2 2 3
# A 0 1 2 3 3 3 3
# K 0 1 2 3 3 4 4