[ 백준 9252 해설 ] ( python ) LCS 2

 

📚 LCS 2

 

 

문제

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

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

 

입력

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

 

출력

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

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

 

예제 입력 1 복사

ACAYKP
CAPCAK

예제 출력 1 복사

4
ACAK

 

 

 

✍ 접근

• 가장 긴 공통 부분 수열
• dp를 활용하여 점화식을 세워 풀 수 있다
• 점화식에 값이 아닌 지나온 순서도 저장해준다

 

 

 

 

 

정답코드 

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

len_A = len(A)
len_B = len(B)

board = [['']*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]:
            board[i][j] = board[i-1][j-1] + A[i]
        else:
            if len(board[i-1][j]) < len(board[i][j-1]):
                board[i][j] = board[i][j-1]
            else:
                board[i][j] = board[i-1][j]
                
res = board[-1][-1]

if len(res) != 0:
    print(len(res))
    print(res)
else:
    print(0)

해설

입력

• 문제에서 나온 값을 입력받는다
• 입력받을 때 점화식으로 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]에서 맞는 값(A[i])을 더해준다.
  • else
    dp[i][j]는 B의 바로 전 값에서 올 때의 길이 / A의 바로 전 값에서 올 때의 길이를 비교하여 길이가 더 긴 값을 가져와서 업데이트해준다

 

 

 

 

 

⭐ 배움

• dp + 문자열 + 경로저장