최장 증가 수열 (LIS, Longest Increasing Subsequence)

1. LIS (Longest Increasing Subsequence)의 정의

최장 증가 부분 수열(LIS)이란, 주어진 수열에서 몇 개의 숫자를 골라서 만들 수 있는 가장 긴 증가하는 부분 수열을 의미합니다. 단, 부분 수열은 원래 수열에서 순서를 유지해야 합니다. 예를 들어, 수열이 {6, 2, 5, 1, 7, 4, 8, 3}이라면, 이 수열에서 LIS는 {2, 5, 7, 8}로 길이가 4가 됩니다.

LIS 문제는 다양한 알고리즘으로 해결할 수 있지만, 이 중 이진 탐색을 활용하여 O(N log N) 시간 복잡도로 해결하는 방법이 가장 효율적입니다.

2. 문제 해결 코드

아래는 LIS 문제를 해결하는 C++ 코드입니다. 이 코드는 이진 탐색을 통해 효율적으로 LIS의 길이를 구하고 실제 LIS 수열을 추적하고 출력하는 방식입니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 이진 탐색 함수: 정렬된 배열에서 num 이상의 첫 번째 위치를 찾음
// lower_bound 함수를 통해서 사용 가능
int binary_search(vector<int>& lis, int num) {
	int low = 0, high = lis.size();

	while (low < high) {
		int mid = low + (high - low) / 2;
		if (lis[mid] < num) {
			low = mid + 1;
		}
		else {
			high = mid;
		}
	}
	return low;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;

	vector<int> arr(N);  // 입력된 수열
	vector<int> lis;  // LIS를 저장할 벡터
	vector<int> pos(N);  // 각 숫자가 LIS에서 들어간 위치를 기록할 배열
	vector<int> trace(N, -1);  // 이전 위치 추적을 위한 배열

	// 입력 받기
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	// LIS 구하기
	for (int i = 0; i < N; i++) {
		int num = arr[i];
		int pos_in_lis = binary_search(lis, num);  // 이진 탐색을 통해 LIS에서 들어갈 위치를 찾음
		

		if (pos_in_lis == lis.size()) {
			lis.push_back(num);  // 새로운 숫자를 LIS의 끝에 추가
		}
		else {
			lis[pos_in_lis] = num;  // 해당 위치의 값을 갱신
		}

		pos[i] = pos_in_lis;  // 해당 숫자가 들어간 위치 기록

		// trace 배열로 이전 요소 추적
		if (pos_in_lis > 0) {
			trace[i] = pos_in_lis - 1;
		}
	}

	// LIS 복원하기
	vector<int> actual_lis(lis.size());
	int current_pos = lis.size() - 1;
	for (int i = N - 1; i >= 0; i--) {
		if (pos[i] == current_pos) {
			actual_lis[current_pos] = arr[i];
			current_pos--;
		}
	}

	// 결과 출력: LIS 길이와 실제 LIS
	cout << "LIS 길이: " << lis.size() << "\n";
	cout << "LIS: ";
	for (int num : actual_lis) {
		cout << num << " ";
	}
	cout << "\n";

	return 0;
}

 

3. 동작 과정

이 코드는 주어진 수열에서 이진 탐색을 사용하여 LIS의 길이를 구하고, 각 수가 LIS에서 차지하는 위치를 기록하며, 이를 바탕으로 실제 LIS 수열을 복원하는 방식으로 동작합니다.

 

입력:

8
6 2 5 1 7 4 8 3

 

초기 설정

• lis: LIS 배열로, 실제 증가하는 부분 수열을 기록합니다.
• pos: 각 수가 LIS 배열의 어느 위치에 삽입되었는지 기록합니다.
• trace: LIS 수열을 복원하기 위해, 각 수가 어디서 왔는지를 기록합니다.

---

각 단계별 lis, pos, trace 배열 변화

1) 첫 번째 수: 6

• lis에 6을 추가합니다.
• lis 상태: [6]
• pos 상태: [0]
• trace 상태: [-1]

2) 두 번째 수: 2

• lis[0] 위치에 2를 덮어씁니다.
• lis 상태: [2]
• pos 상태: [0, 0]
• trace 상태: [-1, -1]

3) 세 번째 수: 5

• lis에 5를 추가합니다.
• lis 상태: [2, 5]
• pos 상태: [0, 0, 1]
• trace 상태: [-1, -1, 0]

4) 네 번째 수: 1

• lis[0] 위치에 1을 덮어씁니다.
• lis 상태: [1, 5]
• pos 상태: [0, 0, 1, 0]
• trace 상태: [-1, -1, 0, -1]

5) 다섯 번째 수: 7

• lis에 7을 추가합니다.
• lis 상태: [1, 5, 7]
• pos 상태: [0, 0, 1, 0, 2]
• trace 상태: [-1, -1, 0, -1, 1]

6) 여섯 번째 수: 4

• lis[1] 위치에 4를 덮어씁니다.
• lis 상태: [1, 4, 7]
• pos 상태: [0, 0, 1, 0, 2, 1]
• trace 상태: [-1, -1, 0, -1, 1, 0]

7) 일곱 번째 수: 8

• lis에 8을 추가합니다.
• lis 상태: [1, 4, 7, 8]
• pos 상태: [0, 0, 1, 0, 2, 1, 3]
• trace 상태: [-1, -1, 0, -1, 1, 0, 2]

8) 여덟 번째 수: 3

• lis[1] 위치에 3을 덮어씁니다.
• lis 상태: [1, 3, 7, 8]
• pos 상태: [0, 0, 1, 0, 2, 1, 3, 1]
• trace 상태: [-1, -1, 0, -1, 1, 0, 2, 0]

---

LIS 복원 과정

trace 배열을 이용해 실제 LIS 수열을 복원하는 과정입니다.

lis의 마지막 인덱스인 3에서 시작하여, trace 배열을 따라갑니다.

• pos[6] = 3 → arr[6] = 8 → LIS에 8 추가.
• pos[4] = 2 → arr[4] = 7 → LIS에 7 추가.
• pos[2] = 1 → arr[2] = 5 → LIS에 5 추가.
• pos[1] = 0 → arr[1] = 2 → LIS에 2 추가.

최종적으로 구해진 LIS는 {2, 5, 7, 8}입니다.

---

예시 문제: 백준 12015번

백준 12015 - 가장 긴 증가하는 부분 수열 2 문제는 바로 이 LIS 문제를 이진 탐색을 활용해 풀 수 있는 대표적인 문제입니다.

 

문제 요약:

주어진 수열에서 최장 증가 부분 수열(LIS)의 길이를 구하는 문제입니다.

 

입력 예시:

6
10 20 10 30 20 50

 

출력 예시:

4

 

이 문제에서 최장 증가 부분 수열은 {10, 20, 30, 50}이므로, 그 길이는 4가 됩니다.

백준 12015번 문제는 위에서 설명한 이진 탐색을 사용한 방식으로 효율적으로 해결할 수 있습니다.