백준 - [BOJ 12015] 가장 긴 증가하는 부분 수열 2

백준 온라인 져지(BOJ)에서 제공 되는 12015번 문제는 선행 문제가 있다.

가장 긴 증가하는 부분 수열

나는 위 문제를 먼저 풀어보고 오는 것을 추천한다.

해당 문제는 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)로 유명한 문제이다.

---

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

---

풀이

위와 같은 정보로 문제를 해결해야한다.

 

우리는, 문제의 예시 때문에 {10, 20, 10, 30, 20, 50}이라는 수열의 최장 길이를 알 수 있다.

해당 문제는 1 <= N <= 100만이므로 O(1) ~ O(NlogN)에 해결해야하는 문제임을 예측할 수 있다.

 

Naive 하게 접근하기

 

1. 직관적으로 보기

1. 10, 20이 만들어짐

2. 10은 붙여봤자 짧으니까 붙이지 않음.

3. 10, 20, 30이 만들어짐

4. 20은 붙여봤자 짧으니까 붙이지 않음

5. 10, 20, 30, 50이 만들어짐

 

정말 보이는대로만 접근하면 위와같은 과정이 발생한다.

 

과연, 정답일까?

 

우리는 주어진 수열에서 {10, 20, 10, 30, 20, 50} 색칠된 값 때문에 원소 사이에 어떤 값이 있을지 모른다.

{10, 20, 11, 12, 15, 30, 20, 50} 해당 수열에서 위 풀이가 성립되지 않음을 알 수 있다.

 

그럼, 어떻게 접근해야할까?

 

순서대로 입장을 생각해보면 된다. 이 말이 무슨 뜻이냐면,

{10, 20, 11, 12, 15, 30, 20, 50} 다음과 같은 수열에서 

1. 0번 째 index : 10, 맨 앞이므로 수열의 최장 길이는 1을 갖게 된다.
2. 1번 째 index : 20, 내 앞에 나보다 작은 원소를 찾는다.
   • 0번 째 index인 10, 10의 길이 = 1
   • 1번 째 index인 20의 길이는 나보다 작은 원소에 이어지는 수열이므로 10의 길이 + 1로 업데이트한다.
3. 2번 째 index : 11, 내 앞에 나보다 작은 원소를 찾는다.
   • 1번 째 index인 20, 나보다 큼
   • 0번 째 index인 10, 나보다 작음
   • 0번 째 index까지의 길이 + 1로 내 길이를 업데이트한다.

해당 문제는 다이나믹 프로그래밍임을 알 수 있다.이전 값의 기록을 이용해 현재 내 기록을 업데이트 하는 메모제이션 기법이 들어간다.

 

시간 복잡도는?

 

풀이를 생각했다면, BOJ와 같은 온라인 져지에서는 그냥 냅다 제출해봐도 무관하다.

하지만, 코딩테스트나 알고리즘 대회를 생각한다면 정답이 옳은지 검증을 해봐야한다.

우리는 위 풀이가 정답이 나올 수 있다는 것은 알게 됐다.

 

그럼 시간 안에 문제가 해결되는지 시간 복잡도를 한 번 계산해봐야 하는데,

현재 인덱스일 때, 이전 인덱스 중에서 나보다 작은 값을 찾는 문제이다.

만약에 수열이 내림차순 {5, 4, 3, 2, 1}로 되어 있다면?

 

정답은 1이지만 최악의 경우, O(N^2)을 생각해 볼 수 있다.

N개에 대해서 N-1번까지 탐색을 해야하므로 N * (N-1)의 시간 복잡도가 발생한다.

 

문제에서 우리가 입력받는 N의 데이터는 100만개이다. 

100만 * (100만 - 1), 주어진 제한 시간은 1초인데 터무니 없다 ㅋㅋㅋ

 

좀 더 효율적인 접근을 하기

 

좀 더, 효율적인 접근을 한다는게 말만 쉽지. 그것을 적용하는 것이 무척 힘들다는 것은 안다.

Dynamic Programming 적인 접근이 성공했다면 좀 더 효율적인 접근이 가능하다.

{10, 20, 11, 30} 이 있다고 할 때, 우리는 {10, 20, 30}을 선택할 수 있지만 {10, 11, 30}도 선택할 수 있다.

이 내용을 보고 {10, 20, 11, 12, 15, 30, 20, 50}  이 수열을 본다면 어떻게 해결할 지 떠올려야 한다.

 

현재 원소에 대해서 이전 원소까지 같은 길이의 수열 집합이 여러개가 있다면?

 

{10, 20, 11, 12, 30} 을 보자
길이가 1일 때, {10}

길이가 2일 때, {10, 20}, {10, 11}

길이가 3일 때, {10, 20, 30}, {10, 11, 12}, {10, 11, 30}, {11, 12, 30}

...

이런 식으로 나열된다.

 

어차피 같은 길이라면 더 작은수를 선택하는 것이 낫지 않을까?

 

우리는 이런 생각에서 이 문제를 접근해야한다.

그럼 또 다른 반례를 들어보자.

{10, 20, 11, 12, 15, 30, 13, 20, 25, 50} 일 때, 
우리가 원하는 결과 대로면 6번째 인덱스의 값인 '13'에 대해서 처리 할 때,
5번째 인덱스까지 처리한 결과는 {10, 11, 12, 15, 30}를 만족하게 된다는 것이다.

 

이제 '13'보다 작은 녀석을 찾아서 뒤에 붙여주면 된다.

그럼 {10, 11, 12, 13}을 구할 수 있다는 것을 알 수 있다. 

이것의 길이는 4이고 5번째 인덱스까지 처리한 결과에서 길이가 4인 수열은 {10, 11, 12, 15}이다.

 

{10, 11, 12, 13}이 더 작은 값이므로 선택하게된다면 결과는 {10, 11, 12, 13, 30}이 되는 것이다.

 

어 ? 근데 13은 30보다 뒤에 있는데? 

이런 생각이 든다면 정상이다.

우리는 최장 길이를 구하는 것이기 때문에 지금 4번째에 13인지 15인지 알 필요가 없다.

그냥 30보다 작은수로 이루어진 LIS의 길이가 4라는 것은 알고 있다.

우리는 길이만 알면 되니까 30 앞에 13이 있던, 15가 있던 30보다 작은 수니까 만족한다는 것이다.

 

이게 또 헷갈릴 수 있으니 {10, 20, 11, 12, 15, 30, 13, 20, 25, 50} 이 수열에 대해 이번에는 20을 선택해보자.

7번 째 인덱스의 값인 '20'에 대해서 6번째 인덱스 값인 30까지의 결과를 알아야 한다.

우리는 위의 과정에서 {10, 11, 12, 13, 30}라는 결과를 얻었고 이제 20을 넣어보자.

 

'20'보다 작은 수로 구성된 수열은 {10, 11, 12, 13}이고 이어 붙이게 된다면 {10, 11, 12, 13, 20}이 된다.

이것의 길이는 5이고 이전 결과에서 길이가 5인 수열은 {10, 11, 12, 13, 30} 이다.

 

우리는 더 작은 값을 선택하기로 했으니 7번째 인덱스까지 LIS 길이는 5이다.

 

이제 '25'를 선택해보자.
{10, 11, 12, 13, 20} 에서 '25'보다 작은 수로 이루어진 수열을 찾는다고하면 그 자체이다.

뒤에 25만 추가해주면 될 뿐이게 됨. -> {10, 11, 12, 13, 20, 25}

 

그런데 만약, 이전 과정에서 {10, 11, 12, 13, 20}과 {10, 11, 12, 13, 30}의 길이가 같다는 이유로 
{10, 11, 12, 13, 30}을 선택했다면? 

우리의 논리대로라면 {10, 11, 12, 13, 25}라는 결과를 얻게 될 것이다.

 

우리는 위 과정에서 모든 경우의 수를 다 구해봤다.

그럼, 이제 직접 문제를 풀어봐야 하는데 어떻게 풀 수 있을까?

lower_bound

 

우리는 lower_bound라는 알고리즘을 사용해서 해당 문제를 해결할 수 있다.

생각의 전환을 가져보자.

 

작은 수까지 선택한다는 것은 작은수가 아닌 수를 선택하면? 그 이전까지는 무조건 작은 수이다.

논리식으로 표현하면 key < x가 작은 수까지 선택, 이 반대는 key >= x

 

즉, 현재 원소 값 이상의 값을 찾으면 되는 것이다.

log N에 빠르게 찾아주는 lower_bound를 사용!

 

lower_bound만 이용

/*
	authored by jihwankim
	https://dev-dot.tistory.com
	acm 12015
*/

#include <bits/stdc++.h>

using namespace std;
 

vector<int> input(int &n) {
	cin >> n;
	vector<int> arr(n);
	for(int i = 0; i < n; i++) {
		cin >> arr[i];	
	}
	
	return arr;
}

int solve(vector<int> &arr) {
	vector<int> lis;
	
	for(int i = 0; i < arr.size(); i++) {
		int key = arr[i];
		int v = lower_bound(lis.begin(), lis.end(), key) - lis.begin();
		 
		if(v == lis.size()) {
			lis.push_back(key);
		} else {		
			lis[v] = key;	
		}
		
	}

	return lis.size();
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	
	int n;
	vector<int> arr = input(n);
	cout << solve(arr);
	
	return 0;
}

 

STL set을 이용

 

난 문제를 풀 때는 set을 사용해서 풀긴했다.

원리는 같으나 어떤 차이점들이 있는지 알아보는 것도 좋을듯!

그리고 어떤 방식을 사용하는게 더 좋은지도 생각해보면 좋을듯!

/*
	authored by jihwankim
	https://dev-dot.tistory.com
	acm 12015
*/

#include <bits/stdc++.h>

using namespace std;
 

vector<int> input(int &n) {
	cin >> n;
	vector<int> arr(n);
	
	for(int i = 0; i < n; i++) {
		cin >> arr[i];	
	}
	
	return arr;
}

int solve(vector<int> &arr) {
	set<int> s;
	
	for (int &now: arr) {
		auto it = s.lower_bound(now);
		if (it != s.end()) s.erase(it); 
		s.insert(now);
	}
	
	return s.size();
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	
	int n;
	vector<int> arr = input(n);
	cout << solve(arr);
	
	return 0;
}

 

참고할 포스트

 

아직 미작성

 

문제

 

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

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