boj 3745: 오름세

이 문제에서 주의해야할 점은 아래 2가지이다.

• EOF 처리
• 최장부분증가수열을 빠르게 구하기
  • 완전탐색 => O(2^N)

 

1차 시도 - `동적 계획법`을 사용하여 문제를 풀어보았다. 결과는 50%에서 시간초과.

=> O(N^2), N ≤ 100000이므로 1초안에 통과될 수 없다. 아마 10초정도 걸릴것임...ㅠㅠ

 

dp[n]: n번째 수를 마지막으로 하는 최장증가부분수열로 정의했다.

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNextInt()) {

			int n = in.nextInt();
			int[] stock = new int[n];
			int[] dp = new int[n];
			int max = 0;
			for (int i = 0; i < n; i++) {
				stock[i] = in.nextInt();
			}

			dp[0] = 1;

			for (int i = 1; i < n; i++) {
				dp[i] = 1;
				for (int j = 0; j < i; j++) {
					if (stock[i] > stock[j]) {
						dp[i] = Math.max(dp[j], dp[j] + 1);
					}
				}
				max = Math.max(max, dp[i]);
			}
			System.out.println(max);
		}
	}
}

 

 

2차 시도 - N ≤ 100000이므로 1초안에 통과하려면 시간복잡도가 적어도 NlogN을 되어야 한다. => `이분탐색`을 이용한다

stock 수열을 처음부터 보면서

1. dp의 끝 값과 비교했을 때 마지막 값보다 큰 경우 dp의 마지막에 바로 삽입

2. dp의 끝 값과 비교했을 때 마지막 값보다 작거나 같은 경우 이분탐색을 이용하여 LIS를 유지하기 위한 위치에 수를 삽입하도록 한다.

https://www.acmicpc.net/problem/3745 예제

 

 

 

 

 

 

stock[0]을 dp 리스트에 넣는다.

 

 

stock[1]이 어디에 삽입될 수 있는지 인덱스를 이분탐색을 이용하여 구한다. (index=0)

 

 

stock[2]가 어디에 삽입될 수 있는지 인덱스를 이분탐색을 이용하여 구한다. (index=0)

 

 

stock[3]은 1보다 크므로 바로 삽입

 

 

stock[4]는 4보다 크므로 바로 삽입

 

 

 

stock[5]가 어디에 삽입될 수 있는지 인덱스를 이분탐색을 이용하여 구한다. (index=1)

 

 

 

 

 

 

예제에서 볼 수 있듯이 최종 dp 수열은 진짜 최장 증가 부분 수열을 이루는 요소와는 상관 없으며, lis의 길이만 연관이 있다는 점이 중요하다

위 알고리즘을 적용하여 코드를 짜 보면 아래와 같다.

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNextInt()) {

			int n = in.nextInt();
			int[] stock = new int[n];
			int[] dp = new int[n];
			for (int i = 0; i < n; i++) {
				stock[i] = in.nextInt();
			}

			dp[0] = stock[0];
			int lastIndex = 0;

			for (int i = 1; i < n; i++) {
				if (dp[lastIndex] < stock[i]) {
					lastIndex++;
					dp[lastIndex] = stock[i];
				} else {
					int index = findIndex(dp, stock[i], lastIndex);
					dp[index] = stock[i];
				}
			}
			System.out.println(lastIndex + 1);
		}
	}

	public static int findIndex(int[] dp, int num, int lastIndex) {
		int left = 0;
		int right = lastIndex;

		while (left < right) {
			int mid = (left + right) / 2;
			if (dp[mid] == num) {
				return mid;
			}

			if (dp[mid] > num) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}

		return right;
	}
}

 

 

다른 방법으로는 `segment tree`를 사용하는 방법도 있다. segment tree를 사용하여 lis 길이를 구하는 방법은 아래와 같다.

1. 세그먼트 트리를 모두 0으로 초기화한다. , (stock[i], i) 객체를 만든 후 stock[i] 값에 대해 오름차순으로 정렬한다.

2. (stock[i], i)를 순회하면서 stock[i]에 대해 구간 [0, i]에서 최댓값을 구하고, 그 최대값+1을 세그먼트 트리의 인덱스 i인 리프 노드 값으로 업데이트한다. => i에 대해 구간 [0, i]에 지금까지 존재하는 LIS 길이+1 은 결국 stock[i]으로 끝나는 LIS길이와 같다.

3. 정렬된 객체를 순회하면서 LIS의 max 값을 찾는다.

 

 

 

가장 먼저 stock[i]=1인 i=2를 방문하게 된다.

먼저 구간 [0, 2]의 최댓값은 0이므로 1로 끝나는 LIS 길이는 1이고,

그 1 값을 인덱스 2에 업데이트 해 준다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

그 다음 stock[i]=2인 i=1를 방문하게 된다.

마찬가지로 [0, 1]의 최댓값은 0이므로 인덱스 1에 업데이트 해준다.

 

이때, 기존 LIS 결과가 증가하지는 않는다.

일단 이후 값이 언제 증가되는지 좀 더 보기로 하자.

 

 

 

 

 

 

 

 

 

 

 

 

그 다음 stock[i]=3인 i=5를 방문하게 되는데,

[0, 5]의 최댓값은 1이므로 인덱스 5에 2를 업데이트 해준다.

 

즉, 새로 보는 원소가 기존의 LIS 길이를 증가시키려면 

그 원소가 기존의 LIS보다 뒤에 나타나야 한다.

=> 이를 확인하는 것이 결국 구간 [0, i]의 최댓값을 보는 것이다.

이렇게 세그먼트 트리를 이용하여 stock[i]의 위치에 i번째 수를 마지막 원소로 가지는 lis의 길이를 업데이트함으로써 lis의 가장 긴 길이를 구할 수 있다.

 

 

 

 

 

 

 

 

마찬가지로 stock[i]=4인 i=3를 방문하게 된다.

[0, 3]의 최댓값은 1이므로 인덱스 3에 1+1=2를 업데이트 해준다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

stock[i]=5인 i=0를 방문하게 된다.

[0, 0]의 최댓값은 0이므로 인덱스 0에 0+1=1을 업데이트 해준다.

 

 

 

 

 

 

 

 

 

 

 

 

 

마지막으로 stock[i]=5인 i=4를 방문하게 된다.

[0, 4]의 최댓값은 2이므로 인덱스 4에 2+1=3을 업데이트 해준다

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

최종 구현을 직접 코드로는 안해봤지만... 나중에 업데이트 해 볼 생각히다