LCS
-
LCS(최장 공통 부분 수열 - longest common subsequence) DPAlgorithm with C/Dynamic Programming 2020. 9. 28. 16:35
LCS가 처음이라면 아래에서 우선 재귀적 방법과 메모이제이션 방법을 익히고 오자. designatedroom87.tistory.com/117 LCS(최장 공통 부분 수열 - longest common subsequence) 재귀적 방법 & 중복제거의 메모이제이션 발췌 문헌 ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4 최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전 위키백과, 우.. designatedroom87.tistory.com 점화식은 아래와 같이 4가지 경우가 있다고 하였다. 1. 두 문자열의 맨 마지막 원소가 같은 원소로 끝나는 경우(LCS에 포함이 되는 경..
-
LCS(최장 공통 부분 수열 - longest common subsequence) 재귀적 방법 & 중복제거의 메모이제이션Algorithm with C/DFS 2020. 9. 27. 23:47
발췌 문헌 ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4 최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 최장 공통 부분수열 문제는 LCS라고도 불린다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종 단 두 개중 하� ko.wikipedia.org LCS 문제는 최적의 부분구조를 가진다. 이 문제는 더 작은, "부분문제"로 쪼개질 수 있고, 이것은 반복해서 자명한 부분문제가 될 때까지 더 간단한 부분문제로 쪼개질 수 있다. LCS는 또한 겹치는 부분문제를 가진다. 더 높은 부분문제에 ..