[백준 12015번][C] 이진 탐색(Binary Search)을 이용한 LIS(최장 증가 수열)

최장 증가 부분 수열, LIS(Longest Increasing Subsequence)는

임의의 수열에서 몇 개의 수를 제거하여 만든 부분수열 중

오름차순으로 정렬된 가장 긴 수열을 말한다

 

---

 

예를 들어 다음 수열이 주어졌다고 하자.

10 20 10 30 20 50

위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있다.

10 10 30 20 (20, 20 제거)

10 30 20 50 (20, 10 제거)

20 10 30 (10, 20, 50 제거)

10 20 50 (10, 30, 20 제거)

...

이들 중 네번째 수열은 오름차순으로 정렬되어 있다. 이를 '증가 부분 수열'이라고 한다.

그리고 이런 증가 부분 수열 중 가장 긴 수열을 '최장 증가 부분 수열 (LIS)'이라 한다.
부분수열 10 20 30 50은 LIS이다.

한 수열에서 여러 개의 LIS가 나올 수도 있다. 예를 들어 수열

5 1 6 2 7 3 8

에서 부분수열

1 2 3 8
5 6 7 8

은 모두 길이가 4인 LIS인 것이다

 

---

 

DP(Dynamic Programming; 동적 계획법)을 이용한 코드는 다음과 같다

snupi.tistory.com/44 

[C code] DP를 이용한 LIS(Longest Increasing Subsequence; 최장 증가 수열)

 

---

 

위 방법은 O(N²)의 시간복잡도를 가지지만, 이진 탐색을 이용하면 O(NlogN)의 시간복잡도로 해결할 수 있다

 

코드는 다음과 같다

 

#include <stdio.h>
#include <stdlib.h>

int *list;

int biSearch(int l, int r, int target)
{
    // list에서 target(==arr[i]) 찾기
    int mid;
    
    while (l < r)
    {
		mid = (l + r) / 2;

		if (list[mid] < target)
			l = mid + 1;
		else
			r = mid;
	}
	
	//return idx값
	return r; //or l
}

int main()
{
    int N, inp, listIdx=0;
    scanf("%d", &N);
    
    list = (int *)malloc(sizeof(int) * N);

    for(int i=0 ; i<N ; i++)
    {
        scanf("%d", &inp);

        if(i==0) list[i] = inp;

        if(inp > list[listIdx])
            list[++listIdx] = inp;
        else
            list[biSearch(0, listIdx, inp)] = inp;
    }

    return 0;
}

 

2, 1, 3, 5, 4 의 수열을 예로 들어보자

 

i = 0)

list[0] = 2

 

i = 1)

1 < list[0] (== 2) 이므로 이분 탐색으로 들어갈 자리를 찾는다

biSearch() 함수로 0을 리턴하므로

-> list[0] = 1

 

i = 2)

3 > list[0] (== 1) 이므로 맨 뒤에 새롭게 넣는다

-> list[1] = 3

 

i = 3)

5 > list[1] (== 3)

-> list[2] = 5

 

i = 4)

4 < list[2] (== 5) 이므로 이분 탐색으로 들어갈 자리를 찾는다

biSearch() 함수로 2을 리턴하므로

-> list[2] = 4

 

따라서 LIS는 1, 3, 4 로 길이는 3이 된다

 

-chanhuiseok.github.io/posts/algo-49/

-나무위키