[9251] LCS

문제

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

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

 

입력

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

 

출력

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

 

예제 입력 1

ACAYKP
CAPCAK

 

예제 출력 1

4

 

풀이

이 문제는 오늘 알고리즘 스터디에서 종우가 설명해줘서 완벽히 이해한채로 푼거라 거의 복습에 가까웠다

dp 테이블을 이용해서 구하는 것인데, 두 문자열 각각보다 1만큼 큰 이차원배열을 0으로 초기화 시킨 상태에서 행마다 검사하면서

각 문자가 같으면 dp[i-1][j-1] + 1 값으로 채워주고 다르다면 max(dp[i-1][j], dp[i][j-1])로 초기화 해주는 것이다

그렇게 끝까지 검사해나가면 가장 마지막 배열에 값이 LCS의 길이가 되는 것이다

오늘 설명을 들으면서 dp의 중요한 점은 점화식을 잘 세우는 것이 중요한 것 같았다. 앞으로 다이나믹프로그래밍 관련 문제를 풀 때 문제에서 요구하는 사항에 대하여 점화식을 한번 세워보는 방식으로 접근해야겠다고 생각했다.

 

str1 = input()
str2 = input()

dp = [[0 for _ in range(len(str1) + 1)] for i in range(len(str2) + 1)]

for i in range(1, len(str2)+1):
    for j in range(1, len(str1)+1):
        if str1[j-1] == str2[i-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])