⏰ 시간복잡도: O(M N) / 공간복잡도: O(M N)
✏️ 답안
import sys
first = sys.stdin.readline().strip()
second = sys.stdin.readline().strip()
def longest_common_subsequence(text1: str, text2: str) -> int:
dp_grid = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
for col in reversed(range(len(text2))):
for row in reversed(range(len(text1))):
if text2[col] == text1[row]:
dp_grid[row][col] = 1 + dp_grid[row + 1][col + 1]
else:
dp_grid[row][col] = max(dp_grid[row + 1][col], dp_grid[row][col + 1])
return dp_grid[0][0]
print(longest_common_subsequence(first, second))👀 접근방법
1) DP 배열 초기화
큰 문제를 작은 문제로 쪼개어 문제를 해결해나가는 DP의 bottom-up 방식을 활용하여 문제를 풀었다.
먼저 LCS 길이를 저장할 수 있도록(첫 번째 문자열의 길이 + 1) * (두 번째 문자열의 길이 + 1)의 사이즈로 2차원 DP 배열을 만들었다.
연산을 쉽게 하기 위해 문자열의 길이에 1을 더한 사이즈로 만들었고, 모두 0으로 초기화했다.
dp[i][j]는 첫 번째 문자열의 i번째 ~ 마지막 부분과 두 번째 문자열의 j번째 ~ 마지막 부분의 LCS 길이를 의미한다.
아래 그림을 예로 들어 살펴보면 주황색으로 표시한 dp_grid[3][2]에는 문자열 "YKP"와 "PCAK"의 LCS 길이가 들어간다.
2) DP 배열 값 채워넣기
DP 배열의 값을 채워넣는 방법은 아래와 같이 두 가지 경우로 나누어 살펴볼 수 있다.
1) 두 문자열의 첫 글자가 같은 경우
두 문자열의 첫 글자가 같은 경우에는 오른쪽 대각선 아래에 있는 값, 즉 dp[row + 1][col + 1]에 1을 더해주면 된다.
왜 대각선으로 1을 더해주는 것일까?
아래 그림에서 dp[row][col]는 "AYKP"와 "APCAK"의 LCS 길이이고, dp[row + 1][col + 1]는 "YKP"와 "PCAK"의 LCS 길이이다.
이 때, 두 문자열의 첫 글자가 "A"로 동일하므로 더 계산할 것 없이 이미 계산해놓은 "YKP"와 "PCAK"의 LCS 길이에 1을 더해주면 되는 것이다.
2) 두 문자열의 첫 글자가 다른 경우
두 문자열의 첫 글자가 다른 경우에는 오른쪽 칸의 값과 아래쪽 칸의 값 중 더 큰 값을 넣어주면 된다.
왜냐하면 두 문자열의 첫 글자가 다른 경우에는 최장 공통 문자열의 길이가 변하지 않으므로, 이때까지 계산해온 값 중에서 더 큰 값을 넣어주면 되는 것이다.
3) 정답 반환하기
위 과정을 거치면 최종적으로 아래와 같이 DP 배열이 완성된다.
dp[0][0]의 값이 문제에서 구하는 두 문자열의 LCS의 길이이다.
