염기서열 유사성
-
[동적계획법/Dynamic Programming]LCS 문제(최장 공통 부분 수열) 파이썬 코드알고리즘 2020. 12. 20. 21:28
동적 계획법에 대한 자세한 내용 : 2020/12/13 - [알고리즘] - Dynamic Programming (동적 계획법) what ia LCS? Longest Common Subsequence 는 의 subsequence이다. 는 와 의 common subsequence이다. Longest common subsequence? common subsequence들 중 가장 긴것. 는 와 의 LCS이다. 1. optimal substructure x=, yj=, LCS z에 대해서 마지막 부분에 대응하는 값을 떼고 생각할 수 있다. 이런식으로 작은 문제로 쪼갤 수 있다. 2. recursive x1 x2 ... xi-1 xi y1 y2 y3 ... yj-1 yj case1. xi=yi 이므로 그 이전 문..