LIS(최장 증가 수열 ) - 백준 11053 (JAVA)

서론

최장 수열은 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 문제이다.

 

일반적으로 길이를 저장하는 테이블을 만들어 해결한다.

 

이럴경우 이중반복문을 사용하기에 시간복잡도는 O(N^2)이 된다.

 

또 다른 방법은 Binary search를 이용하여 O(NlogN)의 시간복잡도를 갖는 방법도 있다.

 

구현 코드

 

memo[0] = 1;
        for (int i = 1; i < N; i++) {
            memo[i] = 1; //항상 1로 초기화
            for (int j = 0; j < i; j++) {
                if(arr[i]>arr[j] && memo[i] <memo[j]+1) //현재 자신보다 크거나 저장된 memo배열값이 기존의 길이+1보다 작으면
                    memo[i] = memo[j]+1;
            }
            cnt = Math.max(cnt, memo[i]); //최장길이 계속 갱신
        }

 

문제에 적용

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

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

 

알고리즘

 

위와 말한 것 같이 2가지 방법이 있는데 2가지 방법 모두 문제의 시간안에 해결된다.

 

이진 탐색으로 구현할 때는 memo배열의 인덱스(size)를 제어하는 것이 중요하다.

 

구현코드

 

public class Main_11053_binary {
    static int memo[];
    static int N;
    static int arr[];
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(in.readLine().trim());
        arr = new int[N];
        memo = new int[N]; //LIS를 저장할 배열
        StringTokenizer s = new StringTokenizer(in.readLine()," ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(s.nextToken());
        }
        int size = 0; //LIS 개수 memo배열에 저장할 LIS 저장위치

        memo[size++] = arr[0]; // 첫번째 수열 저장 
        for (int i = 1; i < N; i++) {
            System.out.println(Arrays.toString(memo));
            if(memo[size-1] < arr[i])
                memo[size++] = arr[i];
            else //증가 수열이 아니면 
            {
                int idx = Arrays.binarySearch(memo,0,size,arr[i]);
                 //이진 탐색 함수는 target을 못찾을 경우 음수로 마지막 찾은 위치를 반환한다.
                System.out.println("idx= "+idx);
                if(idx < 0) //a[i]와 같은 값이 없으면 idx는 음수로 마지막까지 찾은 위치
                {
                    idx = -idx-1;
                }
                memo[idx] = arr[i];
            }
        }
        System.out.println(size);
    }
}