[Algo] LIS (최장 증가 부분 수열)

LIS란?

최장 증가 부분 수열을 의미한다.

어떠한 수열이 주어졌을 때, 그 중 몇 개의 수를 골라내서 만든 수열을 '부분 수열'이라고 한며, 그 몇 개의 수가 오름차순으로 증가하는 형태일 때 이를 '증가하는 부분 수열'이라고 한다. 증가하는 부분 수열 중 길이가 가장 긴 부분수열이 '최장 증가 부분 수열'이다.

 

예를 들어, [10 20 10 30 40 50]수열이 있을 때,  [10 20 10], [20 30] [20 10 40 50] 등 여러 부분 수열을 만들 수 있다.

그 중 최장 증가 부분 수열은 [10 20 30 40 50] 이다.

 

Solving LIS problem

- LIS 길이 구하기

수열의 첫 번째 숫자부터 순회하면서, 이 숫자를 포함했을 때 오름차순 형태를 유지할 수 있는지, 다시 말해 부분 수열의 이전에 있는 숫자들보다 큰지를 확인하고 더 클 경우에만 부분 수열에 포함시킨다. 이 동작을 수열의 마지막 숫자까지 반복하면 최장 증가 부분 수열을 구할 수 있다.

 

LIS 구하는 문제에서 가장 포인트가 되는 부분은

1. 부분 수열에 있는 숫자보다 큰 경우에만 부분 수열의 마지막에 추가한다.
2. 부분 수열의 마지막 숫자를 가능한 작은 값으로 유지한다.

이 두 가지이다.

예를 들어, [10 40 20 30 50] 수열에서 LIS는 [10 20 30 50]이다. 만약 20 대신 앞에 있는 40이 부분 수열에 포함된다면 30은 넣을 수 없게 된다. 부분 수열의 마지막 값을 최대한 작게 유지하면 뒤에 더 많은 숫자를 넣을 수 있다.

 

따라서 부분 수열의 마지막 숫자보다 클 경우 부분수열에 포함시키고, 부분 수열의 마지막 바로 앞에 있는 숫자보다 크거나 같고 부분 수열 마지막 숫자보다 작을 경우에는 부분수열의 마지막 숫자를 바꿔주면 된다고 생각했다 (아래는 pseudo code)

INIT ARRAY sub_seq
FOR each number of the sequence
	IF the last of sub_seq < number THEN
    	INSERT number INTO ARRAY sub_seq
    ELSE IF just before of the last of sub_seq < number < the last of sub_seq THEN
    	SET the last of sub_seq TO number
    END IF
END FOR    	

PRINT sub_seq

 

하지만.. 위와 같은 방식은 문제가 있다.

예를 들어 수열 [10 20 30 5 15 20 30 40] 이 주어졌을 때, 실제 LIS는 [5 15 20 30 40] 이지만 위 방식으로 풀면 [10 20 30] 이 된다. 5에 대해 부분수열에 있는 숫자와 비교할 때, 부분 수열의 가장 마지막 두 개의 숫자만을 비교하기 때문에 5는 부분 수열에 포함되지 않는다. 따라서 당연하게도 15와 20 30도 포함되지 않는다.

부분 수열의 모든 숫자와 비교를 해야한다!! 하지만 이중 반복문을 사용하면 O(N^2)으로 더 효율적인 방법이 있지 않을까? 고민한 결과..!

 

구글에 도움을 받아 lower_bound를 이용하면 된다는 것을 알게 되었다!!

탐색 방법 중 하나인 lower_bound는 원하는 값 k 이상이 처음 나오는 위치를 찾는다. lower_bound를 이용해 부분 수열에서 현재 숫자보다 크거나 같은 가장 첫 번째 숫자의 위치를 찾아 그 숫자를 현재 숫자로 바꾼다.

 

[10 20 30 5 15 20 30 40]이 주어졌을 때,

sub_seq = [10]                         //  첫 번재 숫자 → 비교 없이 추가

sub_seq = [10 20]                   //  10 < 20 → 부분 수열에 추가

sub_seq = [10 20 30]             //  20 < 30  → 부분 수열에 추가   

sub_seq = [5 20 30]               //  30 > 5 → lower_bound로 위치 찾아서 현재 숫자 5로 바꿈

sub_seq = [5 15 30]                //  30 > 15 →  lower_bound로 위치 찾아서 현재 숫자 15로 바꿈

sub_seq = [5 15 20]                //  30 > 20 → lower_bound로 위치 찾아서 현재 숫자 20으로 바꿈

sub_seq = [5 15 20 30]          //  20 < 30 → 부분 수열에 추가

sub_seq = [5 15 20 30 40]    //  30 < 40 → 부분 수열에 추가

sub_seq의 길이인 5가 LIS의 길이로 답이 된다.

 

!! 하지만 이 방법은 LIS의 길이는 구할 수 있지만 LIS 자체를 구할 수는 없다. !!

lower_bound로 현재 숫자가 부분 수열에 포함된다면 어디에 들어가야 하는지 찾아서 그 위치에 넣어주지만, 기존 수열에서의 순서와 상관없이 넣기 때문이다. 

[10 20 30 5] 가 주어졌을 때, 최종적으로 sub_seq = [5 20 30] 으로 실제 LIS인 [10 20 30] 과는 길이는 같지만 다른 수열이 나오며, [5 20 30]은 더 뒤에 있는 5가 20 30 보다 앞에 있으므로 올바른 부분 수열도 아니다. 

 

 

- LIS 구하기

길이 뿐만 아니라 LIS 자체를 구하기 위해서는 추가적으로 수열의 각 숫자가 부분 수열에 추가되는 위치가 필요하다. 이 위치 정보를 기준으로 뒤에서 부터 위치 정보가 n(LIS 길이), n-1, n-2, ..., 1 에 해당하는 숫자로 수열을 만들면 LIS가 된다.

 

예를 들어 [10 20 30 5] 수열의 부분 수열에 추가되는 위치는 [1 2 3 1] 이다.

뒤에서부터 가장 먼저 나오는 3(30), 3보다 왼쪽에 있으면서 가장 먼저 나오는 2(20), 2보다 왼쪽에 있으면서 가장 먼저 나오는 1(10)으로 부분 수열을 만들면 [10 20 30]으로 LIS를 구할 수 있다. 

[10 20 30 5 15 20 30 40] 수열을 예로 들면, 위치 정보는 [1 2 3 1 2 3 4 5] 이다.

위와 같이 구해보면 5(40), 4(30), 3(20), 2(15), 1(5)로 [5 15 20 30 40] LIS를 구할 수 있다.