백준 2352. 반도체 설계 (N*logN LIS)

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

2352번: 반도체 설계

 

이 문제를 통해 N*logN 으로 LIS (Longest Increasing Sequence) 를 구하는 방법을 알게 됐다.

보통 LIS 는 수열의 모든 수들을 탐색하며 이전 수열 중 더 작은 값의 LIS 값 + 1을 저장하는 방식으로 N*N의 시간복잡도를 갖는다.

 

그런데 N*logN 의 시간복잡도로 LIS 의 크기를 구하는 방법이 있다.
그건바로 이분탐색을 이용하는 방법이다.

이분탐색을 이용해 현재 탐색하는 숫자가 들어갈 자리를 찾아 넣는것이다.

여기서 LIS의 크기를 구하는 방법이라고 한 이유는, 이 N*logN 방식으로는 N*N 방식과 달리 실제 LIS 수열을 찾을수는 없고, LIS의 크기만 알수 있기 때문이다. 

 

예를들어 수열이 다음과 같다고 하자.

{ 4 2 6 3 1 5 }

 

현재 수: 4 

우선 첫 숫자 4는 그냥 벡터에 넣는다. 

v: {4} 

 

현재 수: 2 

lower_bound로 2를 탐색하면 iterator는 벡터의 4를 가르킬 것이다. 

4를 2로 대체한다.

v: {2} 

 

현재 수: 6 

lower_bound로 6을 탐색하면 iterator는 벡터의 end를 가르킬 것이다.

벡터에 6을 푸쉬한다.

v: {2, 6} 

 

현재 수: 3

lower_bound로 3을 탐색하면 iterator는 벡터의 6를 가르킬 것이다.

6를 3으로 대체한다.

v: {2,3}

 

현재 수: 1

lower_bound로 1을 탐색하면 iterator는 벡터의 2를 가르킬 것이다.

2를 1로 대체한다.

v: {1,3} 

 

현재 수: 5

lower_bound로 5을 탐색하면 iterator는 벡터의 end를 가르킬 것이다.

벡터의 5를 푸쉬한다.

v: {1,3,5} 

 

 

이렇게 LIS의 크기가 v.size() = 3 이라는 것을 알 수 있다. 

이 방법의 아이디어는 쉽게 말하면 벡터에 저장된 숫자들의 간격을 최대한 좁혀서 저장하는 것이라고 생각할수 있다.

예를들어 위에서 3을 넣을때를 생각해보자.

이때 벡터에는 v:{2,6}가 있고, 6이 3으로 대체되어 v:{2,3}이 된다.

순서상 6보다 3이 뒤에 오기 때문에 {2,3,6}은 될수 없다. 

그리고 우리는 가장 긴 증가 수열을 찾기 때문에 3과 6을 비교하면 2와 더 가깝고 큰 숫자인 3이 더 적절하다. 

따라서 6을 빼고 3을 넣는 것이다.

 

이 방법이 LIS의 크기만 구할수 있는 이유

처음에 이 방법이 LIS 수열 내용은 구할수 없고 크기만 구할수 있다고 했는데 이유는, 수열 상 뒤에 오는 숫자가 벡터에서는 앞에 올수 있기 때문이다.

 

예를들어 수열이 다음과 같다

10

20

5

30

위의 N*logN 방식대로 처리해보면 

처음에 10을 벡터에 넣는다. v:{10}

20도 벡터에 푸쉬한다. v{10,20} 

5의 위치를 찾으면 10 자리 이기 때문에 대체한다. v{5,20}

30을 벡터에 푸쉬한다. v{5,20,30}

 

위 수열의 LIS는 {10,20,30}인데 결과는 {5,20,30}이 나왔다.

이유는 5 때문인데, 5를 벡터에 넣을때를 보면 10을 대체한다.

이 방식은 애초에 벡터에 들어있는 원소들의 값 자체가 중요한것이 아니고 원소들간의 관계와 최종적으로 몇개가 들어가 있는지가 중요하기 때문에 수열 자체를 구할수는 없다.