LIS 최장 증가 부분수열

1. 개념

 

2. 예시

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOKg-a6l0DFAWr

SW Expert Academy

O(N^2) 풀이법

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class swea_3307최장증가부분수열 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			int n = sc.nextInt();
			int lis[] = new int[n];
			int val[] = new int[n];
			for (int i = 0; i < val.length; i++) {
				lis[i]=1;
			}
			for (int i = 0; i < n; i++) {
				val[i] = sc.nextInt();
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < i; j++) {
					if(val[j] < val[i] && lis[i] == lis[j]) {
						lis[i]++;
					}
				}
			}
			Arrays.sort(lis);
			System.out.println("#"+tc+" "+lis[n-1]);
		}
	}
}

 

입력값과 이미 탐색한 부분을 비교하는 조건문

값이 더 크면서, 증가하는 길이가 같다면 더 뒤에 올수 있다는 뜻이어서 lis를 하나 증가시킨다.

if(val[j] < val[i] && lis[i] == lis[j]) {
	lis[i]++;
}

www.acmicpc.net/problem/12015

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

NlogN 풀이법

import java.util.Arrays;
import java.util.Scanner;

public class back_12015가장긴증가하는부분수열2 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int arr[] = new int[n];
		int lis[] = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		int size = 0;
		for (int i = 0; i < n; i++) {
			int k = Arrays.binarySearch(lis, 0, size, arr[i]);
			if (k < 0) {
				int temp = Math.abs(k) - 1;
				lis[temp] = arr[i];
				if (size == temp)
					size++;
			}
		}
		System.out.println(size);
	}
}
//반복문돌면서 키보다 짧은 자리를 찾고 갱신
//사이즈하고 찾은 자리값과 같으면 사이즈 늘려준다

//for n
	//temp = binerySearch(lis,0,size,arr[i])
	//arr = abs(temp) -1
	//if temp == size
		//size++
	//lis를 출력
	

이론

 

{3,2,6,4,5,1}배열이 주어질 때, arr의 값을 기준으로 lis값이 더 작아야한다.

더 작은것중 가장 큰 값을 갱신한다. 

 

lis의 각 길이 마다 가장 작은 값을 저장하고 있다.

lis크기가 1이라면 1~6까지 올수 있는데 이때, 1이 가장 작은 값

lis크기가 2라면 (3 6) (3 4) (2 6) (2 4) (4 5)가 올 수 있다. 이때 4가 가장 작은값이다. 

즉 lis의 최종 길이는 최장 증가 수열이다. 하지만 그 data는 lis가 아니다. 길이만 알 수 있다