[백준 12015번 C/C++] 가장 긴 증가하는 부분 수열 2

 

[백준 12015번 C/C++] 가장 긴 증가하는 부분 수열 2

 

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

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

---

 

 

해결 전략

 

최대 증가길이 수열, 이분 탐색

Longest Increasing Subsequence, LIS

 

---

 

 

처음 시도한 코드 - 시간 초과

 

#include <iostream>
#include <vector>
using namespace std;

int n, result;
vector<int> v, LIS;

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

	cin >> n;

	v.resize(n); // 주어진 값을 넣는 배열
	LIS.resize(n); // 각 숫자의 최대부분 증가 길이를 기록하는 배열
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	LIS[0] = 1; //첫 숫자의 LIS는 무조건 1이다. 
	for (int i = 1; i < n; i++)
	{
		int maxValue = 0;

		// (i~1) ~ 0까지 탐색
		for (int j = i - 1; j >= 0; j--)
		{
			// v[i]의 숫자보다 작은 숫자들 중 최대부분증가 길이가 maxValue보다 큰 경우
			// maxValue값이 0으로 시작해서 계속해서 큰 값으로 갱신된다.
			// 결국에 해당 if조건에서 가장 큰 LIS[j]값이 가장 큰 maxValue값이 된다.
			if (v[j] < v[i] && LIS[j] > maxValue)
				maxValue = LIS[j];//maxValue은 (i-1) ~ 0번까지 LIS 중 가장 큰 값이 된다.
		}

		//LIS[i]보다 작은 숫자에서 가질 수 있는 최대부분증가 길이(위에서 설정한 maxValue)에서 +1 해준다.
		LIS[i] = maxValue + 1;

		//i번째 최대부분증가 길이가 가장 큰 값인지 검사하고 가장 큰 값이면 result값을 LIS[i]로 갱신한다.
		if (result < LIS[i]) result = LIS[i];
	}

	cout << result;

	return 0;
}

이중 배열을 사용해서 시간 초과가 나온다.

 

---

 

코드 - 이분탐색을 사용한 코드

 

#include <iostream>
#include <vector>
using namespace std;

int n; // 입력받을 정수의 개수
vector<int> v, LIS; // v는 입력받은 정수들을 저장하는 벡터, LIS는 최장 증가 부분열을 저장하는 벡터

// key값 이상의 크기의 수 중에서 가장 먼저 나온 수의 인덱스를 반환하는 함수
int BinarySearch(vector<int>& v, int key)
{
	int left = 0;
	int right = v.size() - 1;
	int mid;

	// 이진 탐색 시작
	while (left < right) 
	{
		int mid = (left + right) / 2;
		
		if (key > v[mid]) { // 찾고자 하는 값이 중간 값보다 크면 왼쪽 범위를 줄임
			left = mid + 1;
		}
		else { // 찾고자 하는 값이 중간 값보다 작거나 같으면 오른쪽 범위를 줄임
			right = mid;
		}
	}

	return right; // 탐색 완료 후 인덱스 반환
}

void Solve() 
{
	LIS.push_back(v[0]); // LIS에 첫 번째 값을 추가

	for (int i = 1; i < n; i++) 
	{
        if (LIS.back() < v[i]) { // 현재 검사하고 있는 값이 LIS 마지막 원소보다 크면 LIS에 추가함.
            LIS.push_back(v[i]);
        }
        else {
            int idx = BinarySearch(LIS, v[i]); // 그렇지 않으면 해당 원소가 들어갈 위치를 찾아서 그 위치에 원소를 업데이트 함.
            LIS[idx] = v[i];
        }
    }

	cout << cnt; // 최장 증가 부분열의 길이 출력. 즉, 현재까지 만들어진 최대 길이 출력.
}

int main() {
	cin.tie(0); cout.tie(0);
	cin >> n;

	v.resize(n); 

	for (int i = 0; i < n; i++) {
            cin >> v[i]; 
    }

	Solve(); 

	return 0;
}

 

 

 

---

 

짧은 코드

 

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

using namespace std;

int n; // 입력받을 정수의 개수
vector<int> v; // 최장 증가 부분열(LIS)를 저장하는 벡터

int main() {
    cin >> n; // 정수의 개수를 입력받음

    for (int i = 0; i < n; i++) {
        int input;
        cin >> input;
        
        if (v.empty() || v.back() < input) 
            // 벡터가 비어있거나, 마지막 원소보다 현재 원소가 클 경우에는 벡터에 원소를 추가합니다.
            v.push_back(input);
        
        else 
            // 그렇지 않은 경우, lower_bound 함수로 현재 원소보다 크거나 같은 첫 번째 위치(원소)를 찾아서,
            // 그 위치의 값을 현재 원소로 업데이트합니다.
            *lower_bound(v.begin(), v.end(), input) = input;
        
    }
    
    cout << v.size();  // 최종적으로 LIS의 길이 출력
}