LCS
-
[Baekjoon Online Judge] 9251번: LCS문제 풀이/Baekjoon Online Judge 2021. 1. 8. 20:18
9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS (Longest Common Subsequence) 공통 부분 수열 중 가장 길이가 긴 것이 바로 최장 공통 부분 수열이다. 문제의 예시를 들어보았다. 문자열 A - ACAYKP 문자열 B - CAPCAK 두개의 문자열이 있다고 가정하자. 두 문자열의 공통 부분 수열은 C, CA, ACA, ACAK, AA 등이 있다. 그중 가장 긴 부분 수열을 구하는 문제이다. 문자열 A - ACAYKP 문자열 B - CAPC..