LIS(최장 증가 수열)

Longest Increasing Subsequence

• 어떤 수열이 왼쪽에서 오른쪽으로 나열돼 있으면, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출하는 문제
• 4, 2, 7, 4, 5, 1 이 주어졌을 때 최장 증가 수열은 2, 4, 5이며 길이는 3이다.

완전탐색 접근 방법

• 수열의 모든 부분 집합을 구해서 그 부분 집합이 증가 수열인지 판별
• 증가 수열 중 가장 길이가 긴 값을 구한다.
• 2N 개의 부분 집합
• 시간복잡도는 O(2n)

DP 접근 방법

• 1차원 배열 dp[i]에는 0~i 증가하는 부분 수열의 크기를 나타냄
• 이중 for문을 설계하여 각 수를 직접 비교해가며 증가하는 부분 수열의 크기를 카운트해준다.
  • i : 1 ~ n-1
  • j : 0 ~ i-1
• 가장 긴 증가하는 부분 수열 LIS는 dp[i] 중 최대값을 선택해 출력해주면 된다.

import java.util.Scanner;

/**
 * 시간복잡도(N ^ 2)
 * @author mingggkeee
 *
 */
public class DP_LIS {

	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];	// 자신을 끝으로 하는 LIS길이
		
		for(int i=0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		
		int max = 0;	// LIS 최장길이 저장
		
		// 모든 원소에 대해 자신을 끝으로 하는 LIS 길이 계산
		for(int i=0; i<N; i++) {
			LIS[i] = 1;	// 나 혼자 LIS일 때 1이니까 1로 초기화
			
			// 첫 원소부터 i원소 직전까지 비교
			for(int j=0; j<i; j++) {
				// 증가수열의 모습 확인
				if(arr[j] < arr[i] && LIS[i] < LIS[j]+1) {
					LIS[i] = LIS[j]+1;
					
				}
			}
			if(max<LIS[i]) {
				max = LIS[i];
			}
			
		}
		
		System.out.println(max);
		
		sc.close();
		
	}
	
}

이분탐색 접근방법

• 수열의 크기가 100만 만큼 크게 주어질 경우 DP를 통한 풀이는 시간초과가 발생한다.
• 효율성을 올리기 위해서 이진탐색을 통해 시간 복잡도를 O(nlogn)으로 줄여줄 수 있다.

설명이 너무 어렵다...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * O(NlogN)
 * @author mingggkeee
 *
 */
public class BinarySearch_LIS {

	static int[] memo;
	static int INF = Integer.MIN_VALUE;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] nums = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		memo = new int[N+1];
		int len = 0;
		int idx = 0;
		for(int i=0; i<N; i++) {
			if(nums[i] > memo[len]) {
				len += 1;
				memo[len] = nums[i];
			} else {
				idx = binarySearch(0, len, nums[i]);
				memo[idx] = nums[i];
			}
		}
		
		System.out.println(len);
	}
	
	static int binarySearch(int left, int right, int target) {
		
		int mid = 0;
		while(left<right) {
			mid = (left+right)/2;
			if(memo[mid] < target) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		
		return right;
		
	}
	
}