[백준] 9251번 LCS ★★★

💡문제접근

• LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제였다. 이 문제는 2차원 배열을 이용한 다이나믹 프로그래밍의 문제였다.
• 이 문제를 풀면서 어떤 방식으로 접근을 해야하는지는 이해를 했지만 한 가지 의문점이 들었다. 만약에 최장 공통 부분 수열의 길이가 아니라 최장 공통 부분 수열을 출력하라고 한다면 어떻게 해야할까?
• 스스로 던진 위의 질문에 대해서 더 고민해서 코드를 작성하여 추가로 포스팅할 예정이다.

최장 공통 부분 수열(LCS)

💡코드(메모리 : 55712KB, 시간 : 596ms)

import sys
input = sys.stdin.readline

String1 = input().strip()
String2 = input().strip()
lenString1 = len(String1)
lenString2 = len(String2)

dp = [[0] * (lenString1+1) for _ in range(lenString2+1)]

for i in range(1, lenString2+1):
    for j in range(1, lenString1+1):
        if String2[i-1] == String1[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])

📌 이해를 돕기 위한 2차원 배열 표

X	X	A	C	A	Y	K	P
X	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	2	2	3	3	3	3
K	0	2	2	3	3	4	4

Q1. 최장 공통 부분 수열의 길이와 최장 공통 부분 수열 문자열은?

A1. 최장 공통 부분 수열의 길이 : 4
A2. 최장 공통 부분 수열의 내용 : ACAK

Q2. 최장 공통 부분 수열의 내용을 출력하는 코드를 아래에 작성해보기

💡소요시간 : 34m