옌의 로그

문제 [백준] LCS 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 사용 알고리즘 - 다이나믹 프로그래밍 (Dynamic Programming) 해결방법 입력 받은 두 문자열 X, Y의 위치 인덱스를 각각 i, j라 할 때, 두 문자열의 최장 공통 부문 수열을 LCS(i, j)라 하자 if Xi = Yj 일 때, (두 문자열의 마지막 글자가 같을 때) LCS(i, j) = LCS(i-1, j-1) + 1 if Xi != Yj 일 때, (두 문자열의 마지막 글자가 ..