최적화된 LIS(Longest Increasing Subsequence) 알고리즘과 해 찾기

LIS는 알고리즘 문제로써도, 코드 구현으로써도 너무나도 유명한 문제이지만 최적화된 해법을 찾는 과정은 문제 해결능력에 있어 큰 도움을 준다.

개인적으로 매력있게 느끼는점은 인간이 직관적으로 쉽게 찾을 수 있는 법을 논리적으로 찾기가 쉽지 않으며, 그를 위한 수학적 방법들에 있었다.

LIS 알고리즘은 주어진 수열 내에서 가장 긴 부분 수열을 찾아내는 알고리즘이다. 

가령 다음과 같은 수열이 주어져있을 때를 생각해보자.

위와 같이 주어진 수열에서, LIS 는 10, 20, 50, 90 또는 10, 20, 40, 60 등으로 구해낼 수 있으며 가장 긴 증가하는 부분 수열의 길이는 4라는 걸 직관적으로 구할 수 있다.

하지만, 알고리즘으로 옮기려고 한다면 이 직관을 표현하는 건 쉽지 않다. 

또한 우리는 구현에 있어서 매 Index에 대해 다른 전체 Index를 검색해야하는 어마어마한 시간 복잡도에 마주하게 된다.

이는 최적화 알고리즘 기법의 한종류인 Dynamic Programming 을 이용해도 마찬가지인데, DP로 구현할 시 알고리즘은 다음과 같다.

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

if (dp[i] == 0) {

dp[i] = 1;

}

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

if (num[i] > num[j]) {

dp[i] = Math.max(dp[i], dp[j]+1);

}

}

}

위의 알고리즘의 경우에도 역시 시간 복잡도는 O(N^2) 이 되고, N이 커질수록 부담스러운 알고리즘이 된다.

만약 N이 10000이 넘어간다면? 그때는 눈으로 보일만큼 성능에 영향을 주는 모듈이 되게 된다.

최장 부분 수열의 길이를 구하는 데 있어서 최적의 방법은 일반적으로 O(N logN) 알고리즘으로 알려져있고, Trace 배열을 정의해서 같은 시간복잡도에 최장 부분 수열까지도 알아낼 수 있다.

공부할 당시 최장 부분 수열의 길이를 구하는 부분은 간단했으나, 최장 부분 수열 자체를 O(N logN) 시간 안에 구하는게 쉽지 않았던 기억이 있어 정리해보았다.

최적화의 핵심은 Binary Search 이고, lis 라는 별도의 배열에 내용을 담는다. 과정은 다음과 같다.

먼저, 배열의 각 요소를 순회한다. 이때, 배열의 각 요소를 lis 배열에 담는데, lis 배열에는 작은 순서대로만 들어가야한다.

그를 위해서는, lis 배열의 가장 마지막 요소(우리는 lis 배열을 증가하는 순서로 담았기 때문에 lis 배열의 최댓값이다.)와 배열의 요소를 비교하면 된다.

만약 lis 배열의 최댓값보다 크다면, 해당 요소를 lis 배열의 마지막에 추가시켜주면 된다.

하지만, 다음 요소는 lis 배열의 마지막 요소보다 작다. 이 때 Binary Search 가 필요하다. 우리는 Binary Search 를 통해 

"정렬된" LIS 배열에서 arr 요소가 들어가야할 위치를 찾을 수 있다.

예시에서 이제 LIS 배열은 다음과 같이 변한다.

이런식으로, LIS 배열을 증가하는 부분수열로 만들어 놓으면 쉽게 최장 부분수열의 길이를 O(N logN) 시간복잡도로 구할 수 있다.

하지만, 이런 구현만으로는 어떤 요소가 최장 부분 수열을 구성하는지 알 수 없다. 

가령, 다음과 같이 배열의 마지막 요소가 첫번째 요소보다 작을 경우, 이 구현을 통해 수열 자체를 구하는건 불가능하다.

따라서, lis 배열을 채울때, 어떤 항목이 참조되는지 Reference 배열을 정의하여 요소들을 Tracing 하는 테크닉을 사용한다.

-- LiS 구현(C++) --

/* Find LIS NLogN */

int arr[100001] = {0, };

int lis[100001] = {0, };

int lisCnt = 0;

int trace[100001] = {0, };

int findLIS(int n) {

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

if(i == 0 || arr[i] > lis[lisCnt-1]) {

trace[arr[i]] = lisCnt;

lis[lisCnt++] = arr[i];

} else {

int start = 0, end = lisCnt;

int idx = lisCnt;

while(start<end) {

int mid = (start+end)/2;

if(lis[mid] >= arr[i]) {

idx = min(idx, mid);

end = mid;

} else{

start = mid+1;

}

}

lis[idx] = arr[i];

trace[arr[i]] = idx;

}

}

//trace 배열에서 가장 나중을 꺼내면 됨.

int cur = lisCnt-1;

for(int i=n-1; i>=0; i--) {

if(trace[arr[i]] == cur) {

lis[cur] = arr[i];

cur--;

}

}

return lisCnt;

}

Trace 배열을 사용하면 위와 같이 LIS 알고리즘 사용 중 Refenrence를 저장하는 방식으로 최장 부분 수열의 추적도 가능하다.

Trace 배열에 저장된 인덱스를 끝에서부터 가져오면 최장부분순열 자체를 역순으로 구해낼 수 있다.

알고리즘의 시간복잡도는 O(N logN) 으로 DP 구현보다 효율적인 시간복잡도로 작동하게 된다.

이 방법 외에도 Segment Tree 등을 이용해 최적화된 구현이 가능하다.