💻코딩테스트/백준

[백준/C++] 12015번 : 가장 긴 증가하는 부분 수열 2 (LIS 수열 문제)

공대 컴린이 2023. 8. 10. 15:18
728x90

가장 긴 증가하는 부분 수열 2 

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1 

6
10 20 10 30 20 50

예제 출력 1 

4

LIS (최장 증가 부분 수열) 유형에서 시간제한이 있는 문제를 새롭게 풀어보았다.

❌ 이전 LIS 문제를 풀 땐, i = 0 -> i = 수열.length 와, j = 0 -> j < i 의 2중 for문을 이용해서 시간복잡도 O(N^2)의 풀이방법을 사용했다.

 

그러나 이 문제는, 시간제한이 걸려있고 수열의 크기가 최대 백만으로 큰 수이기 때문에 O(N^2)의 풀이방법으로 해결할 수 없다.

정답을 찾기까지 시간이 꽤나 오래걸리고, 정답지를 보고도 이해하는데 시간이 좀 걸렸다.

 

2중 for문을 없애고 최장 증가 부분 수열을 구하기 위해선 "이분탐색"을 이용해야 한다.

따라서, 이분탐색을 직접 구현한 버전과, c++의 lower_bound 함수를 사용한 버전 두 가지로 문제를 각각 풀이해보았다.

📌 이분탐색 구현 버전

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> arr;

int BinarySearch(int start, int end, int num)
{
	while(start < end)
	{
		int mid = (start + end) / 2;
		if (num > arr[mid])
			start = mid + 1;
		else
			end = mid;
	}
	return start;
}

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

	int N;
	cin >> N;
	vector<int> A(N);
	for (int& a : A)
		cin >> a;

	arr.push_back(A[0]);
	int cnt = 1;
	for(int i = 1; i < N; i++)
	{
		if(A[i] > arr.back())
		{
			arr.push_back(A[i]);
			cnt++;
		}
		else
		{
			int idx = BinarySearch(0, cnt, A[i]);
			arr[idx] = A[i];
		}
	}
	cout << cnt;

	return 0;
}

 

LIS 즉, 최장 증가 부분 수열은 숫자가 오름차순으로 증가될 수 밖에 없기 때문에 배열 A의 원소를 수열 배열 arr에 추가할 때 이전 값의 크기와 비교하여 추가했다.

 

1. 수열을 만들기 전 기본적으로 배열 0인덱스를 첫번째 수열의 원소로 집어넣는다.

2. 이후, 배열 1인덱스 값(A[i])이 수열의 맨 뒤 숫자보다 크다면, 1인덱스 값을 그대로 수열의 맨 뒤에 추가한다.

3. 만약, 배열의 1인덱스 값이 수열의 맨 뒤 숫자보다 작다면, 이분탐색을 통해 1인덱스 값이 들어가야 하는 위치를 구하고, 해당 위치의 수열 원소를 변경해준다.

 

좀 더 쉽게 설명하자면 다음과 같다.

주어진 배열 A: 10 20 10 30 20 50
최장 증가 부분 수열 arr : 10 (A의 첫번째 인덱스 값)
수열 크기 cnt : 1 (A의 첫번째 인덱스가 들어가 있으므로 1부터 시작)

 

위와 같은 조건이 주어져 있을 때, 순서대로 수열을 만들어보자.

 

A[1] = 20 값이 arr.back() 인 10보다 크기 때문에 arr 수열의 맨 뒤에 20을 추가한다.

arr : 10 20

 

A[2] = 10 값이 arr.back()인 20보다 작기 때문에 이분탐색(BinarySearch 함수)를 통해 10이 들어갈 위치를 찾는다.

함수 수행 결과 0 인덱스가 나오므로 arr[0] = A[2] = 10 의 값이 들어간다.

arr: 10 20 (결국 동일하게 유지됨)

 

A[3] = 30 값이 arr.back() 인 20 보다 크기 때문에 맨 뒤에 추가한다.

arr : 10 20 30

 

A[4] = 20 값은 이분탐색 결과 1 인덱스가 나오므로 arr[1] = A[4] = 20 이 된다.

arr: 10 20 30

 

A[5] = 50 값은 arr.back() 인 30 보다 크기 때문에 맨 뒤에 추가한다.

arr: 10 20 30 50

 

모든 A 배열의 끝까지 검사를 완료했기 때문에 수열 arr의 길이인 cnt 정수를 출력하면 답은 4가 나온다.

 위 예제는 숫자가 예쁘게 10 20 30 단위로 나왔기 때문에 이분탐색 결과가 쏙쏙 앞으로 들어갔다.

 

그러나 10 20 50인 배열에서 40이 들어갈 경우, 10 20 40 으로 배열이 바뀌거나 하는 테스트 케이스도 존재한다는 것을 알아두자.

 

⭕ 이렇게 이분탐색을 이용해서 풀이하면 이분탐색의 시간복잡도 O(log N)에, for문을 1부터 N 까지 돌리므로 O(N log N)의 시간이 걸리게 된다.

기존에 풀었던 2중 for문의 시간복잡도 O(N^2)에 비해 훨씬 빨라진 것을 알 수 있다.

📌 lower_bound 함수 사용 버전

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

using namespace std;

vector<int> arr;

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

	int N;
	cin >> N;
	vector<int> A(N);
	for (int& a : A)
		cin >> a;

	arr.push_back(A[0]);
	for (int i = 1; i < N; i++)
	{
		if (A[i] > arr.back())
			arr.push_back(A[i]);
		else
			*lower_bound(arr.begin(), arr.end(), A[i]) = A[i];
	}
	cout << arr.size();

	return 0;
}

 

이진탐색을 구현한 lower_bound 함수를 사용하면 직접 이진탐색 함수 BinarySearch를 구현하지 않고도 문제를 간단히 해결할 수 있다.

lower_bound는 부분 탐색으로 찾은 수의 Iterator를 반환하기 때문에 포인터를 통해 직접 접근 후 바로 A[i] 값으로 초기화해줄 수 있다!

https://www.acmicpc.net/problem/12015

 

12015번: 가장 긴 증가하는 부분 수열 2

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

www.acmicpc.net

 

728x90