[BOJ] 9251 : LCS [다이나믹 프로그래밍](Python)

문제 링크

9251번: LCS (acmicpc.net)

9251번: LCS

소스 코드

a = input()
b = input()

def lcs(a,b):
    m,n = len(a),len(b)

    dp = [[None for _ in range(n+1)] for _ in range(m+1)]

    for row in range(m+1):
        for col in range(n+1):
            if row == 0 or col == 0: # 둘 중 하나가 글자가 아닌 경우
                dp[row][col] = 0
            elif a[row-1] == b[col-1]: # 동일한 글자가 발견된 경우
                dp[row][col] = dp[row-1][col-1] + 1 # 직전 + 1
            else: # 동일한 글자가 아닌 경우 -> 현재까지의 최댓값 불러오기
                dp[row][col] = max(dp[row-1][col],dp[row][col-1])
    
    return dp[row][col]

print(lcs(a,b))

 

해설

• LCS, Longest Common Subsequence, 가장 긴 공통 부분 수열
• DP, Dynamic Programming, 다이나믹 프로그래밍

시간복잡도

문제에서는 문자열 길이에 대한 조건이 따로 주어지지 않았습니다.

그래서 실제로 길이가 다른 문자열이 존재할지 아닐지 테스트해보지는 않았습니다만, 위와 같이 길이가 m,n인 문자열이라고 가정한다면 시간복잡도는 O(m*n)이 됩니다(이중 for문).

만약 두 문자열의 길이가 n으로 동일하다면 O(n^2)이 될 것입니다.

 

각 문자열이 최대 1,000 글자라는 조건은 주어져 있으므로 위 코드로 풀이하더라도 문제되지 않는다는 것을 알 수 있습니다.

 

풀이

1) 둘 중 하나가 글자가 아닌 경우

애초에 dp 테이블을 초기화할 때 길이 m,n 보다 1씩 더 크게 범위를 주었습니다.

따라서 0번 인덱스에 해당하는 것은 문자열 a, b에 대해서는 공백을 의미하게 됩니다.

그렇기 때문에 row, col이 0인 경우에는 그냥 묻고 따지지 않고 0을 입력해줍니다.

if row == 0 or col == 0: # 둘 중 하나가 글자가 아닌 경우
    dp[row][col] = 0

 

2) 동일한 글자가 발견된 경우

위 코드는 문자열 a의 각 글자를 각 행으로, 문자열 b의 각 글자를 각 열로 부여한 것입니다.

따라서 문자열 a의 글자를 기준으로 문자열 b의 글자와 동일한지 비교합니다.

elif a[row-1] == b[col-1]: # 동일한 글자가 발견된 경우
    dp[row][col] = dp[row-1][col-1] + 1 # 직전 + 1

 

둘이 같은 경우, 두 글자의 직전 글자까지의 최댓값 + 1을 해주면 됩니다.

예를 들어 a = 'ABA', b = 'BBA' 라고 해보겠습니다.

 

이때 a의 두 번째 글자 B와 b의 두 번째 글자 B를 비교합니다.

두 글자는 동일합니다. 따라서 a의 첫 번째 글자 A, b의 첫 번째 글자 B까지 비교한 것들 중 최댓값에 1을 더해줍니다.

이 경우에는 첫 글자들은 달랐기 때문에 0+1이 될 것입니다.

 

3) 서로 다른 글자일 경우

이때는 직전 조합에서 최댓값을 불러옵니다.

직전 조합은 문자열 a에 대해서만 직전 글자일 수도 있고, 문자열 b에 대해서만 직전 글자일 수도 있습니다.

따라서 저장된 두 값을 비교하여 큰 것을 새로 저장해주면 됩니다.

else: # 동일한 글자가 아닌 경우 -> 현재까지의 최댓값 불러오기
    dp[row][col] = max(dp[row-1][col],dp[row][col-1])

 

시간 복잡도가 안 좋은 재귀 풀이

def lcs(X, Y, m, n):

    if m == 0 or n == 0:
       return 0;
    elif X[m-1] == Y[n-1]:
       return 1 + lcs(X, Y, m-1, n-1);
    else:
       return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));

print(lcs(X, Y, len(X), len(Y)))

논리 자체는 완전 동일한 풀이 방식입니다.

하지만 두 글자가 동일하지 않은 경우 두 개의 갈래로 나눠지며 재귀가 반복되기 때문에 시간 복잡도가 O(2^n)에 달합니다.

n이 최대 1,000일 수 있다는 점을 감안하면 이런 방식으로는 문제를 풀 수 없다는 것을 알 수 있습니다.