LCS는 'Longest Common Subsequence'의 약어로, 두 개의 수열에서 공통적으로 등장하는 부분 수열 중 가장 긴 것을 찾는 문제를 의미한다. LCS 문제는 주로 문자열 비교와 유사도 분석에 사용되며, 컴퓨터 과학 및 정보 이론에서 중요한 역할을 한다.

LCS는 동적 프로그래밍 기법을 사용하여 효율적으로 해결할 수 있다. 입력으로 주어진 두 개의 수열 A와 B에 대해, 이들 각각의 길이를 n과 m이라고 할 때, LCS의 길이를 저장하는 2차원 배열을 생성하여 점차적으로 값을 계산해 나간다. 일반적으로 dp[i][j]는 A의 처음 i개의 요소와 B의 처음 j개의 요소 사이의 LCS 길이를 나타낸다. 이 때, 점화식은 다음과 같다.

1. A의 i번째 요소와 B의 j번째 요소가 동일하면:

dp[i][j] = dp[i-1][j-1] + 1

2. A의 i번째 요소와 B의 j번째 요소가 다르면:

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

최종적으로 dp[n][m]의 값이 두 수열 A와 B의 LCS의 길이를 나타낸다.

LCS는 다양한 분야에서 활용되며, 특히 버전 관리 시스템, 텍스트 비교 및 유사도 계산 등에서 중요한 알고리즘으로 자리 잡고 있다. LCS 문제의 시간 복잡도는 O(n*m)으로, 수열의 길이에 비례한다. 공간 복잡도는 dp 배열을 사용하기 때문에 O(n*m)이며, 이를 최적화하여 O(min(n, m))으로 줄일 수 있는 방법도 존재한다.