LCS

백준 9251 풀이 (LCS, 다이나믹 프로그래밍)

LCS는 Longest Common Subsequence라고 한다. 최장 공통 부분 수열.....이름부터 먼가 심상치 않다. 두 수열이 주어질때 공통으로 가장 긴 부분 수열을 찾는 알고리즘이다. C와 ACAYKP를 비교한다고 생각하고 2차원 배열을 만든다. 이후에 CA, CAP, CAPC....등으로 확장해나간다. 그러면 아래와 같은 2차원 배열이 생성된다. 0 A C A Y K P 0 0 0 0 0 0 0 0 C 0 0 1 1 1 1 1 A 0 1 1 2 2 2 2 P 0 1 1 2 2 2 3 C 0 1 2 2 2 2 3 A 0 1 2 3 3 3 3 K 0 1 2 3 3 4 4 이때 확인 할 수 있는 것은 다음과 같다.(파랑색은 증가한 경우, 빨강색은 알파벳이 같아도 증가하지 않는경우) 1. 알파벳이 ..