[알고리즘] LIS

LIS

 LIS는 Longest Increasing Subsequence 의 약자로 한글로는 ‘최장 증가수열’, 또는 ‘최대 증가 부분수열’로 불린다. 

이것은 어떤 수열에서 특정 부분을 지워서 만들어낼 수 있는 증가 부분수열 중 가장 긴 수열을 말하는데 이때 부분수열의 숫자들은 원 배열에서 위치가 이어져 있지 않아도 된다는 주요한 특징이 있다. 예를 들어 원 배열이 [1,4,6,8,3,5,6,7]일 때 [1,6,8], [4,6,8], [1,7]은 증가 부분수열인데, 이 중 가장 긴 부분수열은 [1,3,5,6,7]이 된다.

 

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

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

LIS의 이해를 위한 대표적인 문제이다. 그렇다면 LIS를 구하기 위해서는 어떠한 아이디어를 활용해야 할까? 가장 먼저 쉽게 떠올릴 수 있는 방법은 brute force방법이었다. 

 

 

1. Brute Force LIS

 

 배열의 길이보다 짧은 부분수열들을 찾아가면서 검사한다면 가장 긴 길이를 갖는 부분배열을 찾아낼 수 있다. 완전탐색이라는 말에 알맞게 원배열의 모든 부분집합들을 검사할 것이기 때문이다. 하지만 완전탐색의 단점인 수행시간에서 많은 손해를 보기 때문에 (길이 l짜리 배열의 부분집합의 개수는 2^l로 지수적 시간복잡도를 가진다) 다른 방법을 사용하자.

 

 

2. DP LIS - O(N^2)

 

 그렇다면 완전탐색에서 중복되는 부분을 제거하기 위해 동적 계획법을 사용할 수 있다. 

lis(i):i번째 원소에서 끝까지 증가수열의 길이의 최대값

위 그림을 보면 알수있듯, 원배열 내에서의 최장 길이 부분배열을 찾는 문제이기 때문에, 임의의 인덱스 i에서 배열의 끝까지의 배열 중에서 가장 큰 부분배열의 길이는 유일하다. 즉, 인덱스 i를 포함하는 부분배열은 인덱스 i에서 배열의 끝까지의 가장 큰 부분배열을 포함한다. 따라서 bottom-up approach를 사용하는 DP의 사용이 가능해진다. 

int N = 원배열의 크기(index);
int[] arr = new int[N];
int[] dp = new int[N];
for(int i=0; i<N; i++) {dp[i]=1;}
int max=0;

for(int i=0; i<N; i++) //오른쪽에 위치한 수들에 대하여
    for(int j=0; j<N; j++) 
        if(arr[i]<arr[j]) //조건에 맞을경우 캐시에 저장
            dp[j] = max(dp[j], dp[i]+1);

위 알고리즘은 각 루프에서 배열 전체의 루프를 한번씩 돌며 조건에 맞을 경우 캐시(dp)에 값을 저장해가며

1. index j (j<i)의 LIS수열의 마지막에 arr[i]를 추가했을 때의 LIS길이
2. index i의 LIS길이

중에 큰 값으로 업데이트하는 과정을 통해 값을 업데이트하는 방법을 통해 O(N^2)의 polynomial 시간복잡도를 가진다. 핵심은 역시 동적 계획법을 이용하여 다시 사용될 값을 저장해두고 연산하여 중복된 계산을 줄이는 과정이다. DP를 사용하지 않는다면 모든 LIS부분수열의 길이를 구하는데 idx 0부터 검사해야하기 때문에 매우 복잡할 것.

 

 

3. Binary Search LIS - O(NlogN)

 

 앞서 살펴봤던 알고리즘은 DP를 사용하여 중복을 줄였지만, 그래도 LIS길이를 최적화하는데 모든 j(j<i)를 검사하기 때문에 O(N^2)라는 시간복잡도를 갖는다.  따라서 배열의 크기가 큰 경우 이진탐색을 통한 Lower bound 설정을 통해서 시간복잡도를 줄일 수 있다.

 LIS를 구하기 위해서 주어진 배열에서 부분 수열을 찾고 있다고 하자. 배열의 끝까지 찾기 전에는 지금 찾고 있는 수열이 LIS의 일부인지 알기 어려울 것이다. 따라서 시간복잡도 단축을 위해서 이분탐색을 사용한다. 아래의 방법을 한마디로 설명하자면 하나의 배열에 부분증가수열들을 덮어씌워 최종적으로 남는 길이를 구하는 것이다.

 

참고 문제) https://www.acmicpc.net/problem/12015

 

출처:&nbsp;https://loosie.tistory.com/376

 우리의 목적은 가장 긴 부분 증가수열의 길이를 찾는 것이 목적이므로, 최종적으로 구하는 수열의 길이가 LIS의 길이가 될 것이다. 따라서 원래 수열을 arr이라고 하면, arr을 탐색해나가면서 memo라는 별도의 저장공간에 LIS 수열을 만들어나간다.

 단 이 방법만을 사용하면 LIS의 길이만을 구할 수 있다. LIS의 idx까지 구하기 위해서는 추가적인 방법이 필요한데, 유사 리스트와 같이 구현할 수 있다. 

그렇다면 이분탐색을 이용한 LIS배열 자체를 구하라고하면 어떻게 해야할까..