[Baekjoon]12015.가장 긴 증가하는 부분수열2

Baekjoon

#12015. 가장 긴 증가하는 부분 수열2

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

---

 

11053과 같은 문제이지만 N제한이 더 커서 O(N^2)의 방법으로 풀면 시간 초과가 난다. 따라서 O(NlogN) 방법으로 풀어야 한다. 이진 탐색을 활용한 lower bound 알고리즘을 사용했다.  

 

Lower Bound : 배열에서 찾고자 하는 값 k가 있을때 k보다 크거나 같은 값의 첫번째 인덱스를 리턴.

예) 배열 {1, 1, 3, 5, 6} 에서 k=1 일때 Lower Bound = 2(1보다 크거나 같은 값은 3이므로 3의 인덱스인 2를 리턴)

 

먼저 LIS를 저장할 빈 배열을 하나 생성하여 이를 갱신해나가면서 LIS를 구한다. 

입력된 배열 a = {10, 20, 10, 30, 20, 50} 일때 다음과 같은 과정을 거친다.

부분 수열의 최대 길이는 a배열의 크기와 같으므로 같은 크기로 lis 배열을 생성한다. 

lis의 마지막 원소의 인덱스인 idx를 통해 부분 수열의 길이를 알 수 있다. 인덱스를 0부터 했으므로 답은 idx+1 이다. 

 

LowerBound를 구하는 알고리즘은 이분탐색과 거의 유사한 구조로 다음과 같이 작동한다.

• start가 end와 같거나 end보다 커지면 그 때 end값이 lower bound이므로 반복문을 종료하고 리턴한다.
• 중간값이 원하는 값보다 작으면 start를 중간값으로 설정하여 다시 탐색한다.
• 중간값이 원하는 값보다 크거나 같으면 end를 중간값으로 설정하여 다시 탐색한다.

이를 코드로 구현하면 다음과 같다. 

	private static int getLowerBound(int k) {
		int start = 0;
		int end = idx + 1;
		while (start < end) {
			int m = (start + end) / 2;
			if (lis[m] < k) {
				start = m + 1;
			} else {
				end = m;
			}
		}
		return end;
	}

<전체코드>