[백준] 9251번 LCS (Python)

https://www.acmicpc.net/problem/9251

9251번: LCS

 

문제

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

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

 

입력

 

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

출력

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

 

seq1=input()
seq2=input()

dp = [[0]*(len(seq1)) for _ in range(len(seq2))]

for i in range(len(dp)):        # i means row length seq2
    for j in range(len(dp[i])): # j means col length seq1
        if i >= 1 and j >= 1:
            if seq1[j]==seq2[i]:
                dp[i][j] = (dp[i-1][j-1]+1) 
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        elif i==0 and j==0:
            if seq2[i]==seq1[j]:
                dp[i][j] = 1
        elif i == 0:
            if seq2[i]==seq1[j]:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i][j-1]
        elif j == 0:
            if seq1[j]==seq2[i]:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i-1][j]

print(dp[len(seq2)-1][len(seq1)-1])

이전에 풀었던 계단문제와 같은 DP유형 문제이며

점화식을 이용하지 않은 문제 중 가장 잘 알려진 예 중 하나라 생각한다.

 

문제풀이

문제의 시작부분은 계단 오르기와 유사하게 입력받은 만큼의 캐시를 미리 생성한다.

계단 오르기와 다른 점은 문자열 각각을 비교하기 위해 [문자열1 * 문자열2] 크기의 2차원 리스트를 생성한다는 점이다.

 

대부분의 DP문제를 1차원 혹은 2차원 리스트 둘 중 하나의 형태로 캐시를 생성하므로

문제를 풀기 전 이를 미리 결정하고 가야한다.

이번 문제는 문자열1과 문자열2의 길이가 다른데 이런 경우 대게 2차원 리스트를 생성해야 한다.

 

 

DP문제는 언제나 패턴을 찾아내는 게 가장 중요하다

for i in range(len(dp)):        # i means row length seq2
    for j in range(len(dp[i])): # j means col length seq1
        if i >= 1 and j >= 1:
            if seq1[j]==seq2[i]:
                dp[i][j] = (dp[i-1][j-1]+1) 
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

먼저 각 문자열을 문자별로 순회하며 문자열1과 문자열2를 각각 비교할 수 있게 된다.

따라서 dp[i][j]는 문자열1의 i번째 원소 그리고 문자열2의 j번째 원소까지 체크했을 때의 LCS이다.

 

나머지는 초기값인 첫 번째 문자일 경우에 대한 테스트케이스만 고려하면 문제를 풀 수 있다.