dp
-
LCS (Longest Common Subsequence) 최장 공통 부분 수열💻 프로그래밍/알고리즘 2019. 6. 23. 16:42
안녕하세요! 코딩하는 JAY입니다. 오늘은 오랜만에 알고리즘 포스팅을 하려고 합니다:D 오늘 포스팅할 내용은 LCS, 최장 공통 부분 수열입니다. 주의해야할 점은 LCS가 두개라는 점입니다. 1. 최장 공통 부분 수열 = Longest Common Subsequence 2. 최장 공통 부분 문자열 = Longest Common Substring 이 두개의 차이저을 아래 예시로 말씀드리겠습니다. 1. ABCD, ABZC = AB 2. ABCD, ABZC = ABC 1번과 2번 예시의 차이점을 아시겠나요? 아마 차이점을 바로 눈치채셨을것 같아요 ㅋㅋㅋ 1번은 두개의 문자열을 비교했을때, 연속적인 문자열을 추출합니다. 2번은 공통된 부분 수열을 추출합니다(연속X) 여기서 핵심은 연속이냐? 아니냐 입니다 ㅎㅎ ..