Beelog

www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제는 위와 같으며 각 문장을 단어로 쪼개서 하나씩 단어를 늘려가면서 부분 수열의 수를 구하는 방식으로 문제를 해결할 수 있습니다. 예제를 테이블을 이용해 살펴보면 다음과 같습니다. A 문장이 ACAYKP 이고 B 문장이 CAPCAK 인 경우 각 문장을 단어로 쪼개서 이중 for 문을 돌면서 서로 비교합니다. 1. 예를 들어 A 문장의 ACAY 와 B 문장의 CAP ..