[백준 9251번] LCS

first = list(input())
second = list(input())

first_len = len(first)
second_len = len(second)

dp = [[0]*(first_len+1) for _ in range(second_len+1)]

for i in range(second_len):
    for j in range(first_len):
        if second[i] == first[j]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
            
print(dp[second_len-1][first_len-1])

💡 LCS (Longest Common Subsequence)란?

2개 이상의 문자열에서에서 공통으로 나타나는 부분 문자열 중 가장 긴 문자열을 의미한다.
LCS은 대표적으로 DNA의 공통 염기서열을 찾아 데이터를 압축하거나 무선 서명을 통해 휴대폰에서 사용자를 인증할 때 사용됨.

이번 문제는 2가지 수열이 주어졌을 때, 두 수열의 부분 수열 중에서 가장 긴 공통 부분 수열을 찾는 문제(LCS)이다.

 

이 문제는 LIS 문제와 굉장히 유사하여 DP 알고리즘을 사용해야 한다는 것은 대충은 짐작하고 있었는데, 하나의 수열이 아니라 두 개의 수열이 주어지고, 이들을 비교하면서 최대 길이를 구해야 하기 때문에 2중 반복문을 사용하면서 두 수열을 비교해야 한다는 것까지 생각해낼 수 있었다.

 

위 문제는 다음과 같이 2차원 DP 테이블을 선언 및 초기화한 후에

하나의 수열의 첫번째 값부터 다른 수열의 값들을 비교해가며 풀이하는데, 다음과 같은 점화식을 사용하여 DP 테이블을 채울 수 있다.

 

1. 두 번째 수열의 현재 원소의 값(second[i])과 첫 번째 수열의 현재 원소의 값(first[j])이 같은 경우, 부분 수열의 길이를 1 더해준뒤 저장한다.( dp[i][j] = dp[i-1][j-1] + 1 )

2. 원소의 값이 다른 경우, 두번째 수열의 원소를 제외했을 때의 최대 값(dp[i-1][j])와 첫번째 수열의 원소를 제외했을 때의 최대 값(dp[i][j-1]) 중에 더 큰 값을 저장한다. ( dp[i][j] = max(dp[i-1][j],dp[i][j-1] )

		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
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	2
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

문제에 대한 DP 테이블 설계와 점화식을 도출하기 어려워 다른 사람의 풀이를 참고한 문제이지만, DP 문제를 풀이할 때는 표를 그려가며 하나씩 채워가면서 패턴을 찾아가는 것이 중요하다는 것을 다시 한번 깨닫게 해준 문제였다 :)