1. Longest Common Subsequence(LCS)- LCS에 대해서 알아가기 전에 substring과 subsequence의 차이에 대해서 알아보자.- substring : 연속된 부분 문자열- subsequence : 연속되지 않은 부분 문자열 - 여기서 LCS는 subsequence가 최대길이를 가질때를 알고 싶기에 나오게 된 개념이다.2. LCS 구하기- DP로 효율적으로 문제를 해결 가능하다.- LCS는 2개의 문자열을 비교하여 최장인 subsequence를 구해야한다.- 문자열 'BDCABA' 와 'ABCBDAB'가 있다고 생각해보자.- 여기서 하나의 문자열을 기준 문자열, 다른 문자열을 비교 문자열로 가정한다.- 위 표를 보면 문자열 맨 앞에 0을 추가해주었다.- 첫번째 행에 A값..
