[Python] 백준 (LCS 최장 공통 부분 수열) 9251번

문제

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

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

입력

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

출력

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

예제 입력 1

ACAYKP 
CAPCAK

예제 출력 1

4

---

문제 풀이

문제를 처음 본 생각: 무슨 말이지...? 결국 부분 수열 중 길이가 가장 긴 것을 구하자!

• LCS에는 최장 공통 문자열(Longest Common Substring)과 최장 공통 부분 수열(Longest Common Subsequence)이 있다.

• 최장 공통 문자열 VS 최장 공통 부분 수열

• 최장 공통 문자열 (Longest Common Substring)	최장 공통 부분 수열 (Longest Common Subsequence)
  ABCD                               ->             CD ACDEF	ABCD                                   ->             ACD ACDEF

• 비교해보자 a = 'ACAYKP'  b = 'CAPCAK '라면
• a = A, b = C 일 때 LCS는 0(같은 값이 아님)
• a = A, b = CA 일 때 LCS는 1
• ...
• a = AC, b =C일때 LCS는 1
• 반복하며 표를 채운다.
• matrix

• a(i)       b(j)	(0)	(1)  C	(2)  A	(3)  P	(4)  C	(5)  A	(6)  K
  (0)	0	0	0	0	0	0	0
  (1)  A	0	0	1	1	1	1	1
  (2)  C	0	1	1	1	2	2	2
  (3)  A	0	1	2	2	2	3	3
  (4)  Y	0	1	2	2	2	3	3
  (5)  K	0	1	2	2	2	3	4
  (6)  P	0	1	2	3	3	3	4

• a, b를 반복하며 추가되는 문자가 같다면
  matrix[i][j] = matrix[i-1][j-1] + 1      #두 글자가 추가되기 전 가장 큰길이에 1을 더함
  다르다면
  matrix[i][j] = max(matrix[i][j-1], matrix[i-1][j]) # 기존 주어진 문자열로 만들 수 있던 최대 길이

• 예를 들어 빨간색 글자 matrix[2][4]는 현재 AC, CAPC의 상태이고 추가된 문자 C가 일치하는 것이기 때문에 A, CAP상태일때 값에서 1을 더해주면 된다. (matrix[1][3]위치)
• 파란색 글자 matrix[2][5]는 현재 AC, CAPCA상태이고 추가된 문자가 같지 않기 때문에 a와b중에 a가 추가 되지 않은 경우(A, CAPCA)나 b가 추가되지 않은 경우(AC, CAPC)를 비교하여 최대값을 넣는다.

import sys

a = sys.stdin.readline().rstrip()
b = sys.stdin.readline().rstrip()

LCS = [[0]*(len(b)+1) for _ in range(len(a)+1)]
for i in range(0,len(a)+1):
    for j in range(0, len(b)+1):
        if i == 0 or j == 0:
            LCS[i][j] == 0
        elif a[i-1] == b[j-1]:
            LCS[i][j] = LCS[i-1][j-1]+1
        else:
            LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])

print(LCS[-1][-1])

---

제출했을 때 런타임 에러를 마주했다. 이유를 찾아보니 LCS를 0으로 선언해주는 과정에서 len(a)와 len(b)의 위치가 바뀌어 있었던것 LCS = [[0]*(len(a)+1) for _ in range(len(b)+1)] 이렇게 써뒀었음... 당연히 두번째 for문에서 돌리는 b의 갯수만큼 열을 만들어 주어야함. 헷갈리지 말자