dp (1) 썸네일형 리스트형 DP + LCS Algorithm에 대한 이해: 최장 공통 부분 수열 (Longest common subsequence problem) LCS : 최장 공통 부분수열 문제 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제이다. 다시 말해서 두개의 수열 사이에서 가장 긴 공통 부분 수열을 구하는 문제이다. 이때 주의할 점은 substring이 아니라 subsequence 이기 때문에 연속하지 않아도 된다는 것이다. LCS 풀이 접근 방법 그럼 LCS는 어떻게 구할 수 있을까? 기본 아이디어는 DP를 사용한다. 예를 들어 ACAYKP, CAPCAK 두 문자열의 LCS를 구한다고 해보자. 이때 두 문자열을 하나씩 늘려가면서 비교해가는 방법이 가장 쉬운 접근이다. 이때 DP를 사용하여 dp 테이블에 값을 저장한다. 문자열 ACAYKP와 두번째 문자열의 첫번째 char인 C와 최장 공통 수열의 길이는 1이다. 이.. 이전 1 다음
