핵심 인사이트 (3줄 요약)

  1. 본질: LCS (Longest Common Subsequence, 최장 공통 부분 수열)는 두 수열(문자열)에서 순서를 유지하면서 공통으로 존재하는 가장 긴 부분 수열을 찾는 동적 프로그래밍(DP, Dynamic Programming) 문제로, 원소의 연속성(연속 배열 여부)은 요구하지 않는다.
  2. 가치: O(mn) 시간복잡도와 O(mn) 공간복잡도로 최적해를 보장하며, git diff, DNA 서열 비교, 버전 관리, 표절 검사 등 두 시퀀스의 유사도를 측정해야 하는 모든 실무 영역에 핵심 알고리즘으로 활용된다.
  3. 판단 포인트: LCS 길이 L과 원래 수열 길이 n의 비율로 두 수열의 유사도를 정량화하며, 편집 거리(Edit Distance)와 달리 삽입·삭제 비용을 따지지 않고 공통 구조만 추출하므로 서열 유사도 판단에 더 적합하다.

Ⅰ. 개요 및 필요성

LCS (Longest Common Subsequence, 최장 공통 부분 수열)는 두 시퀀스 X와 Y에서 양쪽 모두에 포함되고 원래 순서를 유지하는 가장 긴 공통 서브시퀀스를 구하는 알고리즘이다.

예: X = "ABCBDAB", Y = "BDCAB"의 LCS = "BCAB" 또는 "BDAB" (길이 4).

LCS가 없으면 두 파일의 차이(diff)를 계산할 수 없고, 생물정보학에서 유전자 서열의 유사성을 정량화할 수 없다. 브루트포스로는 2^n 가지 부분 수열을 모두 비교해야 하므로 동적 프로그래밍으로 O(mn)으로 해결하는 것이 필수다.

┌───────────────────────────────────────────────────────┐
│          LCS DP 테이블 구축 (X="ABCB", Y="BCB")       │
├───────────────────────────────────────────────────────┤
│                                                       │
│       ""  B  C  B                                     │
│   ""  [0][0][0][0]                                    │
│   A   [0][0][0][0]   A≠B,C,B → 0                     │
│   B   [0][1][1][1]   B=B → dp[i-1][j-1]+1 = 1        │
│   C   [0][1][2][2]   C=C → dp[i-1][j-1]+1 = 2        │
│   B   [0][1][2][3]   B=B → dp[i-1][j-1]+1 = 3        │
│                                                       │
│  LCS 길이 = dp[4][3] = 3 → "BCB"                     │
└───────────────────────────────────────────────────────┘
  • 📢 섹션 요약 비유: LCS는 두 사람의 여행 사진 앨범에서 같은 장소를 순서대로 방문한 공통 여행지 목록을 찾는 것과 같다. 같은 사진이 이어서 나오지 않아도 되고, 순서만 같으면 공통 여행지로 인정된다.

Ⅱ. 아키텍처 및 핵심 원리

점화식 (Recurrence Relation)

dp[i][j] = dp[i-1][j-1] + 1          (X[i] == Y[j])
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (X[i] != Y[j])

DP 테이블 역추적 (Backtracking)

┌──────────────────────────────────────────────────────┐
│               역추적으로 실제 LCS 복원                 │
├──────────────────────────────────────────────────────┤
│                                                      │
│  dp[i][j] 기준 역추적:                                │
│                                                      │
│  if X[i] == Y[j]:                                    │
│      → LCS에 X[i] 추가, dp[i-1][j-1]로 이동           │
│  else if dp[i-1][j] > dp[i][j-1]:                   │
│      → dp[i-1][j]로 이동 (위쪽)                       │
│  else:                                               │
│      → dp[i][j-1]로 이동 (왼쪽)                       │
└──────────────────────────────────────────────────────┘

시간복잡도: O(mn), 공간복잡도: O(mn) (롤링 배열 사용 시 O(min(m,n))으로 최적화 가능).

  • 📢 섹션 요약 비유: DP 테이블은 두 수열의 교차점마다 공통 서열의 길이를 메모하는 점수판이다. 역추적은 점수판의 최고점에서 출발해 어디서 점수가 올랐는지 되짚어 가며 실제 경로를 복원하는 과정이다.

Ⅲ. 비교 및 연결

알고리즘목적연속성시간복잡도
LCS순서 유지 공통 부분 수열불필요O(mn)
LCS (연속)연속 공통 부분 문자열필수O(mn)
편집 거리(Edit Distance)최소 편집 횟수불필요O(mn)
KMP / Rabin-Karp패턴 검색필수O(m+n)

LCS는 diff 유틸리티의 기반이며, git의 파일 변경 내역 추적, 자연어 처리(NLP)의 문장 유사도 측정에도 활용된다.

  • 📢 섹션 요약 비유: LCS는 두 악보에서 음표 순서가 같은 가장 긴 멜로디를 찾는 것이고, 편집 거리는 두 악보를 같게 만들기 위해 몇 음표를 바꿔야 하는지 세는 것이다.

Ⅳ. 실무 적용 및 기술사 판단

실무 시나리오: git diff 엔진

두 버전의 소스파일 변경 내역을 계산한다.

  1. 파일 A와 B를 라인 단위 배열로 분리.
  2. LCS로 두 배열의 공통 라인(변경 없는 줄) 추출.
  3. LCS에 포함되지 않은 A의 라인 = 삭제(−), B의 라인 = 추가(+)로 출력.

체크리스트

  • 입력이 매우 큰 경우(수십만 라인) Hirschberg 알고리즘(O(min(m,n)) 공간)으로 메모리 최적화.
  • DNA 서열 비교 시 Smith-Waterman(지역 정렬) vs LCS(전역 정렬) 목적에 맞게 선택.

안티패턴

  • LCS와 LCS(연속)을 혼동하는 오류. LCS는 순서만 같으면 되지만, 문자열 검색에서 필요한 연속 공통 부분 문자열(Longest Common Substring)은 다른 알고리즘이다.

  • 📢 섹션 요약 비유: LCS는 두 여행자가 같은 나라를 같은 순서로 방문한 기록이다. 반드시 이어서 방문하지 않아도 된다. 반면 연속 LCS는 이어서 방문한 국가들만 인정한다.

Ⅴ. 기대효과 및 결론

기대효과내용수치
유사도 정량화두 시퀀스의 유사도를 LCS/max(m,n)으로 0~1 정규화DNA 분류 정확도 95%+
diff 최소화최소 변경 집합 계산git diff 계산 성능 O(mn)
표절 탐지문서 간 공통 구조 비율 측정논문 유사도 탐지 활용

LCS는 DP의 교과서적 예제이면서도 실무에서 가장 많이 응용되는 알고리즘 중 하나다. 미래에는 딥러닝 기반 시퀀스 임베딩과 결합하여 의미론적(Semantic) 유사도 측정으로 진화하고 있다.

  • 📢 섹션 요약 비유: LCS는 두 악보에서 같은 음정이 같은 순서로 나타나는 가장 긴 공통 멜로디를 찾아내는 수학적 악보 편집자다.

📌 관련 개념 맵

개념연결 포인트
동적 프로그래밍(DP)LCS의 핵심 해법; 부분 문제 결과를 저장해 중복 계산 제거
편집 거리(Edit Distance)LCS의 쌍둥이 문제; 두 시퀀스를 같게 만드는 최소 연산 수
Hirschberg 알고리즘LCS를 선형 공간(O(min(m,n)))으로 구현하는 최적화 버전
git diffLCS 기반으로 두 파일의 추가/삭제 라인을 계산하는 실무 응용

📈 관련 키워드 및 발전 흐름도

[브루트포스 — 2^n 부분 수열 전수 비교]
    │
    ▼
[LCS DP — O(mn) 최적 해법, 테이블 역추적]
    │
    ▼
[Hirschberg 알고리즘 — O(mn) 시간 + O(min(m,n)) 공간]
    │
    ▼
[실무 응용 — git diff, DNA 서열 분석, 표절 탐지]
    │
    ▼
[딥러닝 유사도 — 임베딩 기반 의미론적 LCS 확장]

브루트포스에서 DP 최적화, 공간 효율화를 거쳐 실무 diff 엔진과 DNA 분석에 응용되며, 의미론적 유사도 탐지로 진화하는 흐름이다.

👶 어린이를 위한 3줄 비유 설명

  1. LCS는 두 친구가 각자 좋아하는 영화 목록에서 같은 영화를 같은 순서로 좋아하는 가장 긴 공통 취향 목록을 찾는 것이에요!
  2. 꼭 이어서 좋아하지 않아도 돼요 — 중간에 다른 영화가 섞여도 순서만 같으면 공통 목록에 넣을 수 있어요.
  3. 컴퓨터가 두 파일을 비교해서 "어디가 바뀌었나요?"를 보여주는 git diff도 이 방법으로 만들어진답니다!