동적 프로그래밍 : LCS(백준 9251번)

▶ 문제 : https://www.acmicpc.net/problem/9251

9251번: LCS

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

##### 입력 #####
# 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 
# 문자열은 알파벳 대문자로만 이루어져 있으며, 
# 최대 1000글자로 이루어져 있다.

##### 출력 #####
# 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

▶ 접근 방법

수열 Xn = x1x2x3...xn, 수열 Ym = y1y2y3...ym이 주어졌을 때,
LCS(Xn, Ym)를 Xn, Ym의 최장 길이 공통부분 수열의 길이라고 하자.

각 수열의 n번 째인 xn과, m번째인 ym이 같다면, 이는 LCS(Xn, Ym)에 포함된다. 
즉, LCS(Xn, Ym)은 n-1번째, m-1번째까지의 LCS(Xn-1, Ym-1)에다 1을 증가시킨 것 이다.
그런데 만약 다르다면,
LCS(Xn, Ym-1)과 LCS(Xn-1, Ym) 중 더 큰 것이 LCS(Xn, Ym)이 된다.

아래 동영상을 참고하였다.
https://www.youtube.com/watch?v=EAXDUxVYquY

 

▶ 풀이 코드

import sys

string_A = list(sys.stdin.readline().rstrip())
string_B = list(sys.stdin.readline().rstrip())

# string_A의 크기를 열, string_B의 크기를 행으로 하여 행열을 만든다.
LCS = [[0] * (len(string_A) + 1) for _ in range(len(string_B) + 1)]


# 행을 하나 씩 보면서
for i in range(1, len(string_B) + 1):
    # 행의 열마다
    for j in range(1, len(string_A) + 1):
        # string_B와 string_A의 값이 같은 걍우가 있다면
        # 아래의 점화식을 따르고
        if string_B[i - 1] == string_A[j - 1]:
            LCS[i][j] = LCS[i-1][j-1] + 1
        # 다르다면, 아래의 점화식을 따른다.
        else :
            LCS[i][j] = max(LCS[i][j-1], LCS[i-1][j])

print(LCS[-1][-1])

 

▶ 관련 링크

2021.11.25 - [알고리즘] - 동적 프로그래밍(Dynamic Programming)이란?

2021.11.25 - [알고리즘] - 동적 프로그래밍 : 피보나치 수 2(백준 2748번)

2021.11.25 - [알고리즘] - 동적 프로그래밍 : 01타일(백준 1904번)

2021.11.26 - [알고리즘] - 동적 프로그래밍 : 평범한 배낭(백준 12865번)

2021.11.27 - [알고리즘] - 동적 프로그래밍 : 동전(백준 9084번)