LCS 문제

LCS 문제 LCS란 Longest Common Subsequence 혹은 Longest Common String 의 약자다. LCS 문제는 특정 문자가 같은 지 여부에 따라 테이블에 기록하는 형식으로 길이와 부분 문자열을 구할 수 있다. 즉, 동적계획법을 활용하여 문제를 풀 수 있다. 문제접근법 LCS 문제는 동적 프로그래밍 접근법에 따라 해결한다. 1. 문재의 해를 분석한 후 부분문제로 분할한다. 2. 부분문제의 해를 보고 큰 문제와의 관계식을 세운다.(점화식 설계) 3. 적당한 순서로 dp table을 채운다. 4. table에서 해를 계산한 후에 정확성을 증명한다.동적계획법에서 중요한 부분은 큰문제와 작은문제의 관계로부터 재귀형태를 찾아 dp table을 채우는 것이다. 정확성 증명은 테이블 채우..