백준 9251: LCS (골드 IV) - DP

9251번: LCS

Longest Common Subsequence, 최장 공통 부분 수열 문제는 두 수열이 주어지면, 공통되는 부분수열 중 최고길이를 가지는 수열을 찾는 문제이다. 해당 문제는 골드 V이지만, 한 번이라도 경험해보지 않으면 생각해내기 정말 어려운 문제인 것 같다. 최장 증가하는 부분수열을 구했던 문제와 동일한 난이도였지만, 어떻게 풀어내야할 지 감 조차도 안왔다. (내가 멍청한거 일수도..) 결국엔 이번 포스팅은 내가 풀어낸 방법이 아닌 유튜브 강의와 블로그를 참고하여 이해한 것을 정리해보는 느낌이라고 생각해도 무방하다.

문제요약

두 문장 "ACAYKP",  "CAPCAK"가 주어질 때 이 두 문장의 공통 부분 수열 중 길이가 가장 긴 부분수열은 "ACAK"이다.

ACAYKP    CAPCAK

이 때의 길이를 출력하는 문제.

솔루션

브루트포스로 두 문장의 모든 부분수열을 구해, 똑같은 것 중 가장 길이가 긴 것을 찾을 수 있으나, 이는 O(2^n)이라는 최악의 시간복잡도를 가진다. 문장의 길이가 최대 1000인것을 고려할 때 2^1000 시간을 가진다. 말이 안되는 천문학적인 수치이다. 

길이가 1000이라는 것은 최대 O(N^2)을 사용해야한다고 생각해도 좋다. DP를 이용하여 O(N^2)으로 풀어낼 수 있다. 

How?

해당 문제는 2차원 리스트를 통해 풀어낸다. 각 축은 각 문장이다. 즉, 다음과 같은 그림으로 셋팅된다.

초기상태의 DP맵

i는 첫 번째 문장의 인덱스, j는 두 번째 문장의 인덱스이다. 그리고 DP[i][j]는 첫 문자열의 1~i번째 문자와 두 번째 문자열 1~j번째까지의 문자를 비교하였을때, 공통부분의 문자열의 최대 길이라고 정의한다.

알고리즘 순서는 행단위로 진행된다고 생각하자. 

i=0

i = 0, before

첫 번째 문자열의 부분 수열 "A"를 두 번째 문자열의 부분수열인 "C", "CA", "CAP", 'CAPC", "CAPCA", "CAPCAK"의 순서로 모두 비교한다. 일단 비교 대상이 "A" 한 글자이므로 최대 공통 부분수열 길이 1을 초과할 수 없다. 두 번째 문자열의 부분수열안에 "A"가 포함되어있으면 그때의 최장길이는 1인것이다.  정정, 첫 번째 문자열의 부분수열이 두 번째 문자열의 부분 수열에 포함여부를 따지는게 아니라, 양 방향으로 따져야한다. i=1일 경우에서 부가설명한다. 따라서 다음과 같은 결과를 가져온다.

i = 0, after

---

i=1

i = 1, before

첫 번째 문자열의 부분 수열 "AC"에 대해 탐색한다. 마찬가지로 두 번째 문자열의 부분수열 "C", "CA", "CAP", 'CAPC", "CAPCA", "CAPCAK"을 비교한다.

여기서 주의해야할 점이 있다. "AC"와 "C"의 공통수열을 확인 할 때, "AC"는 "C"에 포함되어있지 않으므로 0인 것이 아니라, 반대로 "C는 "AC"의 부분수열이기 때문에 최장 공통 부분수열은 1이 되는 것이다. 놓치지 말자.

그리고 길이가 2가 되는 순간은 "AC"와 "CAPC"가 만날 때 최초로 2가 된다. "CAPC"의 부분 수열에 "AC"가 있기 때문이다.
따라서 다음과 같은 결과를 가져온다.

i = 1, after

위 과정을 끝까지 반복하면 최종 맵은 다음과 같다.

최종 완성된 맵

 

점화식 도출

여기서 현재 Dynamic Programming 알고리즘이 적용되었는가? 아직 적용되지 않았다.

하지만 미니 케이스를 통해 다음과 같은 규칙을 발견할 수 있다.

if str1[i-1] == str2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
        
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

해당 점화식을 통해 DP로 문제를 풀어내면 최종 정답이다.

 

소스코드

import sys
input = sys.stdin.readline

dp = [[0 for _ in range(1001)] for _ in range(1001)]

str1 = input().strip()
str2 = input().strip()

len_str1 = len(str1)
len_str2 = len(str2)

for i in range(1, len_str1+1):
    for j in range(1, len_str2+1):
        if str1[i-1] == str2[j-1]:
            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_str1][len_str2])

 

느낀점

DP문제는 무궁무진하다는 느낌이 든 것이, 시뮬레이션을 통해 몇 가지 경우를 구하고, 규칙을 찾아 점화식을 도출하여 풀어내는 것, 애초에 2차원 배열로 풀어내본다는 것을 생각하는거 자체가 정말 어렵게 느껴진다. 

이 문제도 과연 골드 V수준이 맞나? 싶기도 하다, 다른 그래프 탐색에 동일한 난이도는 쉽게 풀어냈기 때문이다.

DP는 반년은 투자해야 익숙해지겠다.