9251 LCS

두 수열에서 두 수열의 부분수열이 되는것중 길이가 가장 긴것을 LCS(최장 공통 부분 수열)이라고 한다. 이 때 두 문자열의 LCS값을 구하는 문제이다.

이 알고리즘은 널리 알려져있어서 나도 그것을 이용했다. DP로 해결이 가능하며 시간복잡도는 O(n*m) 이다. n,m은 각각 두 수열의 길이를 의미한다.

소스