LCS 문제 풀이방식에 대한 이해

최장 공통 부분수열(Longest Common Subsequence, LCS) 문제를 풀기 위한 사전 지식을 다졌습니다. DP 테이블의 구조, 점화식 유도 과정, 그리고 그 근거가 되는 논리까지 차근차근 이해할 수 있었습니다.

학습 주제

• 공부 주제: 최장 공통 부분수열(LCS) 문제 풀이를 위한 동적 계획법(DP) 사전 지식
• 학습 날짜: 2026년 2월 14일

질문과 탐구

학습은 LCS 문제 풀이에 필요한 DP 지식과 문자열 처리 방법을 알아가는 것에서 시작했습니다. 특히, dp[i][j]가 무엇을 의미하는지, 이전 상태를 어떻게 활용하여 현재 상태를 결정하는지, 그리고 테이블을 채우는 방향과 순서가 왜 중요한지에 대한 질문들이 이어졌습니다.

핵심 학습 내용

LCS는 두 수열에서 공통으로 나타나는 부분수열 중 가장 긴 것을 찾는 문제입니다. 여기서 '부분수열'은 원본 수열의 원소를 0개 이상 제거하여 만든 수열로, 남은 원소들의 상대적 순서는 유지되어야 한다는 점이 중요합니다.

DP를 통해 LCS 길이를 구하는 핵심은 dp[i][j]를 정의하고 점화식을 세우는 것입니다.

DP 테이블 정의 및 점화식

• dp[i][j]: 첫 번째 문자열의 i번째 인덱스까지, 두 번째 문자열의 j번째 인덱스까지 봤을 때의 최장 공통 부분수열의 길이. (일반적으로 1-based indexing을 사용하며, i와 j는 문자열의 길이를 나타냅니다.)

점화식은 두 가지 경우로 나뉩니다.

1. 문자가 같은 경우 (str1[i-1] == str2[j-1]):

   • dp[i][j] = dp[i-1][j-1] + 1
   • 이유: 현재 문자가 같으므로, 이전까지의 최장 공통 부분수열 (dp[i-1][j-1])에 현재 문자를 추가하여 길이를 1 늘릴 수 있습니다. 이는 (i, j) 위치에 도달하기 위한 유일하게 가능한 이전 상태인 왼쪽 위 대각선 (dp[i-1][j-1])을 참조하여, 해당 시점에서 이어붙일 수 있는 최적의 경로를 찾는 것입니다.

2. 문자가 다른 경우 (str1[i-1] != str2[j-1]):

   • dp[i][j] = max(dp[i-1][j], dp[i][j-1])
   • 이유: 현재 문자가 다르므로, 현재 문자를 LCS에 포함시킬 수 없습니다. 따라서 이전까지의 최장 공통 부분수열 길이를 유지해야 합니다. 선택지는 다음과 같습니다:
     • 첫 번째 문자열의 i번째 문자를 버리고 진행 (dp[i-1][j])
     • 두 번째 문자열의 j번째 문자를 버리고 진행 (dp[i][j-1])
       이 두 경로 중 더 긴 길이를 선택하여 dp[i][j]에 저장합니다. 이는 서로 다른 경로에서 최적해를 탐색하고, 더 나은 결과를 취하는 DP의 기본 원리입니다.

탐구 과정에서의 중요한 포인트

• 테이블 구조: 행에는 첫 번째 문자열, 열에는 두 번째 문자열을 배치하는 것이 일반적입니다.
• 계산 방향: 테이블은 왼쪽에서 오른쪽, 위에서 아래로 순차적으로 채워져야 합니다. 이는 부분수열의 순서 조건을 유지하고, dp[i][j]를 계산할 때 필요한 이전 값들 (dp[i-1][j], dp[i][j-1], dp[i-1][j-1])이 이미 계산되어 있도록 보장합니다.
• 초기화: 첫 행과 첫 열은 빈 문자열과의 비교이므로 모두 0으로 초기화합니다. 이는 LCS에 공통 문자가 없을 경우 최종 결과가 0이 되도록 하며, dp[i-1][j-1] 참조 시 가비지 값을 방지합니다.
• 최종 답: LCS의 길이는 테이블의 가장 오른쪽 아래 칸인 dp[n][m]에 위치합니다. 이는 모든 문자를 고려했을 때의 최장 공통 부분수열의 길이를 나타냅니다.

이해한 내용

가장 큰 진전은 dp[i][j]가 단순한 '값'이 아니라, **특정 경로를 따라 도달한 '최적의 부분해'**라는 점을 이해한 것입니다. 특히, 문자가 같을 때 왜 왼쪽 위 대각선(dp[i-1][j-1])을 참조하는지에 대한 직관적인 이해가 깊어졌습니다. 이는 (i, j)에서 공통문자를 발견했을 때, 그 이전까지의 LCS를 그대로 이어붙일 수 있는 유일하게 '정상적인' 경로이기 때문입니다. 즉, (i-1, j-1)까지의 경로가 현재 (i, j)에서의 공통 문자와 자연스럽게 연결될 수 있는 최적의 상태를 보장합니다.

문자가 다를 때 max(dp[i-1][j], dp[i][j-1])을 사용하는 것은, 현재 (i, j)에서 공통문자를 찾지 못했기 때문에 둘 중 하나를 '포기'해야 하지만, 어떤 경로로 포기하든 그 이전까지의 최적의 LCS 길이를 참조하여 가능한 가장 긴 길이를 찾아가는 과정이라는 것을 명확히 알게 되었습니다.

실전 적용

이 DP 원리는 다양한 최적 경로 찾기 문제에 응용될 수 있습니다.

• 단백질 서열 정렬: 두 단백질 서열의 유사성을 비교하는 데 사용될 수 있습니다.
• 버전 관리 시스템: 파일의 차이를 비교하고 병합하는 데 활용될 수 있습니다.
• 최단 편집 거리 (Edit Distance): 두 문자열을 같게 만들기 위한 최소 삽입, 삭제, 교체 횟수를 계산하는 알고리즘 역시 유사한 DP 구조를 가집니다.

추가 학습 계획

• LCS 부분 수열 복원: 단순히 LCS의 길이만 구하는 것을 넘어, 실제 LCS 문자열을 복원하는 방법에 대해 더 깊이 공부해보고 싶습니다. 이를 위해서는 DP 테이블을 역추적하는 과정이 필요할 것으로 예상됩니다.
• 다른 DP 관련 알고리즘: 배낭 문제, 쉬운 계단, 최장 증가 부분 수열 등 다른 DP 문제들을 풀어보며 다양한 DP 접근 방식을 익히고 싶습니다.

참고 자료

• AI와의 대화 내용 (Claude)
• LCS 복원 알고리즘 관련 문서 및 튜토리얼