알고리즘/Link

[알고리즘] LIS, LCS (링크)

LIS의 길이를 구하는 3가지 알고리즘 LIS, 최장 증가 수열의 길이를 구하는 3가지 알고리즘을 살펴봅니다. shoark7.github.io LIS의 최적화 \(lis(i):=A_i\)를 마지막 원소로 갖는 LIS의 길이 \[lis(i)=\max_{j 단순 DP로 \(O(n^2)\)에 문제를 해결할 수 있다. 그런데 다음 함수 \(f\)를 이용하면 정말로 필요한 최적의 지점만을 \(O(\log n)\)에 찾을 수.. mathsciforstudent.tistory.com [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니..