최장 증가 부분 수열(LIS) 알고리즘 - JAVA

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

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

예를 들어 주어진 수열이 위와 같을 때 만들어 질 수 있는 증가하는 부분 수열은 

위와 같이 같은 색으로 묶인 {2, 4}, {1, 2, 3}, {1, 5, 6} 등 여러가지가 있을 수 있지만

위 그림과 같이 원소 5개로 이루어진 {1, 2, 3, 5, 6}이 수열 A에서 가장 긴 증가하는 부분 수열이다. 이렇게 최장 증가 부분수열을 구하는 알고리즘에 대해 알아보자.

풀이방법

LIS 길이 구하기 - DP: O(n^2)

LIS 길이 구하기 - 이분탐색: O(n log n)

DP를 이용하여 구할 경우 구현이 간단하지만 시간복잡도가 O(n^2)으로 수열의 길이가 길어질수록 효율이 떨어지게 된다.
해당 문제를 해결하기 위해 이분탐색을 이용하는 방법이 있다.

모든 원소에 대하여 LIS를 구하는데 각 원소마다 오름차순으로 들어갈 위치를 이분탐색으로 찾는 방법이다.
LIS의 길이를 length라 했을 때, 시작 단계에서 0으로 초기화를 해준다.

위와 같이 수열이 존재할 때 가장 앞 원소부터 들어갈 위치를 찾는다. A[0]의 경우 LIS의 배열이 비어있으므로 LIS[length]에 들어가게 되고, top = 1이 된다.
LIS[length-1] = 2
length = 1

A[1]인 4는 LIS에 들어간 원소의 가장 마지막 숫자(LIS[length-1] = 2)보다 크기 때문에 LIS 배열에 들어가며 length은 증가하게 된다.
`lis[length++] = A[1];`
LIS[length-1] = 4
length = 2

A[2]=2일 경우, LIS에서 가장 마지막 원소인 4보다 작기 때문에 이분탐색을 통해 A[2]와 같은 숫자이거나 A[2]보다 큰 수 중에 가장 작은 숫자의 위치를 차지하게 된다.
`lis[binarySearch(A[2])] = A[2];`
LIS[length-1] = 4
length = 2

그 다음 원소인 A[3]=1또한 마찬가지로 LIS[top-1]=4보다 작으므로 이분탐색을 통해 들어갈 위치를 찾는다. 같은 숫자가 존재하지 않으므로 A[3]보다 크면서 가장 작은 수인 2의 위치인 LIS[0]을 업데이트 하게 된다.
`lis[binarySearch(A[3])] = A[3];`
LIS[length-1] = 4
length = 2

같은 방법으로 진행할 경우를 설명을 생략하고 그림으로 확인한다면 아래 과정과 같다.

`lis[length++] = A[4];`
length=3

`lis[length++] = A[9];`
length=4

`lis[length++] = A[13];`
length=5

그러므로 LIS의 길이는 5가 된다.

코드

이를 코드로 구현하면 아래와 같다.

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

public class Main {
    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[] A = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        int[] lis = new int[N];
        int top = 0;
        for (int num : A) {
            if (top == 0 || lis[top - 1] < num) {
                lis[top++] = num;
                continue;
            }
            lis[binarySearch(lis, top, num)] = num;
        }
        System.out.println(top);
    }

    private static int binarySearch(int[] lis, int top, int num) {
        int start = 0;
        int mid = 0;
        int end = top;
        while (start <= end) {
            mid = (start + end) / 2;
            if (lis[mid] == num) {
                return mid;
            } else if (lis[mid] < num) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        if (lis[mid] < num) {
            return mid + 1;
        } else {
            return mid;
        }
    }
}

연습문제

[BOJ] 가장 긴 증가하는 부분 수열 2 - https://www.acmicpc.net/problem/12015

 

 

-수정중