백준 12015 풀이 (가장 긴 증가하는 부분 수열 2, LIS, 이분탐색)

이 문제는 어떻게 접근해야하나 LIS를 찾다가 거의 정답을 알게되서 거의 꽁으로 푼 문제다.

그러나 이해하는데에 상당히 어려웠기 때문에 내 수준에서 이해한 풀이를 적어보겠다.

 

이전에 LIS문제가 있었는데 그건 다이나믹 프로그래밍으로 풀었던 문제였다.

guccin.tistory.com/38

백준 11053 풀이 (가장 긴 증가하는 부분 수열, LIS)

당시의 풀이 방법은 처음부터 i번째 시점에서 가장 많이 몇번째인지 정하는 방식으로 풀이를 진행한다. 이렇게 설명하려니 상당히 어려운데, 자세한 사항은 상단의 링크를 참조하면 될거 같다. 

그러나 이러한 방식은 상당히 시간이 오래걸리고 시간복잡도가 높다. 그래서 DP형태로는 풀수가 없다.

 

그래서 LIS를 찾아보니 상당히 획기적인 방법이 존재했다.

이 방법은 가능성에 대해서 리스트에 표기하는 방법이다. 말이 어렵긴하다.

 

예를들어 리스트가 [5,6,1,2,...]인 리스트가 존재한다. 우리는 5,6,1,2가 존재하는 것은 알고 있지만 뒤에 무슨 값이 들어있는지는 모르는 상태이다.

그렇다면 현재 만들수 있는 증가수열은 [5,6] 이거나 [1,2]이다.

만약 뒤에 값이 [3,4]라면 [1,2,3,4]가 선택되어야 하고, 뒤에 값이 [7]이라면 [5,6,7]이거나 [1,2,7]일 수 있는것이다.

그러면 우리는 생각할 수 있다. 길이만 구하는 경우라면 [5,6]을 선택하는 것보다 [1,2]를 선택하는게 향후에 나올수 있는 값에 대해서 유연하게 대처가 가능하다.

 

왜냐하면 [5,6,1,2,....] 인 경우 4가 뒤에 있다고 생각해보자.

[5,6]으로 리스트를 만들게 되면 4가 왔을때 4를 추가할 수 없지만, [1,2]로 만들면 4를 추가하여 [1,2,4]를 만들 수 있다.

만약 7이 숨어 있는 경우는 위에서 이야기 했기 때문에 생략한다.

결국 뒤에 올 값에 유연하게 대처하기 위해서는 앞의 값을 낮은 수로 바꿔주는게 더 유리하다는 것이다.

따라서 그림으로 표현하자면 아래와 같다.

(*lowerbound : n값 이상인 값이 처음 나오는 위치)

우선 i가 3일때 리스트가 비어있기 때문에 3을 그대로 삽입한다.

i가 2일때 3과 2를 비교한다. 3보다는 2가 작으므로 3을 대체하는게 가능하다. 따라서 2로 교체한다.

i가 5일때 리스트의 마지막 값인 2보다 크다. 따라서 위에서 2로 대체되기 전에 값이 무엇이든 2보다는 크기 때문에 적어도 부분수열의 길이가 2가 될수 있다는 것을 알 수 있다. 그러므로 5를 리스트에 삽입한다. 그럼 현재까지 적어도 최장 증가 수열의 길이가 2라는 것은 확인할 수 있다.

i가 2일때 리스트의 마지막 값인 5보다 작다. 따라서 들어갈수 있는 lowerbound는 인덱스0의 2값이다. 그러므로 2와 2를 교체한다.(굳이 교체 안해도 되긴함.)

i가 3일때 리스트의 마지막 값인 5보다 작다. 그런데 lowerbound의 위치가 인덱스1인 5값이다. 나중에 어떤 값이 올지 모르기 때문에 5를 3으로 교체해준다. 이렇게 하더라도 최장증가 수열의 길이가 2라는 사실은 변함이 없다.

i가 1일때 리스트의 마지막 값인 3보다 작다. 또한 lowerbound의 위치가 인덱스 0인 2값이다. 따라서 2와 1을 교체해준다.

i가 4일때 리스트의 마지막 값인 3보다 크다. 따라서 4를 삽입한다. 그럼 결과적으로 최장 부분 수열의 길이는 3이 된다.  

흐름에 따라 설명을 하려니 텍스트가 길었다. 

 

짧게 정리하면 다음과 같다.

1. 리스트의 마지막 값과 i값을 비교하여 i가 크면 리스트에 삽입한다.

2. 마지막 값이 작은 경우 lowerbound위치를 찾아서 교체해준다.(훗날 올 수에 대해서 대응하기 위해)

요게 끝이다.

 

거기에 화룡정점으로 lowerbound를 찾을 때 이분탐색을 이용해 주면 python3로 통과가 가능해진다. 

import sys
n = int(input())
t = list(map(int, sys.stdin.readline().split()))
L=[t[0]]
for i in range(1,n):
    if t[i] > L[-1]:
        L.append(t[i])
        continue
    # 이분탐색
    l = 0
    r = len(L)-1
    m = (l+r)//2
    while l < r:
        if L[m] == t[i]:
            break
        elif L[m] > t[i]:
            r = m
        else:
            l = m+1
        m = (l+r)//2
    L[m] = t[i]
print(len(L))