[🥇5 / 백준 9251 / 파이썬] LCS

 

9251번: LCS

 

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때,

모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

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

입력

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

출력

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

 

예제 입력 ACAYKP CAPCAK

예제 출력 4

 

풀이

 

이번엔 숫자가 아닌 문자열에서 부분 수열의 최장 길이를 찾는 문제이다.

 

숫자의 대소 비교가 불가능하므로 2차원 배열을 만들어 모든 문자열을 한 번씩 대조해준다.

 

공통 부분수열의 길이를 구하는 핵심은, 이번에 비교한 문자열이 다르다고 해서

 

이전에 구했던 최장 길이가 달라지지 않는다는 점이다.

 

 

예시 코드

 

a = "-" + "ABABABABACAB"
b = "-" + "ABC"

dp = [[0 for i in range(len(a))] for i in range(len(b))]
# 인덱스 언더플로우가 되지 않게 1만큼 더 길게 만든다.

for i in range(1,len(b)):
    for j in range(1,len(a)):
        if b[i] == a[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[-1][-1])
for i in dp:
    print(*i)

 

a와 b의 문자열을 바꾸어 가며 비교 배열이 어떻게 되는지 보도록 하자.

 

 

정답 코드

 

a = "-" + input()
b = "-" + input()

dp = [[0 for i in range(len(a))] for i in range(len(b))]

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