softwareNote softwareNote

LCS란 주어진 모든 수열들의 부분 수열(연속적이지 않아도 된다)이 되는 수열 중 가장 긴 것이다. str1과 str2라는 두 수열이 주어졌다고 하자. P] str1과 str2의 부분수열 중 가장 긴 수열의 길이를 구하라. Sol) str1의 시작부터 x번째까지의 문자열과 str2의 시작부터 y번째까지의 문자열의 LCS를 f(x, y)라고 하자. 이때 f(m, n)은, 1) str1의 m번째 문자 == str2의 n번째 문자일때 f(m, n) = f(m - 1, n - 1) + 1 : 현재 일치하는 문자를 제외하고 나머지 문자열들의 LCS가 현재 문자열들의 LCS보다 하나 짧아야 하므로 자명하다. 2) str1의 m번째 문자 != str2의 n번째 문자일때 f(m, n) = max(f(m - 1, n) ..