[맛있는물회] [파이썬] <백준 알고리즘> 9251번 "LCS" (최장 공통 부분 수열 찾기)

문제 조건

---

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

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

 

Input

---

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

 

Output

---

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

 

생각한 아이디어

---

아주 유명한 LCS 문제이다.

맨첨에 LIS 알고리즘 푸는 방법으로 접근했다.

1차원 DP로 그렇게 했더니 테스트 케이스는 다 맞았는데 

예를들어

ABCD

DBCA

같은 경우는 A가 젤 끝 A와 다시 비교되어서 B를 다시 보지 못한다.

 

따라서 dp가 1차원이 아닌 2차원이 되어야한다.

그래서 새로운 알고리즘으로 다시 접근해야했다.

 

알고리즘의 원리에 대해서는 다른 블로그 포스팅에서 너무 잘 나와있어서 참고하기가 좋았다.

2차원 DP를 만들면서

for y in range(1,len(arr2)+1):

      for x in range(1,len(arr1)+1):

         if arr2[y-1]==arr1[x-1]:

            dp[y][x]=dp[y-1][x-1]+1

         else:

            dp[y][x]=max(dp[y-1][x],dp[y][x-1])

 

이렇게 수행해주면 된다.

즉, 값이 같다면 이전 (좌측 대각선 값)에 +1을 해주고

값이 다르다면 왼쪽값과 위쪽값의 최대값을 가지고 오면된다.

 

나중에 LCS 알고리즘에 대해 다시 한번 정리해야겠다!

 

 

소스코드

import sys
from collections import deque
import copy
input=sys.stdin.readline
INF=sys.maxsize

if __name__ == "__main__":
   arr1=list(input().rstrip())
   arr2=list(input().rstrip())
   dp=[[0 for _ in range(len(arr1)+1)] for _ in range(len(arr2)+1)]
   for y in range(1,len(arr2)+1):
      for x in range(1,len(arr1)+1):
         if arr2[y-1]==arr1[x-1]:
            dp[y][x]=dp[y-1][x-1]+1
         else:
            dp[y][x]=max(dp[y-1][x],dp[y][x-1])
   print(dp[-1][-1])

 

*파이썬 문법 정리