백준 9251번: LCS (Python)

접근

몇 번 코드를 작성해보다가 전혀 답에 근접해지지 않아 다른 분들의 풀이를 참고하여 풀게 되었다.

다음과 같은 표를 작성해보자.

문자	0	C	A	P	C	A	K
0	0	0	0	0	0	0	0
A	0
C	0
A	0
Y	0
K	0
P	0

표시된 칸부터 순환하며 칸을 채우되, 칸을 채우는 조건은 아래와 같다.

dp[i][j] 칸을 채울 때,

1. i행 문자와 j열 문자가 같다면, dp[i - 1][j - 1] + 1
2. i행 문자와 j열 문자가 다르다면, max(dp[i][j - 1], dp[i - 1][j]

와 같은 방법으로 채워나가면 된다.

두번째 행까지 채울 경우 다음과 같은 결과를 얻을 수 있다.

문자	0	C	A	P	C	A	K
0	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0
Y	0
K	0
P	0

i 행과 j 열 문자가 같은 경우만 음영으로 표시하였다. 이와 같이 풀어가다 보면,

문자	0	C	A	P	C	A	K
0	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4

와 같은 결과를 얻을 수 있다.

이 표에서 dp[i][j]가 의미하는 것은 해당들끼리 비교했을 때의 최장 공통 부분 수열의 길이이다. 예를 들어 dp[5][3] = 2 는 문자 ACAYK와 CAP의 공통 수열인 CA의 길이 2를 나타낸다.

참고 : LCS(최장 공통 부분 수열) 알고리즘

코드

import sys

m = [0] + list(sys.stdin.readline().rstrip())
n = [0] + list(sys.stdin.readline().rstrip())
dp = [[0 for _ in range(1002)] for __ in range(1002)]
for i in range(1, len(m)):
    for j in range(1, len(n)):
        if m[i] == n[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[len(m) - 1][len(n) - 1])

더 생각해 볼 것?

왜 저런 표에 저러한 결과 값이 나오는지 이해한 것 같지만 여전히 완전히 받아들이지는 못한 느낌이다. 조금 더 생각을 깊게 해보아야 할 것 같다.