2 min to read

LIS 알고리즘

LIS 알고리즘이란?

Imagem de capa

최장 증가 수열 LIS(Longest Increasing Subsequence)

백준 문제를 통해 풀어봅시다.
가장 긴 증가하는 부분 수열

O(N^2) 이중 for문으로 해결할 수도 있지만 O(NlogN)으로 만들어봅시다!

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

public class Main{

    public static void main(String[] args) throws IOException {

        int N; // array length
        int[] A;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        A = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {

            A[i] = Integer.parseInt(st.nextToken());
        }

        // O(N log N)
        System.out.println(LISLength(A, N));

    }
    //10,20,10,30,20,50
    static int LISLength(int[] A, int size) {

        int[] tailTable = new int[size];
        int lisLength = 0; // always points empty slot

        tailTable[0] = A[0];
        lisLength = 1;

        for (int i = 1; i < size; i++) {

            // 후보값이 LIS의 처음 값보다 작으면 바꿔줍니다.
            if (A[i] < tailTable[0]) {

                tailTable[0] = A[i];
            }

            // 후보값이 LIS의 마지막 값 보다 크다면 마지막에 넣어줍니다.
            else if (A[i] > tailTable[lisLength - 1]) {

                tailTable[lisLength] = A[i];
                lisLength++;

             // CeilIndex를 찾고 replace합니다.
            } else {

                int idx1 = Arrays.binarySearch(tailTable, 0, lisLength, A[i]);

                idx1 = idx1 < 0 ? -idx1 - 1 : idx1;

                tailTable[idx1] = A[i];

            }

        }

        return lisLength;
    }
}