백준 9251번 - LCS (골드 5) 문제 분석두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 문제 풀이먼저, 예시로 주어진 두 문자열을 비교해보자.아래 표는 해당 문자까지의 최대 길이를 저장한 배열이다. ACAYKPC011111A112222P112223C122222A123333K123344 행과 열을 비교하며 표를 채울 수 있다.'A'와 'C'를 비교하면 LCS는 0이 된다.'AC'와 'C'를 비교하면 LCS는 'C'로 1이 된다.'ACA'와 'C'를 비교하면 LCS는 'C'로 1이 된다. 이런 식으로 표를 채워가면 아래 공식을 발견할 수 있다.두 문자가 같을 때는 문자를 추가하기 전 ..
