❓백준(BaekJoon) 9252번 : LCS 2
📈 문제 요약
LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제는 두 수열일 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 두 문자열이 주어졌을 때 LCS의 길이와 LCS 문자열을 출력하면 되는 문제
🤨 접근법
직전문제(LCS) 에서 LCS 길이 뿐만이 아니라 LCS 문자열 자체를 구해내야 되는 문제이다. LCS 문자열은 최종 DP 테이블을 역추적 해 DP 테이블이 채워지는 과정에서 얻어낼 수 있기 때문에 직전 문제의 풀이처럼 1차원 DP 배열을 업데이트 하는 방식이 아닌, 2차원 DP 배열을 채워나가는 방식으로 우선 LCS의 길이를 구해냈다.
LCS의 길이를 구하는 방식은 위 그림처럼 두 문자열의 각 길이 만큼을 행, 열로한 2차원 dp 배열을 채워나가면서 구해낼 수 있다. dp배열을 모두 0으로 초기화 한 다음, 아래과 같은 점화식을 통해 dp배열을 순회하며 메모이제이션 해준다.
메모이제이션 과정을 대략적으로 설명하면, dp[i][j]가 의미하는 바는 각각 str1[i], str2[j]번째 문자를 포함했을 때 LCS의 길이이며, str1[i]와 str2[j]가 같다면 각 문자열에서 해당 문자를 포함하지 않았던 LCS 길이(dp[i-1][j-1])에 +1을 해주는 것이고, 같지 않다면 두 문자열 중 어느 한 쪽의 문자열만 해당 문자를 포함하게 되었을 때 더 큰 경우의 수를 그대로 가져가는 것이다.
이러한 방식으로 dp 테이블을 모두 채웠다면, 이제 이 과정을 역으로 추적해서 실제 LCS를 구해야 한다.
dp 테이블의 마지막 인덱스부터 시작해 i와 j 포인터를 잡고 다음의 방법으로 dp[i][j]가 0인 곳을 만날 때 까지 포인터를 업데이트하며 각 문자열의 원소를 비교한다.
- str1[i]와 str2[j]가 같지 않다면 dp[i][j]의 수는 dp[i-1][j]와 dp[i][j-1] 중 더 큰 쪽에서 온 수이므로 포인터를 더 큰 쪽의 인덱스로 이동한다.
- str1[i]와 str2[j]가 같다면 dp[i][j]의 수는 dp[i-1][j-1]에서 1이 더해져서 온 수이므로 포인터를 i-1, j-1로 이동한 후 LCS 문자열에 해당 문자를 더해준다.
최종적으로 더해진 LCS 문자열은 역으로 뒤집혀있으므로, 출력 시 문자열을 반전하여 출력하도록 해야한다. 또한 문제의 조건에 따라 LCS길이가 0인 경우 LCS 문자열을 출력하지 않도록 해야한다.
🔡 코드
import sys
input = sys.stdin.readline
str1, str2 = input().rstrip(), input().rstrip()
# str1 : ACAYKP
# str2 : CAPCAK
n1, n2 = len(str1), len(str2)
dp = [[0 for _ in range(n2+1)] for _ in range(n1+1)]
for i in range(1, n1+1):
for j in range(1, n2+1):
if str1[i-1] == str2[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])
if dp[i][j]:
LCS = ''
while dp[i][j]:
if str1[i-1] == str2[j-1]:
LCS += str1[i-1]
i, j = i-1, j-1
else:
if dp[i-1][j] < dp[i][j-1]:
j -= 1
else:
i -= 1
print(LCS[::-1])