최장 공통 부분 수열

문제 설명LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.      제한 사항      풀이문제를 요약하면 LCS를 구하는 것이다.LCS는 최장 공통 부분 수열을 의미한다. 최장 공통 부분 수열은 두 개의 문자열 혹은 배열에서 가장 긴 공통된 부분을 의미한다.예를 들어 보자.ACAYKP, CAPCAK 두 개의 문자열의 LCS는 ACAK이다. 그렇다면, 이를 어떻게 구해내는지 알아보자.LCS는 DP를 이용하여 간단하게 구해낼 수 있다.이차원 배열을 통해 메모이제이션을 한다.두 문자열의 각 위치를 비교하며 같을 때와 다..