목록알고리즘/LCS 알고리즘 (최장공통부분수열 알고리즘) (1)

프로그래밍에 대한 고찰 및 생각

[1][LCS : 최장 공통 부분 수열 알고리즘] (Longest Common Substring)

최장 공통 부분 수열( LCS : Longest common substring ) 최장 공통 부분 수열(이하 LCS)은 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제이다. 여기서 공통 부분 수열이라함은 예를 들어 ABCD ADEFB 두 문자열이 있을 때, 공통 부분 수열은 A D AD AB 라고 할 수 있다. 여기서 최장 공통 부분 수열은 이들중 가장 길이가 긴 수열이므로 AD 혹은 AB가 된다. 이 LCS를 구하기 위해서 대표적으로 사용되는 예인 ACAYKP 와 CAPCAK 로 살펴보자. 위의 표로 설명을 할텐데 안에 채워질 숫자의 의미는 해당 열와 행까지의 수열에서 LCS를 의미한다. 다음 그림을 참고해보자. 맨 첫칸부터 (0,0) 이라하면 ? 가 있는 부분은 (..
알고리즘/LCS 알고리즘 (최장공통부분수열 알고리즘) 2020. 2. 27. 14:07
이전 Prev 1 Next 다음