(Python/🥇4)백준알고리즘 9251번: LCS

문제바로가기

백준 알고리즘 LCS

 

문제:

 

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

 

문입력:

 

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

출력:

 

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

 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
sys.setrecursionlimit(10**6)

lst1 = [ i for i in sys.stdin.readline().rstrip()]
lst2 = [ i for i in sys.stdin.readline().rstrip()]

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

 

이 문제는 LIS 문제이면서 DP를 사용하는것 같다. 이게 이 전 문제인 전깃줄 보다 어려운거같다.

 

ACAYKP
CAPCAK

lst1, lst2 에 각각 저장하고, dp 도 2차원 배열로 해준다. 그 이유는

lst1 이 1일때 lst 2에 전 길이를 비교하면서 dp를 채워 나가는 식이다.

 

예를 들어보면 i = 1 일대 j 는 1 ~ 끝까지 돌게된다 그럼 

[0,0,1,1,1,1,1] 이렇게 나오게되는데 이유는

A
CAPCAK

이렇게 생각하고 LIS를 생각해보라 그러면 0번인덱스 일때는 C 이기 때문에 0이고 1번인덱스에서 A가 나와 최댓값이 1 로 갱신된다. 그 다음 인덱스 들은 A가 앞에 있었기 때문에 최댓값인 1로 유지된다.

 

i가 2일때 다음은 C 차례인다. C일때도 j 1~ 6 에 있는지 비교한다. 그러면 C와C, C와A, C와P ... 이런식으로 같은걸 찾게된다.

만약에 같다면 [i-1][j-1] 에서 +1 을 해주면된다.

 

만약에 같지 않다면

dp[i-1][j],dp[i][j-1]

중에 최댓값으로 해주면된다. 아래 꺼를 기준으로 CAP 에서 P 일때 C와 다르다. 

그러면

A 한개일때의 최댓값과

AC 2개일때의 지금까지의 값 중에 최댓값으로 갱신시켜주는것이다.

 

AC
CAPCAK

 

[

[0,0,1,1,1,1,1] 

[0,1,1,1,2,2,2]

]

이렇게 말이다.

 

그리고 마지막에 뽑아주면 된다

역시 dp어렵다 

 

이런 문제를 LCS이라고 부른다 따로 정리를 해보도록 하겠다.