Oneulog

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 100..

LCS 알고리즘 LCS는 주로 최장 공통 부분 수열(Longest Common Subsequence)을 말한다. LCS는 최장 공통 문자열(Longest Common Substring)을 말하기도 한다. 최장 공통 부분 수열과 최장 공통 문자열의 구분 최장 공통 부분 수열(Longest Common Subsequence) 점화식 두 문자가 다를 경우 LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]) 두 문자가 같을 경우 LCS[i][j] = LCS[i-1][j-1] + 1 동작 과정 1. 문자열 A, 문자열 B를 한 글자씩 비교한다. 2. 두 문자가 다르다면 LCS[i-1][j] 와 LCS[i][j-1] 중 큰 값을 표시 3. 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아..