[백준 파이썬] 9252번 LCS 2 (골드 3)

9252번 LCS 2 (골드 3)

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

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

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

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

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

4. 문제 풀이
LCS 의 전형적인 문제이다. 다만, 길이만 구하는게 아니라, LCS 자체도 구해야하는 문제이다.
LCS를 풀어봤다면 알겠지만, 방법은 동일하게 하되, 
DP에 길이가 아닌, 해당 LCS 자체를 갱신하며 저장해 가면 되는 문제이다.

LCS의 규칙은 다음과 같다.
1) 현재 위치의 글자가 마지막 글자라고 가정하며, DP에 저장한다.
즉 DP[i][j]는 str1의 i번쨰 글자가 마지막이고, str2의 글자가 마지막이라고 할때의 LCS를 저장한다.

2) 현재 위치의 글자가 같다면 (str1[i] == str2[i]),
현재 위치에서 -1된 부분의 LCS 에 현재 글자를 더한 것이 현 위치의 LCS가 된다.

3) 현재 위치에서 글자가 다르다면 (str1[i] != str2[i]), 
str1의 현재글자와 str2의 이전글자 까지의 LCS (DP[i][j-1])와 
str1의 이전글자와 str2의 현재글자 까지의 LCS (DP[i-1][j])중 더 긴 것이 LCS가 된다.

이를 Top-down과 Bottom-up 방식으로 모두 풀이가 가능하다.

>>>코드1. Bottom-up

"""
9252번 LCS 2 (골드 3)
input : 
    A 문자열 A
    B 문자열 B
output :
    length 두 문자열의 LCS 길이
    LCS 두 문자열의 LCS
"""
A = input()
B = input()

def LCS(str1, str2):
    a, b = len(str1), len(str2)
    DP = [[''] * (b+1) for _ in range(a+1)]
    
    for i in range(1, a+1):
        for j in range(1, b+1):
            if str1[i-1] == str2[j-1]:
                DP[i][j] = DP[i-1][j-1] + str1[i-1]
            else:
                if len(DP[i-1][j]) > len(DP[i][j-1]):
                    DP[i][j] = DP[i-1][j]
                else:
                    DP[i][j] = DP[i][j-1]
    
    return DP[a][b]

ans = LCS(A, B)
length = len(ans)

print(length)
if length:
    print(''.join(ans))

 

Bottom-Up 메모리/시간

Top-down의 경우, 메모이제이션을 사용하는 것을 확실하게 확인하자.
필요한 값을 구해놓고 다시 구하는것만큼 멍청한 일이 없다.

그리고 Top-Down의 경우 LCS를 memo 리스트 안에 저장하면, 시간초과와 메모리 초과가 발생할 수 있다.
bottom-down과는 다르게, 하위 문자열의 LCS를 구하려고 슬라이싱을 할때마다,
새로운 문자열이 생성되기 때문이다. 
따라서, 이를 해결하기 위해, lcs 함수에 문자열을 전달하지말고, 인덱스만 전달하도록 한다.
또한, 길이를 memo에 저장하는 lcs_length 함수와 문자를 도출하는 lcs_string 함수를 따로 만들어 실행한다.
여기까지 보면 감이 왔겠지만, 그냥 bottom-up 하는게 신상에 이로운듯 하다.

>>>코드2. Top-down + 메모이제이션

"""
9252번 LCS 2 (골드 3)
input : 
    A 문자열 A
    B 문자열 B
output :
    length 두 문자열의 LCS 길이
    LCS 두 문자열의 LCS
"""
import sys
sys.setrecursionlimit(10**5)

A = sys.stdin.readline().strip()
B = sys.stdin.readline().strip()

a, b = len(A), len(B)
memo = [[-1] * (b+1) for _ in range(a+1)]

# LCS 길이 반환 memoization 함수
def LCS_length(i, j):
    # 0인 경우 빈칸 문자열 반환
    if i == 0 or j == 0:
        return 0
    
    # 메모이제이션 (한번 구한값을 또 구하지 않고 재사용)
    if memo[i][j] != -1:
        return memo[i][j]
    
    # 재귀 시작
    if A[i-1] == B[j-1]:
        memo[i][j] = LCS_length(i-1, j-1) + 1
        return memo[i][j]
    else:
        case1 = LCS_length(i-1, j)
        case2 = LCS_length(i, j-1)
        memo[i][j] = max(case1, case2)
        return memo[i][j]

# LCS 반환 memo 활용 함수
def LCS_string(i, j):
    if i == 0 or j == 0:
        return ""
    
    if A[i-1] == B[j-1]:
        return LCS_string(i-1, j-1) + A[i-1]
    else:
        if memo[i][j-1] > memo[i-1][j]:
            return LCS_string(i, j-1)
        else:
            return LCS_string(i-1, j)
        

length = LCS_length(a, b)
print(length)
if length:
    print(LCS_string(a, b))

Top-Down 메모리/시간

5. 문제 링크
https://www.acmicpc.net/problem/9252