최장 공통 부분 수열

작성자

익명

작성일

2026.08.01

조회수

버전

일반 문서

📋 문서 버전

이 문서는 2개의 버전이 있습니다. 현재 최신 버전을 보고 있습니다.

최장 공통 부분 수열

개요

최장통 부분 수열(Longest Subsequence, 이하 LCS)은 개 이상의 문자열(또는 수열)에서 동시에 나타나는 부분 수열(subsequence) 중 가장 긴 것을 찾는 문제입니다. 이 알고리즘은 자연어처리(NLP), 생물정보학, 버전 관리 시스템(예: git diff), 텍스트 비교 도구 등 다양한 분야에서 핵심적으로 활용됩니다.

부분 수열이란 원래 수열에서 일부 요소를 삭제하여 얻을 수 있는 새로운 수열을 의미하며, 요소의 순서는 유지되어야 하지만, 연속적일 필요는 없습니다. 예를 들어, 수열 ABCBDAB의 부분 수열에는 ABD, BCB, ABBA 등이 포함될 수 있습니다.

LCS는 문자열 간의 유사도를 측정하는 데 유용하며, 특히 자연어처리에서는 문서 간 유사성 분석, 기계 번역 평가, 오타 수정, 문장 정렬 등에 응용됩니다.

알고리즘 원리

1. 문제 정의

두 수열 X = x₁, x₂, ..., xₘ과 Y = y₁, y₂, ..., yₙ이 주어졌을 때, X와 Y의 공통 부분 수열 중 길이가 가장 긴 것을 찾는 것이 목표입니다.

예: - X = "AGCAT" - Y = "GACAT" - 가능한 공통 부분 수열: "ACAT", "GAT", "GCAT" 등 - 최장 공통 부분 수열: "GAT" 또는 "ACAT" (길이 4)

2. 동적 프로그래밍 접근

LCS 문제는 동적 프로그래밍(Dynamic Programming, DP)을 통해 효율적으로 해결할 수 있습니다. 이 방법은 중복된 하위 문제를 저장하고 재사용함으로써 시간 복잡도를 줄입니다.

점화식 (Recurrence Relation)

L[i][j]를 X의 첫 i개 문자와 Y의 첫 j개 문자의 LCS 길이라고 정의합니다.

L[0][j] = 0 (X가 빈 문자열)
L[i][0] = 0 (Y가 빈 문자열)
만약 X[i-1] == Y[j-1], 즉 마지막 문자가 같으면:
L[i][j] = L[i-1][j-1] + 1
그렇지 않으면:
L[i][j] = max(L[i-1][j], L[i][j-1])

이 점화식을 바탕으로 m×n 크기의 2차원 테이블을 채워 나갑니다.

예시 계산

X = "ABCD", Y = "ACBD"

	A	C	B	D
Ø	0	0	0	0
A	1	1	1	1
B	1	1	2	2
C	1	2	2	2
D	1	2	2	3

최종 값 L[4][4] = 3이며, 실제 LCS는 "ABD" 또는 "ACD"입니다.

알고리즘 구현

다음은 Python을 사용한 LCS 길이 계산 및 실제 수열 복원 예시입니다:

def lcs_length_and_sequence(X, Y):
    m, n = len(X), len(Y)
    # DP 테이블 초기화
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 테이블 채우기
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # LCS 수열 복원
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            lcs.append(X[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
    return dp[m][n], ''.join(reversed(lcs))

# 사용 예
X = "AGCAT"
Y = "GACAT"
length, sequence = lcs_length_and_sequence(X, Y)
print(f"LCS 길이: {length}, 수열: {sequence}")  # 출력: LCS 길이: 4, 수열: ACAT

시간 및 공간 복잡도

항목	값
시간 복잡도	O(m × n)
공간 복잡도	O(m × n)

단, 공간 최적화를 위해 두 줄만 유지하는 방식으로 공간 복잡도를 O(min(m, n))로 줄일 수 있습니다. 다만 이 경우 실제 수열 복원은 불가능하거나 추가 처리가 필요합니다.

응용 분야

1. 자연어처리 (NLP)

문서 유사도 측정: 두 문장 또는 문서의 LCS를 통해 구조적 유사성을 분석합니다.
오타 감지 및 수정: 입력 문장과 정답 문장을 비교해 차이를 식별합니다.
기계 번역 평가: 예측 문장과 참조 문장의 LCS를 기반으로 정확도를 계산합니다.

2. 버전 제어 시스템

git diff나 diff 명령어는 LCS 알고리즘을 기반으로 파일 간 변경 사항을 비교합니다.
추가/삭제된 부분을 추적하기 위해 LCS의 보완 알고리즘인 Myers diff 알고리즘이 사용됩니다.

3. 생물정보학

DNA 또는 단백질 서열 정렬에 활용됩니다.
유사한 유전자 서열을 찾는 데 중요한 기초 기술입니다.

DP 이론적 근거

LCS 문제는 동적 프로그래밍의 두 가지 핵심 성질을 모두 만족합니다.

최적 부분 구조 (Optimal Substructure): 전체 문제의 최적해(LCS 길이)가 하위 문제의 최적해들로부터 구성됩니다. 즉, 두 수열의 마지막 문자가 같으면 그 이전까지의 LCS 길이에 1을 더한 것이 전체의 최적해가 되며, 다르면 두 가지 가능한 하위 문제(한쪽 수열의 마지막 문자를 제외한 경우) 중 더 큰 값이 최적해가 됩니다.
중복 부분 문제 (Overlapping Subproblems): 재귀적으로 문제를 해결할 때 동일한 하위 문제(특정 인덱스 $i, j$에서의 LCS 계산)가 반복적으로 호출됩니다. 이를 메모이제이션(Memoization)이나 테이블 채우기 방식으로 저장함으로써 중복 계산을 방지하고 효율성을 높입니다.

공간 복잡도 최적화 원리

LCS의 점화식을 살펴보면 L[i][j]를 계산하기 위해 오직 현재 행(i)과 이전 행(i-1)의 정보만 필요합니다. 따라서 $m \times n$ 전체 테이블을 유지할 필요 없이, 두 개의 행(또는 하나의 행과 임시 변수)만 사용하여 공간 복잡도를 $O(\min(m, n))$으로 최적화할 수 있습니다.

행 저장 방식 비교

구분	기본 DP 방식	공간 최적화 방식
저장 구조	$m \times n$ 2차원 배열	$2 \times n$ (또는 $1 \times n$) 1차원 배열
공간 복잡도	$O(m \times n)$	$O(\min(m, n))$
수열 복원	테이블 역추적으로 가능	불가능 (길이만 계산 가능)
메모리 사용	수열 길이에 비례해 급격히 증가	수열 길이에 선형적으로 증가

편집 거리 관계식의 적용

편집 거리(Edit Distance)와 LCS의 관계식 $\text{편집 거리} = m + n - 2 \times \text{LCS}$는 치환(Substitution) 연산이 허용되지 않고 삽입(Insertion)과 삭제(Deletion)만 가능할 때 성립합니다.

적용 예시: - 수열 $X = \text{"ABC"}$ ($m=3$), $Y = \text{"ACD"}$ ($n=3$) - $\text{LCS}(X, Y) = \text{"AC"}$ (길이 2) - 관계식 적용: $3 + 3 - (2 \times 2) = 2$ - 실제 연산 과정: "ABC" $\rightarrow$ 'B' 삭제 $\rightarrow$ "AC" $\rightarrow$ 'D' 삽입 $\rightarrow$ "ACD" (총 2회 연산) - 결과적으로 LCS를 제외한 나머지 문자들을 모두 삭제하고 새로운 문자들을 삽입하는 과정이 최소 편집 거리가 됩니다.

최적화 기법 및 변형 알고리즘

입력 데이터의 특성에 따라 기본 DP보다 효율적인 알고리즘을 사용할 수 있습니다.

Hunt-Szymanski 알고리즘: 일치하는 문자의 수($r$)가 적은 경우에 효율적입니다. 각 문자의 위치를 인덱스로 저장하여 일치하는 쌍만 처리함으로써 시간 복잡도를 $O((r + n) \log n)$으로 개선합니다. 이는 특히 소스 코드 비교와 같이 일치하는 부분이 적은 텍스트 비교에 유리합니다.
Bit-parallelism (비트 병렬성): 비트 연산을 이용하여 DP 테이블의 업데이트를 가속화하는 방식으로, 알파벳 크기가 작을 때 매우 빠른 성능을 보입니다.

다중 수열 LCS (Multiple Sequence LCS)

두 개가 아닌 $k$개의 수열 $S_1, S_2, \dots, S_k$에서 공통 부분 수열을 찾는 문제입니다.

정의: 모든 수열에 공통으로 포함되면서 길이가 가장 긴 수열을 찾는 것입니다.
복잡도: $k$개의 수열에 대해 DP를 적용하면 시간 및 공간 복잡도는 $O(n^k)$로 지수적으로 증가합니다.
계산 복잡성: 다중 수열 LCS 문제는 NP-hard임이 증명되어 있으며, 수열의 개수가 늘어날수록 최적해를 찾는 것이 매우 어렵습니다. 따라서 실제 응용에서는 근사 알고리즘(Approximation Algorithm)이나 휴리스틱 방법이 사용됩니다.

참고 자료

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (209). Introduction to Algorithms (3rd ed.). MIT Press.
Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press.
Myers, E. W. (1986). "An O(ND) Difference Algorithm and Its Variations". Algorithmica.

관련 문서

LCS는 단순해 보이지만, 실세계 응용에서 중요한 기초 알고리즘으로, 자연어처리 기술의 정교한 분석을 가능하게 합니다.

📝 마크다운 원본

이 문서의 마크다운 원본 내용입니다.

# 최장 공통 부분 수열

## 개요

**최장통 부분 수열**(Longest Subsequence, 이하 LCS)은 개 이상의 문자열(또는 수열)에서 동시에 나타나는 **부분 수열**(subsequence) 중 가장 긴 것을 찾는 문제입니다. 이 알고리즘은 **자연어처리**(NLP), **생물정보학**, **버전 관리 시스템**(예: `git diff`), **텍스트 비교 도구** 등 다양한 분야에서 핵심적으로 활용됩니다.

부분 수열이란 원래 수열에서 일부 요소를 삭제하여 얻을 수 있는 새로운 수열을 의미하며, 요소의 **순서는 유지**되어야 하지만, **연속적일 필요는 없습니다**. 예를 들어, 수열 `ABCBDAB`의 부분 수열에는 `ABD`, `BCB`, `ABBA` 등이 포함될 수 있습니다.

LCS는 문자열 간의 유사도를 측정하는 데 유용하며, 특히 자연어처리에서는 문서 간 유사성 분석, 기계 번역 평가, 오타 수정, 문장 정렬 등에 응용됩니다.

---

## 알고리즘 원리

### 1. 문제 정의

두 수열 `X = x₁, x₂, ..., xₘ`과 `Y = y₁, y₂, ..., yₙ`이 주어졌을 때, **X와 Y의 공통 부분 수열** 중 길이가 가장 긴 것을 찾는 것이 목표입니다.

예:
- `X = "AGCAT"`
- `Y = "GACAT"`
- 가능한 공통 부분 수열: `"ACAT"`, `"GAT"`, `"GCAT"` 등
- 최장 공통 부분 수열: `"GAT"` 또는 `"ACAT"` (길이 4)

### 2. 동적 프로그래밍 접근

LCS 문제는 **동적 프로그래밍**(Dynamic Programming, DP)을 통해 효율적으로 해결할 수 있습니다. 이 방법은 중복된 하위 문제를 저장하고 재사용함으로써 시간 복잡도를 줄입니다.

#### 점화식 (Recurrence Relation)

`L[i][j]`를 `X`의 첫 `i`개 문자와 `Y`의 첫 `j`개 문자의 LCS 길이라고 정의합니다.

- `L[0][j] = 0` (X가 빈 문자열)
- `L[i][0] = 0` (Y가 빈 문자열)
- 만약 `X[i-1] == Y[j-1]`, 즉 마지막 문자가 같으면:
  - `L[i][j] = L[i-1][j-1] + 1`
- 그렇지 않으면:
  - `L[i][j] = max(L[i-1][j], L[i][j-1])`

이 점화식을 바탕으로 `m×n` 크기의 2차원 테이블을 채워 나갑니다.

#### 예시 계산

`X = "ABCD"`, `Y = "ACBD"`

|   | Ø | A | C | B | D |
|---|---|---|---|---|---|
| Ø | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 1 | 1 | 1 | 1 |
| B | 0 | 1 | 1 | 2 | 2 |
| C | 0 | 1 | 2 | 2 | 2 |
| D | 0 | 1 | 2 | 2 | **3** |

최종 값 `L[4][4] = 3`이며, 실제 LCS는 `"ABD"` 또는 `"ACD"`입니다.

---

## 알고리즘 구현

다음은 Python을 사용한 LCS 길이 계산 및 실제 수열 복원 예시입니다:

```python
def lcs_length_and_sequence(X, Y):
    m, n = len(X), len(Y)
    # DP 테이블 초기화
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 테이블 채우기
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # LCS 수열 복원
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            lcs.append(X[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
    return dp[m][n], ''.join(reversed(lcs))

# 사용 예
X = "AGCAT"
Y = "GACAT"
length, sequence = lcs_length_and_sequence(X, Y)
print(f"LCS 길이: {length}, 수열: {sequence}")  # 출력: LCS 길이: 4, 수열: ACAT
```

---

## 시간 및 공간 복잡도

| 항목 | 값 |
|------|----|
| **시간 복잡도** | O(m × n) |
| **공간 복잡도** | O(m × n) |

단, 공간 최적화를 위해 **두 줄만 유지**하는 방식으로 공간 복잡도를 `O(min(m, n))`로 줄일 수 있습니다. 다만 이 경우 실제 수열 복원은 불가능하거나 추가 처리가 필요합니다.

---

## 응용 분야

### 1. 자연어처리 (NLP)
- **문서 유사도 측정**: 두 문장 또는 문서의 LCS를 통해 구조적 유사성을 분석합니다.
- **오타 감지 및 수정**: 입력 문장과 정답 문장을 비교해 차이를 식별합니다.
- **기계 번역 평가**: 예측 문장과 참조 문장의 LCS를 기반으로 정확도를 계산합니다.

### 2. 버전 제어 시스템
- `git diff`나 `diff` 명령어는 LCS 알고리즘을 기반으로 파일 간 변경 사항을 비교합니다.
- 추가/삭제된 부분을 추적하기 위해 LCS의 보완 알고리즘인 **Myers diff 알고리즘**이 사용됩니다.

### 3. 생물정보학
- DNA 또는 단백질 서열 정렬에 활용됩니다.
- 유사한 유전자 서열을 찾는 데 중요한 기초 기술입니다.

---

## 관련 알고리즘 및 확장

- **최장 공통 부분 문자열**(Longest Common Substring): 부분 수열이 아닌 **연속된 부분 문자열**을 찾는 문제입니다. DP 접근법이 유사하지만 조건이 다릅니다.
- **편집 거리**(Edit Distance): 삽입, 삭제, 치환을 통해 한 문자열을 다른 문자열로 변환하는 최소 연산 횟수. LCS와 밀접한 관련이 있으며, `편집 거리 = m + n - 2 × LCS`로 근사 가능합니다.
- **Hirschberg’s 알고리즘**: 공간 복잡도 `O(min(m, n))`를 유지하면서 실제 LCS 수열을 복원할 수 있는 분할 정복 기반 알고리즘입니다.

---

## DP 이론적 근거

LCS 문제는 동적 프로그래밍의 두 가지 핵심 성질을 모두 만족합니다.

*   **최적 부분 구조 (Optimal Substructure)**: 전체 문제의 최적해(LCS 길이)가 하위 문제의 최적해들로부터 구성됩니다. 즉, 두 수열의 마지막 문자가 같으면 그 이전까지의 LCS 길이에 1을 더한 것이 전체의 최적해가 되며, 다르면 두 가지 가능한 하위 문제(한쪽 수열의 마지막 문자를 제외한 경우) 중 더 큰 값이 최적해가 됩니다.
*   **중복 부분 문제 (Overlapping Subproblems)**: 재귀적으로 문제를 해결할 때 동일한 하위 문제(특정 인덱스 $i, j$에서의 LCS 계산)가 반복적으로 호출됩니다. 이를 메모이제이션(Memoization)이나 테이블 채우기 방식으로 저장함으로써 중복 계산을 방지하고 효율성을 높입니다.

## 공간 복잡도 최적화 원리

LCS의 점화식을 살펴보면 `L[i][j]`를 계산하기 위해 오직 **현재 행(`i`)**과 **이전 행(`i-1`)**의 정보만 필요합니다. 따라서 $m \times n$ 전체 테이블을 유지할 필요 없이, 두 개의 행(또는 하나의 행과 임시 변수)만 사용하여 공간 복잡도를 $O(\min(m, n))$으로 최적화할 수 있습니다.

**행 저장 방식 비교**

| 구분 | 기본 DP 방식 | 공간 최적화 방식 |
| :--- | :--- | :--- |
| **저장 구조** | $m \times n$ 2차원 배열 | $2 \times n$ (또는 $1 \times n$) 1차원 배열 |
| **공간 복잡도** | $O(m \times n)$ | $O(\min(m, n))$ |
| **수열 복원** | 테이블 역추적으로 가능 | 불가능 (길이만 계산 가능) |
| **메모리 사용** | 수열 길이에 비례해 급격히 증가 | 수열 길이에 선형적으로 증가 |

## 편집 거리 관계식의 적용

편집 거리(Edit Distance)와 LCS의 관계식 $\text{편집 거리} = m + n - 2 \times \text{LCS}$는 **치환(Substitution) 연산이 허용되지 않고 삽입(Insertion)과 삭제(Deletion)만 가능할 때** 성립합니다.

**적용 예시:**
- 수열 $X = \text{"ABC"}$ ($m=3$), $Y = \text{"ACD"}$ ($n=3$)
- $\text{LCS}(X, Y) = \text{"AC"}$ (길이 2)
- 관계식 적용: $3 + 3 - (2 \times 2) = 2$
- 실제 연산 과정: `"ABC"` $\rightarrow$ `'B'` 삭제 $\rightarrow$ `"AC"` $\rightarrow$ `'D'` 삽입 $\rightarrow$ `"ACD"` (총 2회 연산)
- 결과적으로 LCS를 제외한 나머지 문자들을 모두 삭제하고 새로운 문자들을 삽입하는 과정이 최소 편집 거리가 됩니다.

## 최적화 기법 및 변형 알고리즘

입력 데이터의 특성에 따라 기본 DP보다 효율적인 알고리즘을 사용할 수 있습니다.

*   **Hunt-Szymanski 알고리즘**: 일치하는 문자의 수($r$)가 적은 경우에 효율적입니다. 각 문자의 위치를 인덱스로 저장하여 일치하는 쌍만 처리함으로써 시간 복잡도를 $O((r + n) \log n)$으로 개선합니다. 이는 특히 소스 코드 비교와 같이 일치하는 부분이 적은 텍스트 비교에 유리합니다.
*   **Bit-parallelism (비트 병렬성)**: 비트 연산을 이용하여 DP 테이블의 업데이트를 가속화하는 방식으로, 알파벳 크기가 작을 때 매우 빠른 성능을 보입니다.

## 다중 수열 LCS (Multiple Sequence LCS)

두 개가 아닌 $k$개의 수열 $S_1, S_2, \dots, S_k$에서 공통 부분 수열을 찾는 문제입니다.

*   **정의**: 모든 수열에 공통으로 포함되면서 길이가 가장 긴 수열을 찾는 것입니다.
*   **복잡도**: $k$개의 수열에 대해 DP를 적용하면 시간 및 공간 복잡도는 $O(n^k)$로 지수적으로 증가합니다.
*   **계산 복잡성**: 다중 수열 LCS 문제는 [NP-hard](https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Multiple_sequences)임이 증명되어 있으며, 수열의 개수가 늘어날수록 최적해를 찾는 것이 매우 어렵습니다. 따라서 실제 응용에서는 근사 알고리즘(Approximation Algorithm)이나 휴리스틱 방법이 사용됩니다.

## 참고 자료

- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (209). *Introduction to Algorithms* (3rd ed.). MIT Press.
- Gusfield, D. (1997). *Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology*. Cambridge University Press.
- Myers, E. W. (1986). "An O(ND) Difference Algorithm and Its Variations". *Algorithmica*.

---

## 관련 문서

- [동적 프로그래밍](https://ko.wikipedia.org/wiki/동적_프로그래밍)
- [편집 거리](https://ko.wikipedia.org/wiki/편집_거리)
- [Myers diff 알고리즘](https://en.wikipedia.org/wiki/Myers%27s_difference_algorithm)
- [자연어 유사도 측정](https://ko.wikipedia.org/wiki/자연어_유사도)

LCS는 단순해 보이지만, 실세계 응용에서 중요한 기초 알고리즘으로, 자연어처리 기술의 정교한 분석을 가능하게 합니다.

AI 생성 콘텐츠 안내

이 문서는 AI 모델(gemma-4-31b)에 의해 생성된 콘텐츠입니다.

주의사항: AI가 생성한 내용은 부정확하거나 편향된 정보를 포함할 수 있습니다. 중요한 결정을 내리기 전에 반드시 신뢰할 수 있는 출처를 통해 정보를 확인하시기 바랍니다.

위키너와나

최장 공통 부분 수열

📋 문서 버전

최장 공통 부분 수열

개요

알고리즘 원리

1. 문제 정의

2. 동적 프로그래밍 접근

점화식 (Recurrence Relation)

예시 계산

알고리즘 구현

시간 및 공간 복잡도

응용 분야

1. 자연어처리 (NLP)

2. 버전 제어 시스템

3. 생물정보학

관련 알고리즘 및 확장

DP 이론적 근거

공간 복잡도 최적화 원리

편집 거리 관계식의 적용

최적화 기법 및 변형 알고리즘

다중 수열 LCS (Multiple Sequence LCS)

참고 자료

관련 문서

📝 마크다운 원본

🤔 AI의 사고 과정

이 AI 생성 콘텐츠가 도움이 되었나요?