[BOJ] 가장 긴 증가하는 부분 수열(LIS)Series.java

#. Series 1

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

* The copyright in this matter is in BOJ

#. Solve

나무위키에 LIS의 자세한 설명이 기록되어있다(링크)

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ11053 {       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;           int N = Integer.parseInt(br.readLine());         int[] arr = new int[N + 1];         // 자신을 끝으로 하는 LIS 최장길이         int[] LIS = new int[N + 1];           st = new StringTokenizer(br.readLine());           for (int i = 1; i <= N; i++) {             arr[i] = Integer.parseInt(st.nextToken());         }           int res = 0;         for (int i = 1; i <= N; i++) {             // 자신만으로 LIS 구성했을 때의 길이는 1             LIS[i] = 1;               // 자신(i)의 앞에 있는 원소들과 비교             for (int j = 0; j < i; j++) {                 // 앞쪽 원소보다 자신이 큰 경우                 if (arr[j] < arr[i] && LIS[i] < LIS[j] + 1)                     LIS[i] = LIS[j] + 1;             }             // 현재 원소의 LIS 값과 전체 최대값하고 비교하여 최댓값 갱신             res = Math.max(res, LIS[i]);         }           System.out.println(res);       }   } Colored by Color Scripter

cs

---

#. Series 2

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

* The copyright in this matter is in BOJ

#. Solve

N의 범위가 1 ≤ N ≤ 1,000,000 라서

나이브한 LIS 로는 해결할 수 없다.

이 문제는 시간복잡도를 줄이기 위해

자신보다 앞에 있는 원소들과 비교하는 단계에서 이분탐색을 적용해야한다.

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
 
    static int[] nums;
    static ArrayList<Integer> lis;
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        nums = new int[N+1];
        // 최장 증가 수열 저장
        lis = new ArrayList<>();
        
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());  
        }
        
        for (int i = 1; i <= N; i++) {
            
            if(lis.isEmpty() || nums[i] > lis.get(lis.size() - 1))
                lis.add(nums[i]);
            else {
                int idx = binarySearch(lis.size(), nums[i]);
                lis.set(idx, nums[i]);
            }
        }
        
        System.out.println(lis.size());
    }
 
    private static int binarySearch(int end, int find) {
        
        int start = 0, mid = 0;
        // 이분탐색
        while(start <= end) {
            mid = (start + end) / 2;
            
            // find 보다 크다면
            if(find < lis.get(mid)) end = mid - 1;
            // find 보다 크다면
            else if(find > lis.get(mid)) start = mid + 1;
            // find 와 같다면
            else return mid;
        }
        
        return start;
    }
 
}
 

#. Code_API

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class BOJ12015_v2 {
 
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        // 각 LIS의 길이를 만족하는 맨 끝에오는 최솟값을 저장
        int[] LIS = new int[N];    
        
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());  
        }
        
        int size = 0;
        for (int i = 0; i < N; i++) {
            // 탐색키를 찾으면 해당 index return
            // 못 찾으면 음수값으로 자신이 삽입될 위치 return
                // -(삽입위치) - 1 : (0일 경우를 구별하기 위해 -1)
            int tmp = Arrays.binarySearch(LIS, 0, size, arr[i]);
            
            // 중복값이 없다면 tmp : 음수값
            // 삽입위치 환산
            if(tmp < 0) 
                tmp = Math.abs(tmp) - 1;
            LIS[tmp] = arr[i];
            
            // 맨 뒤에 추가할 경우
            if(tmp == size) ++size;
        }
        
        System.out.println(size);
    }
    
}