백준 9251번: LCS Dynamic Programming https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 문제 설명 LCS는 두개의 문자열이 주어졌을때, 공통적으로 가장 긴 subsequence를 찾는 문제이다. 이때, substring과 달리 subsequence는 문자열이 연속적이지 않아도 된다. 만약, 문자열 X와 Y가 다음과 같다고 하자. X = Y = 이때 생성될 수 있는 subse..