스터디 목표
LIS와 LCS 문제의 핵심 원리를 이해하고, 'DP 테이블의 상태를 어떻게 정의하고 채워나갈 것인가'에 대한 자신감을 얻는다.
Part 1. 모든 것의 시작: '부분 수열' 제대로 이해하기
LIS(최장 증가 부분 수열)와 LCS(최장 공통 부분 수열)를 제대로 이해하려면,
두 개념을 관통하는 핵심인 '부분 수열(Subsequence)' 이 무엇인지부터 명확히 알아야 합니다.
이것만 제대로 구분해도 앞으로의 개념 학습이 훨씬 쉬워질 거예요.
📜 "그래서, 부분 수열(Subsequence)이 뭔데?"
부분 수열은 아주 간단한 규칙을 따릅니다.
"원래 수열에서 일부 원소를 제거해서 만들 수 있는 새로운 수열"
여기서 가장 중요한 핵심 키워드는 '순서 유지' 입니다.
원래 수열에 있던 원소들의 상대적인 순서는 절대 바뀌면 안 됩니다. 다만, '부분 문자열(Substring)'처럼 원소들이 꼭 연속적으로 붙어있을 필요는 없구요.
- 예를 들어,
A = [1, 3, 2, 5, 4]라는 수열이 있다고 해봅시다. [1, 2, 4]는 A의 부분 수열이 맞습니다. (1, 2, 4의 순서가 그대로 유지되었죠?)[3, 5, 4]도 A의 부분 수열이 맞습니다.- 하지만
[1, 2, 3]은 A의 부분 수열이 아닙니다. (원래 수열에서 3이 2보다 앞에 있었는데, 순서가 뒤바뀌었기 때문입니다.)
🔍 헷갈리면 손해! '부분 문자열(Substring)'과의 명확한 비교
코딩 테스트에서 '부분 수열'과 가장 많이 헷갈리는 개념이 바로 '부분 문자열(Substring / Subarray)' 입니다.
둘의 차이는 '연속성' 에 있어요.
| 구분 | 부분 수열 (Subsequence) | 부분 문자열 (Substring / Subarray) |
|---|---|---|
| 핵심 규칙 | 순서만 유지되면 OK | 반드시 연속적으로 이어져야 함 |
| 예시 수열 | [A, B, C, D, E] |
[A, B, C, D, E] |
| 가능한 경우 | [A, C, E], [B, D] |
[B, C, D], [A, B] |
| 불가능한 경우 | [A, E, C] (순서 위배) |
[A, C, E] (연속성 위배) |
정리하자면,
- 부분 수열은 '순서를 지키는 듬성듬성한 수열'
- 부분 문자열은 '순서와 연속성을 모두 지키는 딱 붙어있는 수열'
이라고 기억하면 절대 헷갈리지 않을 겁니다.
이제 다음 파트에서는 이 개념 위에 첫 번째 미션인 '최장 증가 부분 수열(LIS)'을 쌓아 올려 봅시다.
Part 2. 첫 번째 미션: 최장 증가 부분 수열 (LIS)
하나의 수열 안에서 '가장 긴 오르막길'을 찾는 여정을 떠나봅시다.
이 문제는 동적 계획법(DP)의 단골손님이지만,
DP로 바로 뛰어들기 전에 왜 이 문제가 DP와 어울리는지,
그리고 더 직관적인(하지만 비효율적인) 방법부터 차근차근 밟아나가 보려고 해요.
🎯 2-1. 문제 정의: LIS란 무엇인가?
최장 증가 부분 수열(Longest Increasing Subsequence, LIS)이란, 주어진 수열의 '부분 수열' 중에서 각 원소가 이전 원소보다 크다는 조건을 만족하면서, 그 길이가 가장 긴 수열을 말합니다.
- 이번 스터디에서 사용할 예시 수열입니다:
arr = [1, 4, 2, 3, 1, 5, 7, 3] - 이 수열에서 만들 수 있는 '증가 부분 수열'은 여러 가지가 있어요.
[1, 4, 5, 7](길이 4)[1, 2, 3, 5, 7](길이 5)[1, 3, 5, 7](길이 4)
- 이 중에서 가장 긴 것의 길이는 5입니다. 따라서 이 수열의 LIS 길이는 5가 됩니다. 우리의 목표는 바로 이 '5'라는 값을 효율적으로 찾아내는 것입니다.
🤔 2-2. 직관적인 접근: 모든 경우의 수를 다 찾아보면 어떨까? (Naive Approach)
알고리즘을 처음 접했을 때 가장 먼저 떠올릴 수 있는, 가장 정직하고 무식한(?) 방법은 무엇일까요? 바로 만들 수 있는 모든 부분 수열을 다 구해본 뒤, 그중에서 증가하는 것들만 골라내 가장 긴 놈을 찾는 것입니다.
- 모든 부분 수열 생성:
[1, 4, 2, 3, 1, 5, 7, 3]배열의 모든 부분 수열을 만듭니다. 각 원소를 포함시키거나, 포함시키지 않거나 두 가지 선택지가 있으므로 총 $2^8 = 256$개의 부분 수열이 만들어집니다.[][1][4]- ...
[1, 4]- ...
[1, 4, 2, 3, 1, 5, 7, 3]
그런데 잠깐, 이 경우의 수가 어떻게 나온 걸까요?
각 원소마다 '이 부분 수열에 포함될 것인가, 말 것인가?' 딱 두 가지 선택지가 있기 때문이죠. 예를 들어 [A, B, C]라는 배열이 있다면, 각 원소의 선택 경우의 수를 모두 곱하는 것이니까요.
- A: 포함 O / 포함 X (2가지)
- B: 포함 O / 포함 X (2가지)
- C: 포함 O / 포함 X (2가지)
따라서 만들 수 있는 모든 경우의 수는 2 * 2 * 2 = 2^3 = 8개가 됩니다. [A, C]라는 부분 수열은 'A는 포함, B는 미포함, C는 포함'하는 선택의 한 가지 결과물인 셈입니다.
- '증가' 조건 확인: 256개의 부분 수열 각각에 대해, 원소들이 오름차순으로 정렬되어 있는지 검사합니다.
[1, 4, 5, 7]-> 증가 수열 O[4, 2, 3]-> 증가 수열 X
- 최대 길이 갱신: 조건을 만족하는 부분 수열들의 길이를 확인하며, 가장 긴 길이를 기록해 나갑니다.
이 방법은 원소의 개수(N)가 8개일 때는 256번이라 컴퓨터가 금방 처리하지만, N이 20만 되어도 $2^{20}$ (약 100만), N이 30이면 $2^{30}$ (약 10억)으로 경우의 수가 기하급수적으로 폭발합니다. 코딩 테스트 환경에서는 N이 조금만 커져도 시간 초과로 절대 통과할 수 없어요.
이처럼 무식한 방법(Brute-force)이 너무나도 비효율적이라는 사실을 확인했어요. 그렇다면 이 반복적인 계산을 줄이고, 더 똑똑하게 문제를 해결할 방법은 무엇일까요?
💡 2-3. DP로 가는 길: 왜 동적 계획법을 떠올려야 할까?
$O(2^N)$이라는 엄청난 시간 복잡도를 보고 우리는 더 나은 방법을 찾아야 한다는 것을 깨달았어요.
여기서 동적 계획법(Dynamic Programming)이 등장합니다. DP는 다음 두 가지 속성을 만족하는 문제에 강력한 힘을 발휘해요.
- 최적 부분 구조 (Optimal Substructure): 문제의 최적 해결책이, 그보다 작은 문제들의 최적 해결책들로부터 구해질 수 있다는 의미입니다. LIS에서는,
arr[i]에서 끝나는 가장 긴 수열을 찾으려면, 그 이전(i보다 작은j인덱스)에서 끝나는 가장 긴 수열들의 정보가 필요합니다. 이처럼 큰 문제의 답이 작은 문제들의 답에 의존하는 구조를 가집니다. - 중복되는 부분 문제 (Overlapping Subproblems): 작은 문제들의 결과가 여러 번 반복해서 사용됩니다. $O(2^N)$ 접근법에서는
[1, 2]라는 부분 문제를 수없이 많은 조합 속에서 반복적으로 계산하게 됩니다.
DP는 바로 이 '중복되는 계산'을 피하기 위한 전략입니다. "앞서 힘들게 계산한 문제의 정답은 일단 어딘가에 기록해두고, 나중에 같은 문제가 또 나오면 기록된 답을 그냥 꺼내 쓰자!" 라는 아이디어가 바로 DP의 핵심입니다. 이 '기록해두는 메모장' 역할을 하는 것이 바로 DP 테이블(배열)입니다.
📝 2-4. 핵심 로직 설계 ($O(N^2)$)
이제 본격적으로 DP 테이블을 채워봅시다. 이 과정이 LIS 문제의 심장부입니다.
1. 상태 정의 (가장 중요!)
DP에서 가장 먼저, 그리고 가장 명확하게 해야 할 일입니다. "DP 테이블의 각 칸이 무엇을 의미하는가?"를 정의하는 것입니다.
DP[i]=arr[i]를 반드시 마지막 원소로 포함하는 최장 증가 부분 수열의 길이
이 정의가 정말 중요합니다. 'i번째까지의 LIS 길이'가 절대 아닙니다. arr[i]가 주인공이 되어야 합니다.
무슨 말이냐면, 쉽게 말해 '누구를 주인공으로 보느냐'의 차이입니다.
arr = [10, 50, 30] 이라는 배열로 예를 들어 볼게요. i=2일 때, 즉 30을 살펴볼 때 두 정의는 완전히 다른 의미가 됩니다.
❌ 틀린 정의: 'i번째까지의 LIS 길이'
- 주인공:
arr[0]부터arr[i]까지의 '부분 배열 전체' i=2일 때:[10, 50, 30]이라는 부분 배열에서 만들 수 있는 가장 긴 증가 부분 수열을 찾습니다.- 결과:
[10, 50]이므로 길이는 2입니다. 여기서 주인공인30은 포함되지 않았습니다.
이 정보는 다음 단계 계산에 쓸모가 없습니다. 왜냐하면 30으로 끝나는 수열에 대한 정보가 없기 때문이죠.
✅ 올바른 정의: 'arr[i]를 반드시 포함하는 LIS 길이'
- 주인공: 오직
arr[i]자신 i=2일 때: 반드시30으로 끝나야 하는 가장 긴 증가 부분 수열을 찾습니다.- 결과:
30앞에 올 수 있는 숫자는10뿐이므로,[10, 30]이 만들어지고 길이는 2입니다.
이 정보는 다음 단계 계산에 매우 유용합니다. 만약 뒤에 40이 온다면, 우리는 '30으로 끝나는 LIS의 길이가 2'라는 이 정보를 활용해 [10, 30, 40](길이 3)을 바로 만들 수 있습니다.
결론적으로, arr[i]를 주인공으로 삼아야만 이전 단계의 계산 결과를 다음 단계에서 '이어 붙이는' 동적 계획법의 핵심 원리가 동작할 수 있습니다.
2. 점화식 도출
DP[i]를 어떻게 계산할 수 있을까요? arr[i] 앞에 있는 모든 원소들(arr[j], 단 j < i)을 둘러보며 arr[i]를 이어 붙일 수 있는지 확인하면 됩니다.
arr[j]가arr[i]보다 작다면(arr[j] < arr[i]),arr[i]를arr[j]로 끝나는 LIS 뒤에 붙일 수 있습니다.- 이때 만들어지는 새로운 LIS의 길이는
DP[j] + 1이 됩니다. arr[i]앞에 이런arr[j]가 여러 개 있을 수 있으므로, 그중 가장 긴 것(max(DP[j]))을 골라+1을 해준 것이DP[i]의 값이 됩니다.- 만약 앞에 붙일 원소가 없다면(즉,
arr[i]가 가장 작다면), 자기 자신만으로 길이 1짜리 LIS를 만듭니다. (모든 DP 배열의 값을 1로 초기화하면 이 경우를 처리할 수 있습니다.)
DP[i] = max(DP[j]) + 1
(단, 0 <= j < i 이고 arr[j] < arr[i])
DP[1] = 1 (종료조건)
3. 시뮬레이션: DP 테이블 채우기
이제 arr = [1, 4, 2, 3, 1, 5, 7, 3] 예시로 테이블을 직접 채워봅시다.
| i | arr[i] |
비교 과정 (j < i 이고 arr[j] < arr[i] 인 j 찾기) | DP[i] |
|---|---|---|---|
| 0 | 1 | 비교 대상 없음. 자기 자신만으로 길이 1 | 1 |
| 1 | 4 | j=0: arr[0](1) < 4. DP[0]+1 = 2. |
2 |
| 2 | 2 | j=0: arr[0](1) < 2. DP[0]+1 = 2. j=1: arr[1](4)는 2보다 큼. |
2 |
| 3 | 3 | j=0: arr[0](1) < 3. DP[0]+1 = 2. j=2: arr[2](2) < 3. DP[2]+1 = 3. (2와 3 중 더 큰 값인 3 선택) |
3 |
| 4 | 1 | arr[i]보다 작은 arr[j]가 없음. 자기 자신만으로 길이 1. |
1 |
| 5 | 5 | j=0,1,2,3: arr[0](1),arr[1](4),arr[2](2),arr[3](3) < 5.대응되는 DP값은 1,2,2,3. 이 중 max는 DP[3]=3. 따라서 3+1 = 4. |
4 |
| 6 | 7 | j=0,1,2,3,5: arr[j]들 모두 7보다 작음.대응되는 DP값은 1,2,2,3,4. 이 중 max는 DP[5]=4.따라서 4+1 = 5. |
5 |
| 7 | 3 | j=0,2,4: arr[0](1), arr[2](2), arr[4](1) < 3. 대응되는 DP값은 1,2,1. 이 중 max는 DP[2]=2.따라서 2+1 = 3. |
3 |
최종 DP 배열: DP = [1, 2, 2, 3, 1, 4, 5, 3]
4. 정답 찾기
여기서 또 하나의 함정이 있습니다. 최종 정답은 DP 배열의 마지막 값(DP[7])이 아닙니다!
LIS는 어느 원소에서든 끝날 수 있기 때문이죠. 따라서 우리가 구한 DP 배열의 최댓값이 바로 문제의 정답입니다.
정답 =
max(DP)= 5
✨ 2-5. 심화: 더 빠르게! 이진 탐색을 이용한 최적화 ($O(N \log N)$)
$O(N^2)$ 풀이의 병목 지점은 DP[i]를 구하기 위해 i 이전의 모든 j를 탐색하는 내부 반복문 때문입니다.
// arr.length = N 이라고 가정
int[] dp = new int[N];
// 1. 바깥쪽 반복문: i가 0부터 N-1까지, 총 N번 반복합니다.
for (int i = 0; i < N; i++) {
dp[i] = 1; // 자기 자신만으로 길이 1을 가지므로 초기화
// 2. 안쪽 반복문: j가 0부터 i-1까지, i번 반복합니다.
// -> DP[i] 하나를 결정하기 위해 i번의 연산이 필요합니다.
for (int j = 0; j < i; j++) {
// ... arr[j] 와 arr[i] 를 비교하고, dp[j] 값을 확인하는 연산 ...
}
}
왜 N2 인가요? 🧐
바깥쪽 반복문이 DP 테이블의 칸(DP[i])을 하나씩 채우기 위해 N번 도는 것은 쉽게 이해할 수 있습니다.
문제는 안쪽 반복문입니다. DP[i]라는 값 하나를 결정하기 위해 i 이전의 모든 j에 대해(0부터 i-1까지) 전부 확인해야 합니다.
- DP[0]을 계산할 때: 안쪽 반복문은 0번 돕니다.
- DP[1]을 계산할 때: 안쪽 반복문은 1번 돕니다 (j=0).
- DP[2]를 계산할 때: 안쪽 반복문은 2번 돕니다 (j=0, 1).
- DP[3]을 계산할 때: 안쪽 반복문은 3번 돕니다 (j=0, 1, 2).
- ...
- DP[N-1]을 계산할 때: 안쪽 반복문은 N-1번 돕니다.
결국 총 연산 횟수는 0 + 1 + 2 + 3 + ... + (N-1) 이 됩니다. 이는 등차수열의 합 공식에 따라 $\frac{(N-1) \* N}{2} = \frac{N^2 - N}{2}$ 이 됩니다.
이 과정을 더 빠르게 할 수 있을까요? 네, 이진 탐색(Binary Search)을 이용하면 $O(N \log N)$으로 최적화할 수 있습니다.
관점을 바꿔봅시다. DP 배열에 길이를 저장하는 대신, '특정 길이를 만들 수 있는 가장 작은 마지막 값'을 저장하는 새로운 배열 tails를 유지하는 것입니다.
tails 배열: LIS를 구성하는 후보들을 담는 배열.
tails의 길이가 곧 현재까지 발견한 LIS의 길이.
알고리즘:
tails라는 빈 배열을 준비합니다.arr배열의 원소를 처음부터 하나씩 순회합니다.- 현재 원소
num을tails배열의 마지막 원소와 비교합니다.num이tails의 마지막 원소보다 크다면:num을tails배열의 맨 뒤에 추가합니다. (LIS 길이가 1 증가)- 그렇지 않다면:
tails배열에서num이상의 값이 처음으로 나타나는 위치(lower bound)를 찾아, 그 위치의 값을num으로 교체합니다.
public int lengthOfLIS(int[] nums) {
// 엣지 케이스: 배열이 비어있으면 LIS의 길이는 0입니다.
if (nums == null || nums.length == 0) {
return 0;
}
// 'tails' 배열 역할을 할 ArrayList를 생성합니다.
// 이 리스트는 각 길이의 증가 부분 수열을 만들 수 있는
// 가장 작은 마지막 값을 저장합니다.
List<Integer> tails = new ArrayList<>();
// 입력 배열의 모든 숫자를 순회합니다.
for (int num : nums) {
// 이진 탐색을 사용하여 'tails' 리스트에서 num이 들어갈 위치를 찾습니다.
int idx = Collections.binarySearch(tails, num);
// binarySearch 결과가 음수이면, 해당 숫자가 리스트에 없다는 의미입니다.
// 이때 반환값은 '-(insertion point) - 1' 입니다.
// 따라서, 실제 삽입 위치는 -(idx + 1) 입니다.
if (idx < 0) {
idx = -(idx + 1);
}
// 삽입 위치가 리스트의 현재 크기와 같다면,
// num이 tails의 모든 원소보다 크다는 의미입니다.
// 이 경우, LIS의 길이가 1 증가하므로 리스트에 num을 추가합니다.
if (idx == tails.size()) {
tails.add(num);
}
// 삽입 위치가 리스트의 크기보다 작다면,
// 기존의 값을 더 작은 값인 num으로 교체(업그레이드)하여
// 미래에 더 긴 수열을 만들 수 있는 잠재력을 높입니다.
else {
tails.set(idx, num);
}
}
// 최종적으로 tails 리스트의 크기가 LIS의 길이가 됩니다.
return tails.size();
}
왜 이게 성립할까요? tails 배열의 값을 더 작은 값으로 교체하면, 같은 길이를 갖는 증가 부분 수열이라도 마지막 값이 더 작아지므로, 앞으로 더 많은 원소들이 뒤에 붙을 수 있는 '더 좋은 잠재력'을 갖게 되기 때문입니다.
시뮬레이션 (arr = [1, 4, 2, 3, 1, 5, 7, 3])
num |
tails 배열 |
설명 |
|---|---|---|
| 1 | [1] |
tails가 비어있으므로 추가. |
| 4 | [1, 4] |
4가 마지막 원소 1보다 크므로 추가. |
| 2 | [1, 2] |
2는 4보다 작음. tails에서 4의 자리를 2로 교체. |
| 3 | [1, 2, 3] |
3이 마지막 원소 2보다 크므로 추가. |
| 1 | [1, 2, 3] |
1은 1보다 작지 않음. tails에서 1의 자리를 1로 교체. (변화 없음) |
| 5 | [1, 2, 3, 5] |
5가 마지막 원소 3보다 크므로 추가. |
| 7 | [1, 2, 3, 5, 7] |
7이 마지막 원소 5보다 크므로 추가. |
| 3 | [1, 2, 3, 5, 7] |
3은 3보다 작지 않음. tails에서 3의 자리를 3으로 교체. (변화 없음) |
최종 tails 배열: [1, 2, 3, 5, 7]
정답: tails.length = 5
결론적으로 tails 배열의 각 자리는 '특정 길이의 LIS를 만들 수 있는 가장 작은 마지막 숫자'를 의미합니다.
tails[0] = 1 : 길이 1짜리 LIS를 만들 수 있는 가장 작은 마지막 값은 1이다.
tails[1] = 2 : 길이 2짜리 LIS를 만들 수 있는 가장 작은 마지막 값은 2이다. ([1, 4]보다 [1, 2]가 더 잠재력이 좋으므로 2가 차지)
...
✅ 결국 tails 배열의 '길이' 자체가 우리가 만들 수 있었던 '카드 더미의 최대 개수'가 되고, 이것이 바로 LIS의 길이가 되는 것입니다.
이 게임은 실제 LIS 수열([1, 2, 3, 5, 7])을 만드는 과정이 아니라, LIS의 '길이'를 찾기 위해 매 순간 가장 잠재력 높은 상태만 유지하는 똑똑한 전략이라고 이해할 수 있어요.
🚨중요🚨: 이 방법으로 나온 tails 배열([1, 2, 3, 5, 7])이 실제 LIS 자체와 우연히 같게 나왔지만, tails 배열이 항상 실제 LIS와 동일한 것은 아닙니다.
무슨 말이냐, 이 말은 tails 배열이 LIS의 '길이'를 알아내기 위한 똑똑한 도구일 뿐, 그 자체가 실제 LIS는 아니라는 뜻입니다.
tails 배열은 '가짜' 수열 또는 '유령' 수열이라고 생각하면 쉽습니다. 실제 역사(원래 수열의 순서)는 무시하고, 오직 LIS의 길이를 늘릴 '잠재력'이 가장 높은 숫자들만 모아놓은 드림팀 같은 것이죠.
예를 들어,arr = [3, 5, 2, 6] 를 봐봅시다.
이 배열의 실제 LIS는 [3, 5, 6]이고, 길이는 3입니다.
이제 이 배열로 '카드 놓기' 게임을 해보면 왜 tails가 가짜 수열인지 명확해집니다.
1. 카드 3을 뽑음
- tails: [3]
2. 카드 5를 뽑음
- 5는 3보다 크므로 새 더미를 만듭니다.
- tails: [3, 5]
3. 카드 2를 뽑음
- 2는 5보다 작습니다. tails에서 2보다 크거나 같은 가장 왼쪽 카드(3)를 찾아 바꿔치기합니다.
- tails: [2, 5]
- 🚨 바로 이 순간이 핵심입니다!
- tails 배열은 [2, 5]가 되었습니다. 하지만 원래 배열 [3, 5, 2, 6]에서 2는 5 뒤에 나옵니다.
- 즉, [2, 5]는 원본 배열의 순서를 무시한 존재할 수 없는 '유령' 수열입니다. 이 알고리즘은 오직 "길이 2짜리 수열의 마지막은 5보다 2가 더 좋아!"라며 잠재력만 보고 3을 2로 바꿔버린 것입니다.
4. 카드 6을 뽑음
- 6은 5보다 크므로 새 더미를 만듭니다.
- tails: [2, 5, 6]
결과 비교
- 최종 tails 배열: [2, 5, 6] (길이 3)
- 실제 LIS: [3, 5, 6] (길이 3)
보시다시피 길이는 3으로 정확하게 일치하지만, tails 배열 자체는 실제 정답과 다릅니다. 이처럼 tails 배열은 길이를 구하는 과정에서 최적의 선택을 위해 원본의 순서를 파괴할 수 있기 때문에, 그 내용물은 믿을 수 없고 오직 배열의 길이만이 진짜 정보인 것입니다.
이 알고리즘은 오직 'LIS의 길이'를 $O(N \log N)$으로 정확하게 찾는 데 목적이 있다는 점을 꼭 기억해야 합니다.
Part 3. 두 번째 미션: 최장 공통 부분 수열 (LCS)
첫 번째 미션이었던 LIS가 하나의 수열 안에서 숨은 '질서'를 찾는 과정이었다면,
두 번째 미션인 최장 공통 부분 수열(Longest Common Subsequence, LCS)은
두 개의 수열 사이에서 '공통의 역사'를 찾는 과정입니다.
이 문제를 통해 우리는 DP의 차원을 한 단계 확장하는 경험을 해봅시다.
🎯 3-1. 문제 정의: LCS란 무엇인가?
최장 공통 부분 수열이란, 주어진 두 개의 수열에 공통으로 존재하는 부분 수열 중에서 가장 긴 것을 말합니다.
여기서 핵심은 Part 1에서 배운 '부분 수열'의 개념이 그대로 적용된다는 점입니다. 즉, 두 수열에서 몇 개의 문자를 건너뛰더라도, 순서만 맞다면 '공통 부분 수열'로 인정됩니다.
- 예를 들어, 두 개의 문자열
str1 = "ACAYKP"와str2 = "CAPCAK"가 있다고 해봅시다. - 이 둘의 '공통 부분 수열'은 여러 가지가 있습니다.
"ACK""ACA""ACAK"
- 이 중에서 가장 길이가 긴 것은
"ACAK"이므로, 두 문자열의 LCS는"ACAK"이고 그 길이는 4가 됩니다.
LCS 문제는 단순히 문자열 비교를 넘어, DNA 염기서열 분석이나 Git의 diff 알고리즘처럼 두 데이터 시퀀스 간의 유사도를 측정하는 데 매우 중요하게 사용되는 근본적인 알고리즘입니다.
💡 3-2. 2차원 DP의 등장: 왜 테이블이 필요한가?
LIS 문제에서는 하나의 수열만 다루었기 때문에, i번째 원소까지의 상태를 저장하는 1차원 DP 배열(DP[i])만으로 충분했습니다.
하지만 LCS는 다릅니다. 우리는 두 개의 수열을 동시에 비교해야 합니다. str1에서는 i번째까지, str2에서는 j번째까지 진행된 상태를 함께 고려해야만 '공통'된 부분 수열의 길이를 계산할 수 있습니다.
이것이 바로 2차원 DP 테이블이 필요한 이유입니다.
str1의 진행 상황을 행(row)으로 나타냅니다.str2의 진행 상황을 열(column)으로 나타냅니다.
이렇게 만들어진 2차원 테이블의 각 칸 DP[i][j]는 'str1의 i번째 문자까지와 str2의 j번째 문자까지, 이 두 부분 문자열 사이의 LCS 길이' 라는 매우 중요한 상태 정보를 담게 됩니다.
즉, 하나의 문제가 아닌 두 문제의 진행 상황을 동시에 기록하기 위해 차원이 하나 늘어난 것입니다. 이 2차원 테이블을 어떻게 채워나갈지가 바로 LCS 알고리즘의 핵심입니다.
📝 3-3. 핵심 로직 설계 ($O(N*M)$)
1. 상태 정의 (복습)
다시 한번 상기해 봅시다. DP[i][j]의 의미는 다음과 같습니다.
DP[i][j] = str1의 첫 i개 문자와 str2의 첫 j개 문자를 사용했을 때의 LCS 길이
(※ 구현 편의를 위해 DP 테이블은(str1.length + 1) x (str2.length + 1)크기로 만들고,i와j는 1부터 시작하는 인덱스라고 생각하겠습니다.)
이 정의는 DP 테이블의 각 칸이 '미니 문제'의 정답을 담고 있다는 의미입니다.
str1 = "ABC"와 str2 = "AXC"라는 아주 간단한 두 문자열이 있다고 해봅시다.
이때 DP[2][3] 이라는 칸은 정확히 무엇을 의미할까요?
- i = 2 👉 str1의 첫 2개 문자 👉 "AB"
- j = 3 👉 str2의 첫 3개 문자 👉 "AXC"
즉, DP[2][3]이라는 칸은 "AB"와 "AXC"의 LCS 길이가 얼마인가? 라는 '미니 문제'의 정답을 저장하는 공간입니다. "AB"와 "AXC"의 가장 긴 공통 부분 수열은 "A" 하나뿐이므로, 그 길이는 1입니다. 따라서 DP[2][3] 칸에는 숫자 1이 저장됩니다.
이 개념을 표로 정리하면 다음과 같습니다.
| DP 칸 | str1 범위 | str2 범위 | 의미 (풀어야 할 '미니 문제') | 정답 (저장될 값) |
| DP[1][1] | "A" | "A" | "A"와 "A"의 LCS 길이는? | 1 |
| DP[2][1] | "AB" | "A" | "AB"와 "A"의 LCS 길이는? | 1 |
| DP[2][3] | "AB" | "AXC" | "AB"와 "AXC"의 LCS 길이는? | 1 |
| DP[3][3] | "ABC" | "AXC" | "ABC"와 "AXC"의 LCS 길이는? | 2 |
이런 식으로 각 칸이 부분 문제의 정답을 차곡차곡 저장해두기 때문에, 우리는 DP[3][3] 같은 더 큰 문제를 풀 때 이전에 풀어둔 DP[2][2] 같은 작은 문제의 정답을 바로바로 꺼내 쓸 수 있는 것입니다. 이것이 DP의 핵심 원리입니다.
2. DP 테이블을 채우는 기본 원리: "딱 세 칸만 보자"
LCS 문제를 푸는 가장 멋진 아이디어는, 복잡한 전체 문제를 '바로 이웃한 세 칸의 관계'라는 아주 작은 문제로 쪼개는 것입니다.
어떤 칸 DP[i][j]의 값을 계산하고 싶을 때, 우리는 딱 세 개의 이웃 칸만 쳐다보면 됩니다.
- ↖ 왼쪽 위 (DP[i-1][j-1])
- ↑ 바로 위 (DP[i-1][j])
- ← 바로 왼쪽 (DP[i][j-1])
DP[i][j]는 이 세 이웃이 가진 값들을 조합해서 결정됩니다. 즉, 우리는 테이블을 채워나가면서 매번 딱 한 가지 질문만 던지면 됩니다.
"지금 비교하는 두 문자(str1[i-1]와 str2[j-1])가 서로 같은가?"
예를 들어 str1 = "ACE"와 str2 = "ABE"가 있고, 우리는 DP[2][2]의 값을 채우려 한다고 상상해 봅시다. 이 칸은 "AC"와 "AB"의 LCS 길이를 의미합니다.
우리의 목표는 물음표(?)가 있는 칸의 값을 알아내는 것입니다.
| (empty)🅰️ | (str2[0])🅱️ | (str2[1]) | |
| (empty) | 0 | 0 | 0 |
| 🅰️ (str1[0]) | 0 | 1 | 1 |
| 🅲 (str1[1]) | 0 | 1 | ❓ |
1. 목표 🎯
- 물음표(?) 칸은 DP[2][2]를 의미합니다.
- 이 값은 str1의 "AC"와 str2의 "AB" 사이의 LCS 길이를 나타냅니다.
2. 질문 ❓
- DP[2][2]에 해당하는 문자는 str1의 'C'와 str2의 'B'입니다.
- 질문: 'C'와 'B'는 같은 문자인가요?
- 답: 아니요. 다릅니다. ❌
3. 규칙 적용 ⚙️
- 문자가 다르기 때문에, 우리는 "아쉽지만, 둘 중 더 좋은 쪽을 계승"하는 규칙을 적용합니다.
- 즉, ? 칸의 바로 위(↑)의 값과 바로 왼쪽(←)의 값 중 더 큰 값을 선택합니다.
4. 결론 ✅
- 바로 위(↑)의 값: 1
- 바로 왼쪽(←)의 값: 1
- max(1, 1) 은 1 입니다.
- 따라서 ? 칸에 들어갈 값은 1이 됩니다.
| (empty)🅰️ | (str2[0])🅱️ | (str2[1]) | |
| (empty) | 0 | 0 | 0 |
| 🅰️ (str1[0]) | 0 | 1 | 1 |
| 🅲 (str1[1]) | 0 | 1 | 1 |
이 값을 계산하기 위해, 우리는 이미 계산된 세 이웃의 값만 알면 됩니다.
- DP[1][2] (↑) = 1 ( "A"와 "AB"의 LCS는 "A" )
- DP[2][1] (←) = 1 ( "AC"와 "A"의 LCS는 "A" )
- DP[1][1] (↖) = 1 ( "A"와 "A"의 LCS는 "A" )
이제 우리의 유일한 질문을 던져봅니다.
"지금 비교하는 두 문자, str1의 두 번째 문자인 'C'와 str2의 두 번째 문자인 'B'는 서로 같은가?"
이 질문에 대한 답이 "YES"냐 "NO"냐에 따라 행동 방침이 명확하게 갈리는 것이죠.
- YES (문자가 같다면) 👉 보너스 점수(+1) 획득!
- 문자가 같다는 건 공통점을 찾았다는 뜻이니까요. 이건 마치 게임에서 보너스 아이템을 얻은 것과 같습니다. 우리는 왼쪽 위 대각선(↖)에 있던 값에 +1을 해서 현재 칸을 채웁니다. 왜냐하면, 이전 단계의 공통된 역사(DP[i-1][j-1])에 새로운 공통의 역사 한 페이지가 추가된 것이니까요.
- NO (문자가 다르다면) 👉 아쉽지만, 둘 중 더 좋은 쪽을 계승.
- 문자가 다르니 공통점을 찾지 못했고, 길이를 늘릴 수 없습니다. 이럴 땐 어쩔 수 없이 이전까지 만들어진 최선의 결과를 그대로 이어받아야 합니다. 선택지는 두 개입니다. 바로 위(↑)의 값과 바로 왼쪽(←)의 값. 둘 중 더 큰 값을 가져와 현재 칸을 채웁니다. "어차피 이번엔 글렀으니, 둘 중 더 길었던 쪽의 역사를 따라가자"는 의미입니다.
이 간단한 두 가지 규칙만 가지고 테이블의 첫 칸부터 마지막 칸까지 쭉 채워나가기만 하면, 어느새 LCS의 정답이 완성되어 있는 것입니다.
(이제 아래의 점화식을 보면, 위에서 설명한 두 가지 규칙을 수학적으로 표현한 것뿐이라는 걸 알 수 있습니다.)
3. 점화식 도출 (가장 중요!)
위에서 살펴보았듯이 DP[i][j]를 채우는 규칙은 딱 두 가지 상황으로 나뉩니다.
현재 비교하는 두 문자(str1[i-1]와 str2[j-1])가 같을 때와 다를 때입니다.
Case 1: 두 문자가 같을 때 (str1[i-1] == str2[j-1])
이건 가장 기분 좋은 상황입니다. 공통 문자를 하나 더 찾았으니까요!
- 새롭게 찾은 이 공통 문자는, 바로 직전 단계의 LCS에 그대로 이어 붙일 수 있습니다.
- '직전 단계'란,
str1과str2에서 현재 문자를 제외한 상태, 즉DP[i-1][j-1]에 저장된 LCS를 의미합니다. - 따라서, 우리는 고민 없이
DP[i-1][j-1]의 길이에 1을 더하면 됩니다.
DP[i][j] = DP[i-1][j-1] + 1
Case 2: 두 문자가 다를 때 (str1[i-1] != str2[j-1])
공통 문자를 찾지 못했으니, 길이를 1 늘리는 것은 불가능합니다.
- 이 경우,
DP[i][j]의 값은 이전 단계에서 이미 계산된 최선의 결과를 그대로 물려받아야 합니다. - 여기엔 두 가지 선택지가 있습니다.
str1의i번째 문자를 포기하고, 이전 상태(DP[i-1][j])의 값을 가져온다.str2의j번째 문자를 포기하고, 이전 상태(DP[i][j-1])의 값을 가져온다.
- 우리는 '최장' 공통 부분 수열을 찾는 것이므로, 두 선택지 중 더 큰 값을 선택하는 것이 당연히 이득입니다.
DP[i][j] = max(DP[i-1][j], DP[i][j-1])
4. 시뮬레이션: 2차원 DP 테이블 채우기
이제 str1 = "ACAYKP" 와 str2 = "CAPCAK" 예시로 테이블을 직접 채워봅시다.
| C | A | P | C | A | K | ||
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| A | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| C | 0 | 1 | 1 | 1 | 2 | 2 | 2 |
| A | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
| Y | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
| K | 0 | 1 | 2 | 2 | 2 | 3 | 4 |
| P | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
DP[1][2](AvsA): 문자가 같으므로, 왼쪽 위 대각선DP[0][1](값:0)에 1을 더해 1이 됩니다.DP[2][1](CvsC): 문자가 같으므로,DP[1][0](값:0)에 1을 더해 1이 됩니다.DP[2][4](CvsC): 문자가 같으므로,DP[1][3](값:1)에 1을 더해 2가 됩니다.DP[3][2](AvsA): 문자가 같으므로,DP[2][1](값:1)에 1을 더해 2가 됩니다.DP[6][3](PvsP): 문자가 같으므로,DP[5][2](값:2)에 1을 더해 3이 됩니다.DP[5][6](KvsK): 문자가 같으므로,DP[4][5](값:3)에 1을 더해 4가 됩니다.
5. 정답 찾기
모든 테이블을 채우고 나면, 최종 정답은 가장 마지막 칸인 맨 오른쪽 아래에 위치하게 됩니다.
정답 =
DP[6][6]= 4
Part 4. 최종 정리: 우리는 무엇을 얻었나?
LIS와 LCS라는 두 가지 대표적인 DP 문제를 통해 우리는 동적 계획법의 핵심 원리를 깊이 있게 탐색했습니다.
이 파트에서는 우리가 배운 것을 한 번 더 다지고,
실제 코딩 테스트나 기술 면접에서 마주칠 수 있는 심화 질문까지 대비해 봅니다.
💻 4-1. 복잡도 분석 및 비교
알고리즘의 효율성을 판단하는 척도인 시간 및 공간 복잡도를 정리해 봅시다.
- LIS (최장 증가 부분 수열)
- 기본 DP: 시간 복잡도 $O(N^2)$, 공간 복잡도 $O(N)$
- 이진 탐색 최적화: 시간 복잡도 $O(N \log N)$, 공간 복잡도 $O(N)$
- LCS (최장 공통 부분 수열)
- 2차원 DP: 시간 복잡도 $O(NM)$, 공간 복잡도 $O(NM)$
- (N과 M은 두 수열의 길이를 의미합니다.)
- 2차원 DP: 시간 복잡도 $O(NM)$, 공간 복잡도 $O(NM)$
💡 4-2. Key Takeaway & 면접 팁
핵심: "DP의 시작은 상태 정의, 끝도 상태 정의다."
LIS와 LCS를 통해 우리가 얻은 가장 중요한 교훈입니다. DP[i]와 DP[i][j]가 무엇을 의미하는지 명확하게 정의하는 순간, 점화식은 자연스럽게 따라오게 됩니다.
DP 문제를 마주쳤을 때 코드를 먼저 생각하지 말고, "내가 각 단계에서 어떤 값을 저장해야 다음 문제를 풀 수 있을까?"라는 '상태 정의'부터 고민하는 습관을 들이는 것이 중요합니다.
함정 피하기: LIS의 DP[i] 정의를 기억하라
면접관이 "LIS에서 DP 배열은 무엇을 의미하나요?"라고 물었을 때, 절대 "i번째 원소까지의 LIS 길이" 라고 답해서는 안 됩니다.
이는 arr[i]를 포함하지 않는 LIS일 수 있어, 다음 단계 계산에 사용할 수 없는 '죽은 정보'가 되기 때문입니다.
"arr[i]를 반드시 마지막 원소로 포함하는 LIS의 길이" 라고 정확히 답해야만 DP의 원리를 제대로 이해하고 있음을 보여줄 수 있습니다.
면접관의 추가 질문: "길이뿐만 아니라, 실제 LIS / LCS 수열 자체를 출력해보세요."
이것은 거의 100% 확률로 나오는 후속 질문입니다. 길이를 구하는 데 사용된 DP 테이블을 역추적(Backtracking)하면 실제 수열을 찾을 수 있습니다.
- LCS 역추적:
- DP 테이블의 맨 오른쪽 아래(
DP[N][M])에서 시작합니다. str1[i-1] == str2[j-1]이라면, 해당 문자는 LCS에 포함됩니다. 문자를 기록하고, 왼쪽 위 대각선(DP[i-1][j-1])으로 이동합니다.- 두 문자가 다르다면, 위쪽(
DP[i-1][j])과 왼쪽(DP[i][j-1]) 중 더 큰 값을 가진 쪽으로 이동합니다. - 테이블의 시작(0행 또는 0열)에 도달할 때까지 반복합니다.
- 기록된 문자들을 역순으로 출력하면 LCS가 됩니다.
- DP 테이블의 맨 오른쪽 아래(
- LIS ($O(N^2)$) 역추적:
DP배열에서 최댓값을 가진 인덱스k를 찾습니다.arr[k]가 LIS의 마지막 원소입니다.k의 왼쪽(인덱스0부터k-1까지)을 탐색하며arr[j] < arr[k]이고DP[j] == DP[k] - 1인j를 찾습니다.arr[j]가 LIS의 바로 이전 원소입니다.j를 새로운k로 삼아,DP값이 1이 될 때까지 이 과정을 반복합니다.
활용 사례: 이건 어디에 쓰이나요?
- LCS: 두 파일의 변경 사항을 비교하는
diff유틸리티의 핵심 원리이며, 생물정보학에서 두 DNA 염기서열의 유사도를 분석하는 데 널리 사용됩니다. - LIS: 직접적인 사용 사례는 드물지만, 다른 동적 계획법 문제(예: 특정 조건을 만족하며 가장 길게 쌓을 수 있는 블록의 높이 구하기 등)를 해결하는 기본 모델로 자주 응용됩니다.
'알고리즘' 카테고리의 다른 글
| O(n²) 너머 ②: 제자리 정렬의 해답, 힙 정렬(Heap Sort) (3) | 2025.07.24 |
|---|---|
| O(n²)의 벽을 넘어서기 위한 관문, 병합 정렬 (2) | 2025.07.11 |
| "느린 정렬"은 정말 항상 느릴까? (feat. 버블, 삽입 정렬의 재발견) (1) | 2025.06.28 |
| 같은 시간 복잡도인데 왜 DFS가 BFS 보다 느릴까? - 스택, 힙, 캐시로 파헤치는 알고리즘의 실제 성능 (BOJ 21736) (2) | 2025.06.07 |
| 백트래킹 개념, 유망 함수와 가지치기, 예시 문제로 이해하기 (0) | 2025.05.25 |
