📌문제
💡문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
💡입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
💡출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.
LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.
📌풀이
💡문제 분석
문자열의 최대 길이가 1000이므로, 2차원 배열을 사용하는 DB 알고리즘으로 해결할 수 있다.
💡LCS의 길이 찾기
두 문자열을 str1, str2라 하자.
str1의 1~i번째와 str2의 1~j번째 사이의 최장 부분 수열의 길이를 dp[i][j]에 저장한다.
이 때 아래와 같은 규칙이 있다.
- 만약 str1의 i번째 문자와 str2의 j번째 문자가 같다면, dp[i][j] = dp[i-1][j-1] + 1이다.
- 만약 str1의 i번째 문자와 str2의 j번째 문자가 다르다면, dp[i-1][j]와 dp[i][j-1] 중 큰 값을 저장한다.
계속 dp[] 값을 채워가다 보면, 두 문자열의 LCS의 길이는 dp[len(str2)][len(str1)]에 저장된다.
💡LCS 찾기
실제 LCS를 찾기 위해서는 앞에서 구한 dp[]를 이용하면 된다.
dp[1][1]에서부터 dp[len(str2)][len(str1)]까지 이동하면서, 다음과 같은 규칙을 사용했다.
- 만약 str1의 i번째 문자와 str2의 j번째 문자가 같다면, dp[i][j] = dp[i-1][j-1] + 1이다.
- 만약 str1의 i번째 문자와 str2의 j번째 문자가 다르다면, dp[i-1][j]와 dp[i][j-1] 중 큰 값을 저장한다.
따라서, dp[len(str2)][len(str1)]에서 역으로 dp[1][1]까지 이동하면서, LCS를 이루는 수를 찾을 수 있지 않을까? 그 이유는 'str1의 i번째 문자와 str2의 j번째 문자가 같다면'이 성립할 때마다 LCS의 길이가 늘어났으므로, 해당 문자는 LCS에 포함된다고 말할 수 있다.
LCS를 찾기 위해서는 아래와 같은 규칙을 사용한다.
- 만약 str1의 i번째 문자와 str2의 j번째 문자가 같다면, 그 문자를 LCS의 원소로 추가하고, dp[i-1][j-1]로 이동한다.
- 만약 str1의 i번째 문자와 str2의 j번째 문자가 다르다면, dp[i-1][j]와 dp[i][j-1] 중 큰 값으로 이동한다.
📌코드
import sys
str1 = list(str(sys.stdin.readline().rstrip()))
str2 = list(str(sys.stdin.readline().rstrip()))
len1 = len(str1)
len2 = len(str2)
dp = [[0 for _ in range(len1 + 1)] for _ in range(len2 + 1)]
for i in range(1, len2 + 1):
for j in range(1, len1 + 1):
if str2[i - 1] == str1[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
i, j = len2, len1
ans = []
while i != 0 and j != 0:
if str2[i - 1] == str1[j - 1]:
ans.append(str2[i - 1])
i -= 1
j -= 1
else:
if dp[i - 1][j] > dp[i][j - 1]:
i -= 1
else:
j -= 1
print(dp[len2][len1])
ans.reverse()
print("".join(ans))
📌코멘트
