LCS
BaekJoon(9251)::LCS
문제 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제파악 해당문제는 단순하게 제목에서부터 풀이법을 말해주고있다. Longest Common Sub-sequence Algorithm(LCS, 최장 공통 부분수열) Longest Common Sub-sequence Algorithm(LCS) LIS알고리즘을 정리하다가 비슷한류의 알고리즘으로 보여 함께 이어서 정리하려고 한다. 이문제 또한 아마 DP를 이용한 문제가 될것으로 생각된다. 다만 문자로 dev-sanghu..
Longest Common Sub-sequence Algorithm(LCS, 최장 공통 부분수열)
Longest Common Sub-sequence Algorithm(LCS) LIS알고리즘을 정리하다가 비슷한류의 알고리즘으로 보여 함께 이어서 정리하려고 한다. 이문제 또한 아마 DP를 이용한 문제가 될것으로 생각된다. 다만 문자로 이루어진 수열이기에 LIS에서 사용했던 이분탐색은 불가능해보인다. 그리고 해당 문제에서도 길이 뿐만이 아닌 해당 부분수열을 구하는 방법도 알아보도록 하겠다. 정의(Definition) 최장 공통 부분수열으로 두 문자열의 가장 긴 공통된 부분문자열을 구하는 문제 Longest Common Sub-sequence 불린다. 여기서 string이 아닌 sequence는 사용하는 이유는 각 단어가 갖는 개념적 의미가 다르기 때문이다. string : 연속된 문자열 sequence :..