LCS최장 공통 부분 수열 알고리즘은, 여러 문자열의 부분 수열 중 가장 긴 수열을 찾는 알고리즘이다.여기서는 두 개의 수열에 대한 해만 다룰 것이다.diff 프로그램의 근간이되는 알고리즘이다.시간 복잡도주어진 수열의 개수가 일정할 때 DP(Dynamic Programming), 동적 계획법으로 풀이할 수 있다.길이가 N과 M인 두 수열이 주어졌을 때 일반적으로 O(N * M)의 시간복잡도를 가진다.LCS 문제의 풀이LCS는 *optimal substructure와 **overlapping subproblems 성격을 지니고 있다. 두 속성을 공유하는 경우 하위 부분 문제들에 대한 최적해를 저장한 메모이제이션 기법을 통한 DP풀이를 사용할 수 있다.*optimal substructure: 하위 문제의 최..
