programmer life guidance 101

www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 33820 13890 10207 40.512% 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다...

Longest Common Subsequence 최장 공통 부분 수열 여기서 substring은 연속된 부분 문자열이고, subsequence는 연속적이지 않은 부분 수열이다. 예로, "iamstudent" 라는 문자열에서 연속된 부분 문자열 mstu은 substring이 되고 연속적으로 이어지지는 않지만 순서는 맞는 mtue는 subsequence가 된다. 그렇다면 공통 부분 수열이란, 두 문자열이 공통으로 가지고 있는 부분 수열이다. 에를 들어 "CDABE" 와 "CDEGT"가 있다면 공통부분 수열은 {}, {C}, {D}, {E}, {C, D}, {D, E}, {C, E}, {C, D, E} 일 것이다. 최장 공통 부분 수열이란 공통 부분 수열 중에서 길이가 가장 긴 부분 수열을 뜻한다. 대표적으로..