백준 9252번 : LCS 2 in Python

9252번: LCS 2

 

acmicpc.net

이 문제는 두 문자열이 주어졌을 때 가장 긴 공통 부분 수열을 구하는 문제이다.

dynamic programming 알고리즘을 사용해 풀 수 있는 대표적인 문제 중 하나이다. 우선 각 문자열의 길이를 N과 M이라고 하면 (N+1)*(M+1) 크기의 행렬 두 개를 만든다. 한 행렬은 dynamic programming을 구현하기 위해 만든 행렬로써 dp라 이름짓고, 나머지 한 행렬은 LCS를 출력하기 위해 dynamic programming 과정을 기록하기 위해 만든 행렬로써 record라 이름짓는다.

그리고 두 문자열의 문자를 하나씩 차례대로 순회하면서, 만약 한 문자열의 i번째 문자와 다른 문자열의 j번째 문자가 서로 같은 경우 dp[i][j]은 dp[i-1][j-1]에 1을 더한 값으로 정의한다. 이는 dp[i][j]가 한 문자열을 i번째 문자까지만 보고, 다른 문자열을 j번째 문자까지만 봤을 때 가장 긴 공통 부분 수열의 길이를 의미하는데, 만약 위와 같은 경우가 발생할 경우 한 문자열을 i-1번째 문자까지만 보고 다른 문자열을 j-1번째 문자까지만 봤을 때 가장 긴 공통 부분 수열에 한 문자열의 i번째 문자나 다른 문자열의 j번째 문자를 뒤에 붙이면 되기 때문이다. 그리고 나중에 이를 출력하기 위해 record[i][j]에 'diagonal'이라는 문자열을 넣는다. 이는 행렬 관점에서 봤을 때 dp[i][j]가 dp[i-1][j-1]을 통해 정의되는데, 정의되는 방향이 대각선 방향임을 반영한 것이다.

만약 한 문자열의 i번째 문자와 다른 문자열의 j번째 문자가 서로 다른 경우 dp[i][j]는 dp[i-1][j]와 dp[i][j-1] 중 큰 값으로 하는데, 만약 dp[i-1][j]가 크다면 record[i][j]는 'down'으로, dp[i][j-1]가 크다면 'right'로 한다. 이는 위와 유사한 이유로 행렬 관점에서 봤을 때 dp[i][j]가 dp[i-1][j]를 통해 정의된 경우 정의되는 방향이 아래쪽이고, dp[i][j-1]을 통해 정의된 경우 정의되는 방향이 오른쪽이기 때문이다.

이 결과 dp[N][M]은 두 문자열의 LCS의 길이를 나타내게 된다. 그리고 이 LCS를 출력하기 위해서는 record 행렬을 (N, M) 성분에서 역방향으로 따라 올라가면서 'diagonal'이 있는 경우에 LCS에 문자열이 하나씩 추가됐음을 이용해 LCS에 해당 문자를 붙여간다. 이를 함수로 구현하면 해당 LCS를 출력할 수 있다.

이를 코드로 구현하면 다음과 같다.

str1 = input()
str2 = input()
N = len(str1)
M = len(str2)
# dynamic programming 구현을 위한 행렬
dp = [[0]*(M+1) for _ in range(N+1)]
# LCS 출력을 보조하기 위한 행렬
record = [['']*(M+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, M+1):
        # 두 문자열의 문자가 같은 경우
        if str1[i-1] == str2[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
            record[i][j] = 'diagonal'
        # 두 문자열의 문자가 다른 경우
        else:
            if dp[i-1][j] > dp[i][j-1]:
                dp[i][j] = dp[i-1][j]
                record[i][j] = 'down'
            else:
                dp[i][j] = dp[i][j-1]
                record[i][j] = 'right'
# LCS 길이 출력
print(dp[N][M])
# LCS 출력 보조 함수
def LCS(n, m):
    if n == 0 or m == 0:
        return ''
    if record[n][m] == 'diagonal':
        return LCS(n-1, m-1) + str1[n-1]
    elif record[n][m] == 'right':
        return LCS(n, m-1)
    elif record[n][m] == 'down':
        return LCS(n-1, m)
    else:
        return ''
print(LCS(N, M))