티스토리 뷰

이론

LCS(최장 공통 부분 수열)

절취선 2021. 2. 9. 14:57
반응형
최장 공통 부분 수열(LCS)은 LIS 최장 증가 부분 수열과 비슷하게 생각하면 된다. LCS 또한 LIS와 같이 DP(동적 계획법)을 기반으로 한다. LCS 알고리즘을 통해 두개의 문자열을 비교하여 공통 부분 수열의 길이를 구할 수 있다. 주의할 점은 LCS는 Longest Common Substring과 Longest Common Subsequence이 존재한다. 공통 부분 문자열(Longest Common Substring), 공통 부분 수열(Longest Common Subsequence)이라고 말할 수 있다. 2개는 다른 의미를 가지고 있기 때문에 구분해야한다. 차이점은 연속 여부이다.
반응형

'이론' 카테고리의 다른 글

HTTP 상태와 요청  (0) 2022.02.26
Mutex VS Semaphore  (0) 2022.02.26
[Dynamic Programming] 로보트  (0) 2021.02.10
Quicksort  (0) 2021.02.09
[정렬] HeapSort  (0) 2021.02.09
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
글 보관함