[DP] 백준 LCS, 2 9251번 with Python3 ★

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

9251번: LCS

문제

정답 풀이

import sys
X = sys.stdin.readline().strip().upper()
Y = sys.stdin.readline().strip().upper()

len1 = len(X)
len2 = len(Y)

dp = [[0] * (len2 + 1) for _ in range(len1+1)]

for i in range(1, len1 + 1):
    for j in range(1, len2 + 1):
        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[-1][-1])

출처:https://suri78.tistory.com/11

 

해석

코드 진행에 대한 로직은 출처에 잘 설명 되어 있다. LCS를 찾는 로직에 대한 깊은 설명은 Introduction to Algorithm 393페이지를 참조하면 된다.

 

 

 

추가 문제

 

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

9252번: LCS 2

내 풀이

import sys
X = sys.stdin.readline().strip().upper()
Y = sys.stdin.readline().strip().upper()

len1 = len(X)
len2 = len(Y)

dp = [[''] * (len2 + 1) for _ in range(len1+1)]

for i in range(1, len(X) + 1):
    dp[i][0] = X[i-1]

for j in range(1, len(Y) + 1):
    dp[0][j] = Y[j-1]

for i in range(1, len1 + 1):
    for j in range(1, len2 + 1):

        if i == 1 and j == 1:
            if X[i-1] == Y[j-1]:
                dp[i][j] = X[i-1]
        elif i == 1 and j > 1:
            if X[i-1] == Y[j-1]:
                dp[i][j] = X[i-1]
            else:
                dp[i][j] = dp[i][j-1]

        elif i > 1 and j == 1:
            if X[i-1] == Y[j-1]:
                dp[i][j] = X[i-1]
            else:
                dp[i][j] = dp[i-1][j]

        else:
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + X[i-1]
            else:
                if len(dp[i-1][j]) > len(dp[i][j-1]):
                    dp[i][j] = dp[i-1][j]
                elif len(dp[i][j-1]) > len(dp[i-1][j]):
                    dp[i][j] = dp[i][j-1]
                else:
                    dp[i][j] = dp[i][j-1]


print(len(dp[-1][-1]))
print(dp[-1][-1])

해석

LCS에서 차이점은 가장 긴 공통 문자열을 길이 뿐만아니라 문자열도 출력해야한다는 점이다.

같은 로직에 사용되는 dp 테이블에 길이가 되는 숫자가 아닌 공통 문자열을 직접 담으면 된다.

 

유일한 문제점? 통과는 되었는데 이해가 안되는점? 은

X[i-1] != Y[j-1] 일 때, 그리고 dp[i-1][j] 와 dp[i][j-1]의 길이가 같을 때, 둘 중 적절한것을 선택하는 알고리즘이 따로 필요하지 않고 그냥 둘중 하나만 하면 된다는 점이다.