최장 공통 부분 수열 (LCS, Longest Common Subsequence)

최장 공통 부분 수열 (LCS, Longest Common Subsequence)

두 문자열의 공통 부분 수열 중 가장 긴 것을 찾는 동적 프로그래밍 문제

목적: 문자열 유사도, diff 도구, DNA 서열 비교

특징: 동적 프로그래밍, 2D 테이블, 최적 부분 구조

점화식: dp[i][j] = (s1[i]==s2[j]) ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1])

시간 복잡도: O(mn) - m, n = 문자열 길이

공간 복잡도: O(mn) - 테이블, O(n) 최적화 가능

역추적(Backtracking): 테이블에서 선택 경로 추적하여 LCS 복원

장점: 정확한 최장 부분 수열, 다양한 응용

단점: O(mn) 시공간, 대규모 문자열 비효율

적용사례: diff 도구(git diff), 파일 비교, DNA 서열 정렬, 표절 검사, 버전 관리

비교: LCS(부분수열/순서유지/불연속) vs 최장 공통 부분 문자열(연속)

연관: 동적 프로그래밍, 편집 거리, diff, 문자열