9251번
-
LCS(최장 공통 부분 수열) 알고리즘 :: 마이구미알고리즘 2017. 2. 17. 15:09
이번 글은 LCS(Longest Common Subsequence) 알고리즘은 다뤄본다. 최장 공통 부분 수열(LCS)은 LIS 최장 증가 부분 수열과 비슷하게 생각하면 된다.LCS 또한 LIS와 같이 DP(동적 계획법)을 기반으로 한다.LCS 알고리즘을 통해 두개의 문자열을 비교하여 공통 부분 수열의 길이를 구할 수 있다. 주의할 점은 LCS는 Longest Common Substring과 Longest Common Subsequence이 존재한다.공통 부분 문자열(Longest Common Substring), 공통 부분 수열(Longest Common Subsequence)이라고 말할 수 있다.2개는 다른 의미를 가지고 있기 때문에 구분해야한다.차이점은 연속 여부이다. 최장 공통 문자열의 길이는 3..