https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS는 가장 긴 공통 부분 수열을 찾는 유형의 문제를 이르는 말인 것 같다. 우선 풀이는 완전탐색(브루트포스), 동적계획법이 가능하다. 어느 블로그를 찾아보니 LCS가 두 가지 문제 유형으로 나뉜다고 한다. 1. Longest Common Substring 2. Longest Common Subsequence 이 문제는 2번이다. 1번은 가장 긴 공통..