LIS (Longest increasing subsequence) nlogn 해법

LIS(Longest Increasing Subsequence) 정의

컴퓨터 공학에서, 최장 증가 부분 수열(Longest Increasing Subsequence) 문제는, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 문제이다. 여기서의 부분 수열은 연속적이거나 유일할 필요는 없다.

최장 증가 부분 수열 - 위키백과

https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EC%A6%9D%EA%B0%80_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4

LIS 문제는 수열에서 주어진 순서에서 벗어나지 않으면서 숫자가 증가하는 가장 긴 부분수열을 찾는 문제이다. 예를 들어 6개의 숫자가 주어져있다고 하자.

0	1	2	3	4	5
10	20	10	30	20	50

여기서 만들 수 있는 증가하는 부분 수열은 무엇이 있을까.

몇가지 예시를 들어보자면 아래와 같은 부분 수열이 있을 것이다.

{ 10 }, { 20 }, ... { 10, 20 }, { 10, 30 }, ... { 10, 20, 30 }, ... { 10, 20, 30, 50 }

여기서는 가장 긴 부분 수열은 { 10, 20, 30, 50 }의 길이 4인 부분 수열일 것이다.

그렇다면 우리는 어떻게 nlogn의 시간 복잡도 내에서 이문제를 풀 수 있을까.

기본적인 풀이 아이디어는

1. 뒤로 가면서 큰 수는 뒤로 계속 이어 붙이고 

2. 중간에 끼어들 수 있는 수는 이분탐색을 이용하여 적절한 자리를 찾아 교체시키는 방식으로 수열을 만들어간다. 

3. 수열에 포함된 숫자들보다 작은 숫자가 나오면 가장 처음 숫자를 교체한다. 

이 아이디어로 문제를 풀었을 때의 한계는 최장 길이를 구할 수는 있지만, 만들어진 배열에 포함된 수열이 실제 그 길이의 최장 증가 부분 수열이 아닐 수 있다는 것이다. 어디까지나 길이를 구하는 것에 의미를 두도록 하자.

위 예시를 이용해서 로직이 어떻게 적용되는지 생각해보자.

첫 숫자 10은 가장 짧은 길이의 증가 부분 수열이다. 배열에 바로 포함시킨다. { 10 }

다음 숫자 20은 10보다 크기 때문에 부분 수열 중 가장 큰 수인 10보다 크다. 바로 뒤에 이어 붙인다. { 10, 20 }

다음 숫자 10은 제일 작은 수인 첫 번째 숫자 10보다 작은 것도 아니고 제일 큰 수인 20보다 큰 것도 아니므로 이분탐색으로 10의 위치를 찾아준다. 제일 첫번째 숫자인 10과 같으므로 이분탐색을 이용해서 교체 가능한 자리를 찾을 경우 첫번째 10의 자리가 리턴될 것이다. 10과 10을 교체한다. 부분 수열의 길이는 유지된다. { 10, 20 }

다음 숫자 30은 부분 수열에서 가장 큰 수인 20보다 크다. 끝에 바로 붙여준다. { 10, 20, 30 }

다음 숫자 20은 부분 수열에서 가장 작은 수인 10과 가장 큰 수인 30 사이에 있는 수이다. 앞에서와 같이 이분 탐색을 이용하여 자리를 찾고 자리를 교체한다. 부분 수열의 길이는 유지된다. { 10, 20, 30 }

마지막 숫자 50은 부분 수열의 가장 큰 수인 30보다 크다. 끝에 바로 붙여준다. { 10, 20, 30, 50 }

이 문제에서는 원래 구하려고 했던 수열 모양 그대로 부분 수열이 구해지긴 했다. 하지만 중간에 2 자리의 10이 5로만 바껴도 부분 수열이 달라졌을 거라는 것은 바로 알 수 있다. 주의해야할 것이다.

실제 문제를 풀면서 이해해보자.

11053번: 가장 긴 증가하는 부분 수열 - Baekjoon Online Judge

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

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int[] A = new int[N];
		for (int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
		}

		int[] lis = new int[N];
		lis[0] = A[0];
		int idx = 1;
		int tmp = 0;
		for (int i = 1; i < N; i++) {
			if (lis[idx - 1] < A[i])
				lis[idx++] = A[i];
			else if (lis[0] > A[i])
				lis[0] = A[i];
			else {
				tmp = Arrays.binarySearch(lis, 0, idx, A[i]);
				lis[tmp < 0 ? -tmp - 1 : tmp] = A[i];
			}
		}
		System.out.println(idx);
	}
}