백준 문제 중 9251번, DP, ‘LCS’

백준 문제 중 9251번

https://www.acmicpc.net/problem/9251

문제

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

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

입력

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

출력

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

---

풀이

떠올려야할 핵심 아이디어가 두가지 정도 있는데 혼자서 생각해내기 상당히 어려워서 꽤나 고생했던 문제이다. 검색을 통해 해결했고 추후에 다시 풀어봐야 할 것 같다.

먼저 2차원 배열을 생성해 DP의 테이블로 활용한다. 핵심적인 아이디어는 이때 주어진 문자열 두개를 각각 A, B 라고 할때 A는 문자열 전체를 DP의 가로축, B는 문자열 중 문자 한개씩을 A와 스캔하여 DP의 각 세로축을 할당 하는것이다.

그리고 두번째 아이디어는 2차원 DP의 처음 가로축과 처음 세로축을 모두 0으로 초기화 하여 계산에 활용하는것이다.

코드의 흐름은 이렇다. 문자열A가 ‘ACAYKP’ 로 문자열 B가 ‘CAPCAK’로 라 하자.

문자열 A의 char들을 str1[a], 문자열 B의 char 들을 str2[b]라 하자. 문자열 A의 char들을 문자열 B 의 char들로 순서대로 스캔을 해나간다.

• str1[a]와 str2[b]가 같을때

str1[a]와 str2[b]가 같다면 해당 문자가 LCS가 될 수 있음을 뜻한다. 그리고 문자 str2[b-1]로 A를 스캔해 각 str1[a]에 대해 ‘str1[0] ~ str1[a-1]’와 ‘str2[0] ~ str2[b-1]’까지의 최대 LCS를 뜻하는 dp[a-1][b-1]에 str2[b]를 이어 붙일수 있음을 의미한다. 그러므로 dp[a][b] = dp[a-1][b-1] + 1 을 대입 하면된다.

예를 들어 아래 표에서 dp[4][2] 에 해당하는 2가 의미하는 바는 다음과 같이 말할 수있다. 문자열 A의 ‘AC’ 와 문자열 B의 ‘CAPC’ 까지의 LCS의 길이는 2이다. 그리고 dp[4][3]에 해당하는 3을 구할때는 다음과 같이 할 수 있다. 문자열 A의 ‘ACA’ 와 문자열 B의 ‘CAPCA’의 마지막 문자가 같고, (4,2)에 해당하는 LCS를 포함하므로 dp[5][3] = dp[4][2] + 1이 된다.

dp	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	[2]	2	2	2	3
A	0	1	2	[3]	3	3	3
K	0	1	2	3	3	4	4

• str1[a]와 str2[b]가 다를때
  str1[a]와 str2[b]가 다르다면 해당 문자가 LCS가 될 수 없음을 뜻한다.

이때는 str2[b-1]로 A를 스캔해 각 str1[a]에 대해 ‘str1[0]~str1[a]’와 ‘str2[0] ~ str2[b-1]’까지의 최대 LCS를 뜻하는 dp[a][b-1],

그리고 str2[b]로 A를 스캔해 각 str1[a]에 대해 str1[0]~str1[a-1]와 str2[0] ~ str2[b]까지의 최대 LCS를 뜻하는 dp[a-1][b] 중 최대값을 dp[a][b]에 대입하면 된다.

dp	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	[1]	2	2	2	2
P	0	[1]	(1)	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

다시 말해 dp[2][2]에 해당하는 1을 구하는법은, ‘A’와 ‘CAP’의 LCS인 dp[2][1] = 1 그리고 ‘AC’와 ‘CA’의 LCS인 dp[1][2] = 1 중 최대값을 대입하면 된다.

그리고 여기서 추가적으로 인덱스 계산의 편의를 위해 dp[i][0] 축과 dp[0][j] 축을 모두 원소를 0으로 가지고 계산하는편이 더 용이하다.

이를 코드로 나타내면 다음과 같다.

str1 = input()
str2 = input()

n, m = len(str1), len(str2)

 #  dp[i][0] 축과 dp[0][j] 축을 모두 원소를 0으로 
dp = [[0]*(m+1) for _ in range(n+1)]

for i in range(1,n+1):

    for j in range(1,m+1):

         # 문자열이 같다면 LSC로 올 수 있음
        if str1[i-1] == str2[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1

         # 문자열이 다를때는 이전의 값들 중 최대값을 가져옴
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

print(dp[n][m])

4