개발자 퉁이리

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 문자열 ⊙ 문제 접근 과정 LCS 알고리즘 문제다. LCS는 번역하면 최장 공통 부분 문자열이다. 전에 다뤘던 LIS 최장 증가 부분 수열과 유사하다. LIS는 다이나믹 프로그래밍(DP)을 기반으로 알고리즘이 구성되어있는데 LCS도 마찬가지이다. DP를 이용하여 구현하면 공..