[백준/python] 9251번: LCS

문제

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

9251번: LCS

---

문제 요약

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

 

주어진 두 문자열의 LCS길이를 출력한다.

 

예) ACAYKP 와 CAPCAK의 LCS는 ACAK가 된다.

---

코드

A = input()
B = input()

dp=[[0] * 1001 for _ in range(1001)]
# dp[i][j]는 인덱스 i번째까지의 A 문자열과 인덱스 j번째까지의 B 문자열 사이의 가장 긴 공통 부분 수열의 길이
# 한 쪽 문자열이 비었을 때 LCS값은 0이기 때문에 dp[i][0]와 dp[0][j]는 항상 0

ans = 0
# 최대 LCS 길이를 저장할 변수

for i in range(1, len(A) + 1):
    for j in range(1, len(B) + 1):
        if A[i - 1] == B[j - 1]:
        # i 이하 문자열의 문자들 중 같은 문자가 있다면
            dp[i][j] = dp[i - 1][j - 1] + 1
            # 이전까지의 공통 부분 수열에 한 개 추가한 길이로 갱신
        else: 
            dp[i][j] = max(dp[i - 1][j],dp[i][j - 1])
            # 현재 접근한 인덱스의 문자가 LCS의 일부가 아니므로 이전 인덱스까지의 LCS길이 중 큰 값으로 설정

        ans = max(ans, dp[i][j])
        # 현재 접근한 인덱스의 LCS길이와 ans길이를 비교하여 더 큰 값을 저장

print(ans)

---

코드 설명

Bottom-Up 풀이를 사용한다.

 

1. 메모이제이션 테이블 dp[i][j]는 문자열 A의 i번째 인덱스까지와 문자열 B의 j번째 인덱스까지 두 문자열의 LCS 길이를 저장한다.

(초기값은 길이의 최소 값인 0이다.)

 

2. 이중 반복문을 이용하여 문자열 A와 B의 모든 쌍에 접근한다.

 

2-1. A의 i-1번째 문자와 B의 j-1번째 문자가 같다면 그 문자를 이전까지의 LCS에 추가한 길이를 dp에 저장한다.

 

2-1. 다르다면, 이전 까지의 수열 의 LCS 길이 중 큰 값으로 갱신한다.

 

3. 항상 위 과정이 끝나면 출력할 변수 ans의 길이보다 큰지 (지금까지 검사한 길이보다 큰지) 확인하고 값을 갱신한다.