백준 알고리즘

[백준/Python]9251_LCS

헝그리개발자 2021. 6. 16. 13:27

문제

https://www.acmicpc.net/problem/9251

 

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

풀이

DP를 이용하여 풉니다.

문제에 주어진 예제를 2차원 DP 테이블에 나타내면 다음과 같습니다.

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

입력받은 두 문자열을 순서대로 s1과 s2 변수에 저장합니다.

(len(s1) + 1) * (len(s2) + 1) 크기의 2차원 배열을 선언하고 0값으로 초기화합니다.

이중 for문을 돌면서 아래의 점화식 조건으로 값을 저장합니다.

  1. s1[i]와 s2[j]가 같을 때
    • dp[i][j] = dp[i - 1][j - 1] + 1
  2. s1[i]와 s2[j]가 다를 때
    • dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

최종적으로, dp[-1][-1]이 s1과 s2의 LCS가 됩니다.

코드

import sys

s1 = sys.stdin.readline().rstrip()
s2 = sys.stdin.readline().rstrip()
dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
for i in range(1, len(s1) + 1):
    for j in range(1, len(s2) + 1):
        if s1[i - 1] == s2[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
            continue
        if s1[i - 1] != s2[j - 1]:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
print(dp[-1][-1])
저작자표시