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

백준의 11053과 같은 유형을 흔히 `최장 증가 부분 수열(Longest Increasing Subsequence,LIS)라 하는데 이를 구하는 방법은 크게 두가지가 존재한다.

 

1. DP를 이용한 풀이 (가장 기본적 간단, 시간복잡도:O(n^2))

• 파이썬

import sys
sys_input=sys.stdin.readline

n=int(sys_input())
arr=list(map(int,sys_input().rstrip().split()))
dp=[1]

for i in range(1,n):
    find=0
    for j in range(i):
        if arr[i]>arr[j]:
            find=max(find,dp[j])

    dp.append(find+1)

print(max(dp))

 

• 자바

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        int[] dp = new int[n];

        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(st.nextToken());
            int find = 0;

            for (int j = 0; j < i; j++) {
                if (arr[j] < x) {
                    find = Math.max(find, dp[j]);
                }
            }
            arr[i] = x;
            dp[i] = find + 1;
        }

        System.out.println(Arrays.stream(dp).max().getAsInt());
    }
}

 

 

위의 두 코드와 같이 DP배열에 현재 인덱스까지 포함한 최장 증가 부분 수열을 찾게된다.

 

그리고 이후 DP배열의 최대값을 찾으면 그것이 전체 수열의 LIS가 된다.

 

 

문제점

 

하지만 이 방식은 시간복잡도가 O(n^2)이기에 수열의 길이가 상당히 긴 경우 시간 초과가 발생할수 있다.

 

 

 2. 이분탐색을 이용한 풀이 (시간복잡도:O(nlog n))

이분탐색을 적용하여 LIS를 구할수 있다. 이분탐색의 시간복잡도는 O(log n)이고 이를 모든 인덱스에 대해 수행하기에 시간복잡도는 O(nlog n)이 되게 된다.

 

작동 방식은 아래와 같다.

 

0. 초기 arr[0]의 값을 빈 배열(lis)의 맨앞에 넣어준다.

 

1. 첫번째 인덱스부터 마지막까지 아래와 같은 과정을 수행한다.

 

1.a arr[i]가 lis의 마지막 인덱스의 값보다 큰경우

    - lis의 뒤에 arr[i]를 넣어준다.(python의 append)

 

1.b arr[i]가 lis의 마지막 인덱스의 값보다 작거나 같은경우

    - arr[i]가 lis에 들어갈 위치를 이분탐색을 통해 찾는다.(lis를 기준으로 arr[i]의 이분탐색)

    - 이분탐색 결과로 나온 인덱스에 arr[i]를 넣어준다.

 

 

적용 예시

 

• 파이썬 (bisect를 이용)

import sys
from bisect import bisect_left

sys_input=sys.stdin.readline

n=int(sys_input())
arr=list(map(int,sys_input().rstrip().split()))
ans=[arr[0]]

for i in range(1,n):
    if ans[-1]<arr[i]:
        ans.append(arr[i])
    else:
        idx=bisect_left(ans,arr[i])
        ans[idx]=arr[i]

print(len(ans))

 

• 자바

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

public class Main {
    public static int n;
    public static int[] arr;
    public static int[] ans;
    public static int len;

    public static int bs(int x) {
        int low = -1;
        int high = len;

        while (low + 1 < high) {
            int mid = (low + high) / 2;

            if (ans[mid] >= x) {
                high = mid;
            } else {
                low = mid;
            }
        }

        return high;
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        arr = new int[n];
        ans = new int[n];
        len = 1;

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        ans[0] = arr[0];

        for (int i = 1; i < n; i++) {
            if (ans[len - 1] < arr[i]) {
                ans[len] = arr[i];
                len += 1;
            } else {
                int idx = bs(arr[i]);
                ans[idx] = arr[i];
            }
        }

        System.out.println(len);
    }
}

 

 

결론

 

문제의 시간 제한과 수열의 최대 길이 조건을 보고 적절하게 둘을 사용하자.