LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.
예제 입력 1
ACAYKP
CAPCAK
예제 출력 1
4
제출 코드
a = input()
b = input()
d = [[0]*(len(b)+1) for _ in range(len(a)+1)]
for i in range(1,len(a)+1):
for j in range(1,len(b)+1):
if a[i-1] == b[j-1]:
d[i][j] = d[i-1][j-1] + 1
else:
d[i][j] = max(d[i-1][j], d[i][j-1])
print(d[-1][-1])
문자열 a와 문자열 b에서 문자를 하나씩 늘려가면서 모든 경우의 수를 비교한다,
a:A
b:C
i = 1, j = 1인 경우
a[0] != b[0] (A != C)
d[1][1] = max(d[0][1], d[1][0]) => 0
a:A
b:CA
i = 1, j = 2인 경우
a[0] == b[1] (A == A)
d[1][2] = d[0][1] + 1 => 1
a:A
b:CAP
i = 1, j = 3인 경우
a[0] == b[2] (A != P)
d[1][3] = max(d[0][3], d[1][2]) => 1
...
a:A
b:CAPCAK
i = 1, j = 6인 경우
d[1][6] = 1
a:AC
b:C
i = 2, j = 1인 경우
a[1] == b[0]
d[2][1] = d[1][0] +1 => 1
a:AC
b:CA
i = 2, j = 2인 경우
a[1] != b[1] (C != A)
d[2][1] = d[1][0] +1 => 1
...
이런 식으로 비교해서 가장 긴 수열을 찾으면 된다
a와 b에 가장 최근에 추가한 문자가 같을 때,
두 문자가 추가되기 전에 구한 최장 수열의 길이에서 +1을 한다.
ex) a: ACA b: CA 는 최근에 추가한 문자가 A로 같으므로,
문자가 추가되기 전 a: AC b:C 인 경우 최장 수열의 길이 = 1에서 +1을 한 2가 답이 된다.