LIS / ( lower_bound , upper_bound )

[WonYong-Jang]

N^2 방법

dp[i] = data[i] 를 마지막 원소로 하는 증가 부분 수열의 최장 길이

for(int i=1; i<= N; i++)
{
	for(int j=0; j < i; j++)
	{
		if(data[i] > data[j] && dp[i] < dp[j] + 1)
		{
			dp[i] = dp[j] + 1;
		}
	}
	result = max(result, dp[i]);
}
System.out.println(result);

Lower Bound 를 이용한 방법 / nlogn

dp 는 길이가 x인 최장증가수열의 마지막 수의 최소값을 의미

• 배열을 하나 생성해서 매번 수열을 구할때 마다 배열의 맨 뒤 원소와 현재 보고 있는 수열의 원소를 비교하여 수열의 원소가 더 클 시 배열 뒤에 push 해준 후 사이즈 +1
• 만약 수열의 원소가 배열의 맨 뒤 원소보다 작을 경우 lower_bound를 이용하여 최적의 자리를 찾은 뒤 그자리값을 해당 수열의 원소로 교체

ex ) 10, 20, 40, 30, 70, 50, 60

1. 처음값 10을 넣어줌 : 배열의 최대 배열 사이즈 1
2. 20 값은 배열 마지막 값인 10보다 크므로 배열 뒤에 추가 : 배열 사이즈 2
3. 40 추가 : 배열 사이즈 3 / (10, 20, 40)
4. 30 값은 배열의 마지막 값인 40보다 작으므로 lower_bound 를 이용하여 40자리에 30을 치환 / (10,20, 30)
5. 70 추가 : 배열 사이즈 4 ( 10, 20, 30, 70)
6. 50 값을 70과 치환 (10, 20, 30, 50) : 배열사이즈 4
7. 60 추가 : 배열 사이즈 5 (10, 20, 30, 50, 60)

고려해야 할 부분

• 자기 뒤에 참조를 한다면 더 적은 값에서 참조를 하는 것이 유리하기 때문에 6번과 같이 70을 50과 치환이 가능
• 주의할 점은 dp 배열에 있는 값들은 LIS를 이루는 요소과 무관한 값들!! ( 수열상에서 뒤에 있던 원소가 먼저 들어온 원소보다 lower_bound로 탐색된 최적의 위치가 앞에 있을 수도 있기 때문!!)

size = 1;
dp[1] = data[1];
for(int i=2; i<= N; i++)
{
	if(data[i] > dp[size]) // dp 맨뒤에 있는 자리와 비교하여 더 큰값이면 이어 붙이기  
	{
		dp[++size] = data[i];
	}
	else if(data[i] < dp[size])
	{
		int tdx = lower_bound(1,size,data[i]);
		dp[tdx] = data[i];
		}
	}
}
System.out.println(size);

lower_bound 방식 ( lis 요소들 추적 가능한 방법! )

• 위의 방식은 LIS 길이를 구하는 방식이지만 해당 길이의 요소를 알수없다. ( 주의 )
  ans 라는 pair 배열을 새로 만들고 정의해야함

• ans[].dx : 실제 그 값이 들어갈수 있는 위치

• ans[].dy : 실제 해당하는 값

실제 lis 배열을 구하는 알고리즘을 보자
예를들면 다음과 같다.
1 6 2 5 7 3 5 6인 경우
ans배열에는 다음과 같이 들어간다.
dx :: 0 1 1 2 3 2 3 4
dy :: 1 6 2 5 7 3 5 6
이 값을 dx를 기준으로 뒤에서 부터 조사해오면
dx가 4일때 (6) - > dx가 3일때 (5) -> dx가 2일때 (3)
-> dx가 1일때 (2) -> dx가 0일때(1)이다.

이것을 스택에 담아 역출력하면 1,2,3,5,6이라는 실제 배열을 구할 수 있다.

public class baek14002 {

	static int N;
	static int[] data = new int[1005];
	static int[] dp = new int[1005];
	static Node[] ans = new Node[1005];
	static Deque<Integer> que = new ArrayDeque<>();
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<= N; i++)
		{
			data[i] = Integer.parseInt(st.nextToken());
			ans[i] = new Node(-1,-1);
		}
		
		dp[1] = data[1];
		ans[1].dx = 1; // 실제 인덱스 1로 처음 시작 
		ans[1].dy = dp[1]; // 실제 값 
		int size = 1;
		for(int i=2; i<= N; i++)
		{
			if(dp[size] < data[i])
			{
				dp[++size] = data[i];
				ans[i].dx = size;
				ans[i].dy = data[i];
			}
			else {
				int idx = lower_bound(1, size, data[i]);
				dp[idx] = data[i];
				ans[i].dx = idx;
				ans[i].dy = data[i];
			}
		}
		System.out.println(size);
		// 인덱스 i=2 부터 계속 해서 업데이트 해왔으므로
		// 맨뒤 인덱스 부터 찾아 나감 
		int t = size;
		for(int i = N; i > 0; i--)
		{
			if(t == ans[i].dx)
			{
				que.addLast(ans[i].dy);
				t--;
			}
		}
		
		while(!que.isEmpty())
		{
			int num = que.pollLast();
			System.out.print(num+" ");
		}
	}
	static class Node {
		int dx, dy;
		Node(int a, int b) {
			dx=a; dy=b;
		}
	}
}

lower_bound 란?

• 이분 탐색을 통해 해당 위치를 return 해주는 방식

인덱스 트리를 이용한 방법 / nlogn

설명 : https://m.blog.naver.com/kks227/220791986409
(그림 확인)

• A[i] = x 값들을 모두 받아서 (x, i) pair 들을 만든 후 x 기준 오름차순 정렬
  A[i]=x 인 i에 대해 구간 [0,i]에 지금까지 존재하는 lis 길이 +1이 x로 끝나는 lis 길이

주의 사항

• 중복된 값이 발생할 경우
  ==> 중복되는 값들 중에서는 가장 큰 인덱스 부터 방문해야 함!!!
  ==> 정렬할때 값 기준 오름차순 / 같은 값있을 경우는 인덱스 기준 내림차순

public class Main {

	static int N, start, result;
	static final int max_node = 500005;
	static ArrayList<Node> arr = new ArrayList<>();
	static int[] tree = new int[4*max_node];
	static int[] dp = new int[max_node];
	static Deque<Integer> que = new ArrayDeque<>();
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		N = Integer.parseInt(st.nextToken());
		start = 1; result = 0;
		int chk = 0; // 트리의 시작 인덱스를 찾기 위한 최대 노드 값 
		
		int dx = 0, dy = 0;
		for(int i=1; i<= N; i++)
		{
			st = new StringTokenizer(br.readLine());
			dx = Integer.parseInt(st.nextToken());
			dy = Integer.parseInt(st.nextToken());
			arr.add(new Node(dy,dx));
			chk = max(chk, dx);
		}
		
		while(chk > start) start *= 2;
		Collections.sort(arr, new mySort());
		
		for(Node cur : arr)
		{
			int cnt = query(1, cur.idx); // 1 ~ i-1 까지의 최대 lis 
			update(cur.idx, cnt+1);
			result = max(result, cnt+1);
			dp[cur.idx] = cnt+1;
		}
		bw.write( (N-result) +"\n");
		int size = result;
		for(int i = chk; i > 0; i--)
		{
			if(dp[i] == 0) continue;
			if(dp[i] == size) {
				size--;
				continue;
			}
			que.addLast(i);
		}
		while(!que.isEmpty())
		{
			int num = que.pollLast();
			bw.write(num+"\n");
		}
		bw.flush();
	}
	public static void update(int idx, int num)
	{
		int s = start + idx - 1;
		
		while(s > 0)
		{
			if(tree[s] < num)
			{
				tree[s] = num;
				s /= 2;
			}
			else break;
		}
	}
	public static int query(int sdx, int edx)
	{
		int ret = 0;
		int s = start + sdx - 1;
		int e = start + edx - 1;
		
		while(s <= e)
		{
			if(s % 2 == 1)
			{
				if( ret < tree[s])
				{
					ret = tree[s];
				}
			}
			
			if(e % 2 == 0)
			{
				if( ret < tree[e])
				{
					ret = tree[e];
				}
			}
			
			s = (s+1) / 2;
			e = (e-1) / 2;
		}
		return ret;
	}
	public static int max(int a, int b)
	{
		return a > b ? a : b;
	}
	static class mySort implements Comparator<Node>{ // 값에 대한 오름차순으로 정렬 하고 동일한 값이 있을 때는 인덱스가 큰 값 기준으로 내림 차순 정렬 
		@Override
		public int compare(Node a, Node b) {
			// TODO Auto-generated method stub
			if(a.num < b.num) return -1;
			else if(a.num > b.num) return 1;
			else {
				if(a.idx > b.idx) return -1;
				else if(a.idx < b.idx) return 1;
				else return 0;
			}
		}
	}
	static class Node {
		int num, idx;
		Node(int a, int b){
			num=a; idx=b;
		}
	}
}

[WonYong-Jang]

함정 문제

백준 11055번 가장 큰 증가 부분 수열

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

7570번: 줄세우기 https://www.acmicpc.net/problem/2631

LIS 문제 모음 : https://github.com/hotehrud/acmicpc/tree/master/algorithm/lis

[WonYong-Jang]

Lower_bound

원하는 값 k 이상의 값이 처음으로 나오는 인덱스를 리턴

주의 ! : 만약 모든 원소가 k 보다 작으면 n+1 을 출력하게 되는데 그렇기 때문에 !!!

===> 처음 구간을 잡을때 [1,n+1] 로 잡을것!!!!!!!!!!!!!!!!!
ex1) 1 3 5 7 7 / target : 7 일 때 ==> 4번째 인덱스 리턴
ex2) 1 2 3 5 7 9 11 15 / target : 6 일때 ==> 5번째 인덱스 리턴
ex3) 1 2 3 4 5 / target : 7 일때 ==> 6번째 인덱스 출력 ( n + 1 )

public static int lower_bound(int s, int e, int target)
{
	int mid =0;
	while( s < e)
	{
		mid = (s + e) / 2;
		if(data[mid] < target) {
			s = mid + 1;
		}
		else {
			e = mid;
		}
	}
	return e;
}

Upper_bound

원하는 값 k를 초과한 값이 처음 나오는 인덱스 리턴

public static int upper_bound(int s, int e, int target)
{
	int mid =0;
	while( s < e)
	{
		mid = (s + e) / 2;
		if(data[mid] <= target) {
			s = mid + 1;
		}
		else {
			e = mid;
		}
	}
	return e;
}