5. LCS(중)
View as PDFLCS를 구현해 보자.
LCS는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
- 첫째 줄에 문자열A의 길이와 문자열B의 길이가 주어진다. 길이는 모두 1000 이하의 자연수이다.
- 두 번째 줄에 문자열A가, 세 번째 줄에 문자열B가 주어진다. 문자열은 모두 알파벳 대문자로만 이루어져 있다.
출력
- 두 문자열의 LCS의 길이를 출력한다.
입력 예시 1
6 6
ACAYKP
CAPCAK
출력 예시 1
4
Comments
이 문제는 우리 교재의 문제입니다. 책을 읽고 잘 이해 하신 다음, 책의 알고리즘을 구현해 보세요.