[ 백준 9251 해설 ] ( python ) LCS

 

📚 LCS

 

문제

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

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

 

입력

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

 

출력

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

 

예제 입력 1 복사

ACAYKP
CAPCAK

예제 출력 1 복사

4

 

 

✍ 접근

• 가장 긴 공통 부분 수열
• dp를 활용하여 점화식을 세워 풀 수 있다

 

 

 

 

 

정답코드 

# ✨ 입력
import sys
input = sys.stdin.readline
A = ' '+input().rstrip()
B = ' '+input().rstrip()
len_A = len(A)
len_B = len(B)

dp = [[0]*(len_B) for _ in range(len_A)]

# ✨ 점화
for i in range(1,len_A):
    for j in range(1,len_B):
        if A[i] == B[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[-1][-1])

해설

입력

• 문제에서 나온 값을 입력받는다
• 입력받을 때 점화식으로 i-1, j-1을 사용할 것이기 때문에 앞에 ' ' 를 넣어주었다.

점화

• 세로에 A(ACAYKP) 가로에 B(CAPCAK)가 있는 board(dp)를 만들고
• for문으로 A/C/A/Y/K/P를 하나하나 돌면서 각각 B 전체와 비교한다.
  • 만약 A/C/A/Y/K/P와 B의 한 부분이 맞으면 그 부분은 dp[i-1][j-1]에서 1을 더해준다
    = 동일 위치를 두 번 확인하면 안되므로 i-1, j-1을 해주는 것
  • else
    dp[i][j]는 B의 바로 전 값에서 올 때의 길이 / A의 바로 전 값에서 올 때의 길이를 비교하여 큰 값을 넣어준다
    = 최장길이를 구하는 것이기 때문에

 

 

 

 

 

⭐ 배움

• dp + 문자열