[Algorithm][BOJ 9251] LCS

문제

 

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

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

풀이

 

대표적인 다이다믹 프로그래밍 문제.

DP 문제는 처음이라 못 풀고 풀이를 보면서 코드를 짰는데

나중에 자세하게 이 부분을 쓰고자 한다.

==========================

 

 

Python 코드

 

import sys

input = sys.stdin.readline

string1 = input().rstrip()
string2 = input().rstrip()

array = [[0]*(len(string2)+1) for _ in range(len(string1)+1)]

for i in range(1, len(string1)+1) :
    for j in range(1, len(string2)+1) :
        if string1[i-1] == string2[j-1] :
            array[i][j] = array[i-1][j-1] + 1
        else :
            array[i][j] = max(array[i][j-1], array[i-1][j])

print(array[-1][-1])

 

 

후기 및 보완할 점

 

DP가 여태까지 했던 알고리즘 중에 가장 이해도가 난해한 것 같다. 풀이를 봐도 엄.. 했던.스터디에서 하기로 한 문제 말고도 다른 문제도 풀어봐야겠다.