[백준_9252] 다이나믹 프로그래밍(DP), LCS 최장 공통 부분 문자열

[백준_9252] 다이나믹 프로그래밍(DP), LCS 최장 공통 부분 문자열

다이나믹 프로그래밍 대표 문제인 LCS 문제를 풀어봤다. LCS(Longest Common Subsequence)는 최장 공통 부분 문자열로 다이나믹 프로그래밍의 대표적인 문제이다.

문자열 출력까지 포함하는 9252번 문제를 풀어보았다.

 

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

9252번: LCS 2

 

문제 풀이

생각 포인트

 

다이나믹 프로그래밍을 풀기 위해서는 2가지 조건을 만족해야한다. 먼저 최적 부분구조를 확인해보자.

이 문제는 각 리스트의 마지막 원소가 중요하다. LCS(Xn, Ym)을 Xn과 Ym 의 최장 공통 부분 문자열의 수라고 하자.

 

Xn = (x0, x1,  ...., xn), Ym = (y1, y2, ...., ym)

 

1) xn = yn 이면 LCS에 xn = yn 이 포함된다.

2) xn != yn 이면 LCS(Xn, Ym-1) 과 LCS(Xn-1, Ym) 둘 중 큰 값이 LCS(Xn, Ym)이다.

 

이를 통해 큰 문제(LCS(Xn, Ym 구하기)를 작은 문제(LCS(Xn-1, Ym), LCS(Xn, Ym-1), LCS(Xn-1, Yn-1))로 나눠 점화식을 만들 수 있는 최적 부분 구조임을 확인 할 수 있다.

그리고 점화식 계산 시 계속해서 같은 LCS값이 사용되기 때문에 중복 부분 문제의 조건도 갖추고 있어 다이나믹 프로그래밍으로 해결 가능하다.

메모이제이션을 위해 dp[] 리스트를 사용하였고, 여기에 LCS길이(첫 코드)나 문자열(수정 코드 2)을 저장하는 방식으로 풀이 하였다.

 

 

코드

첫 번 째 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

X = list(map(str, input().strip()))
Y = list(map(str, input().strip()))
x = len(X)
y = len(Y)

dp = [[0] * (y+1) for _ in range(x+1)] # x 가로, y 세로

dp[0][0] = 0

for i in range(1, x+1): # x 세로
    for j in range(1, y+1): # y 가로
        if i == 0 or j == 0:
            dp[i][j] = 0
            continue
        if X[:i][-1] == Y[:j][-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

print(dp[x][y])

result = []
def dp_list(x1,y1):
    if dp[x1][y1] == 0:
        return
    if X[:x1][-1] == Y[:y1][-1]:
        result.append(X[:x1][-1])
        dp_list(x1-1,y1-1)
    else:
        if dp[x1-1][y1] > dp[x1][y1-1]:
            dp_list(x1-1,y1)
        else:
            dp_list(x1,y1-1)
if dp[x][y] != 0:
    dp_list(x,y)
    result.reverse()
    ans = ''.join(result)
    print(ans)

리스트의 slicing이 시간 소요가 생각보다 많았다. 그래서 이 부분을 수정하였다.

 

수정 코드 1

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

X = list(map(str, input().strip()))
Y = list(map(str, input().strip()))
lx = len(X)
ly = len(Y)

dp = [[0] * (ly+1) for _ in range(lx+1)] # x 가로, y 세로

for i in range(1, lx+1): # x 세로
    for j in range(1, ly+1): # y 가로
        if i == 0 or j == 0:
            dp[i][j] = 0
            continue
        if X[i-1] == Y[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

print(dp[lx][ly])

# LCS 문자열 출력을 위한 함수
def LCS_str(x1,y1):
    # LCS = 0 인경우 종료
    if dp[x1][y1] == 0:
        return
    # X, Y 리스트의 가장 끝 원소의 값이 같은 경우, 그 문자 result에 저장
    if X[:x1][-1] == Y[:y1][-1]:
        result.append(X[:x1][-1])
        LCS_str(x1-1,y1-1)
    # X, Y 리스트의 가장 끝 원소의 값이 다른 경우, X,Y 리스트에서 마지막 원소를 제외했을 때 LCS가 더 큰 경우로 이동
    else:
        if dp[x1-1][y1] > dp[x1][y1-1]:
            LCS_str(x1-1,y1)
        else:
            LCS_str(x1,y1-1)

result = []
LCS_str(lx,ly)
result.reverse()
print(''.join(result))

 

슬라이싱을 없애 처리 속도는 빨라졌다. 하지만 문자열을 확인하기 위한 추가 함수를 만들어서 코드가 길어졌다.

 

수정 코드 2

import sys
input = sys.stdin.readline

X = list(input().strip())
Y = list(input().strip())
lx = len(X)
ly = len(Y)
# memoization을 위한 리스트, X를 세로 축(x좌표), Y를 가로 축(y좌표)로 생각하면 편함
dp = [[''] * (ly+1) for _ in range(lx+1)] # x 가로, y 세로
# LCS 구하기
for i in range(1, lx+1): # x 세로
    for j in range(1, ly+1): # y 가로
        # X,Y 리스트의 가장 끝 원소가 같은 경우
        if X[i-1] == Y[j-1]: 
            dp[i][j] = dp[i-1][j-1] + X[i-1]
        # X,Y 리스트의 가장 끝 원소가 다른 경우
        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]

print(len(dp[lx][ly]))
print(dp[lx][ly])

 

LCS에 길이 대신 문자열을 더해주는 방식. 문자열을 따로 구하지 않아도 돼서 코드가 훨씬 간단하다.

다만 속도 차이는 크게 나지 않는다.