백준/ Gold 2 문제 , 백준 파이썬 12015 , 가장 긴 증가하는 부분 수열 2 , 최장 증가 부분 수열(LIS) 알고리즘

백준/ Gold 2 문제 , 백준 파이썬 12015 , 가장 긴 증가하는 부분 수열 2 , 최장 증가 부분 수열(LIS) 알고리즘

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
여태 배운 dp 문제를 풀어보려고 접근해본건데, 웬걸 이진 탐색의 아이디어로 접근해야 풀리는 문제다.
그리고 그냥도 아닌 최장 증가 부분 수열(LIS)라는 알고리즘을 사용한다. 이건 처음 배운건데 잘 익혀둬야겠다.

 

<문제 출처>

 

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

12015번: 가장 긴 증가하는 부분 수열 2

 

------------------------------------------------------------------------------------------------------------------------------

 

 

 

 

 

https://jainn.tistory.com/90

최장 증가 부분 수열(LIS) 알고리즘

 

 

이 분 블로그에서 최장 증가 부분 수열 (LIS) 에 대해 잘 정리해주셨다.

 

여기에 나온 코드를 그대로 적용 시켜봤다.

 

 

이전 증가 부분 수열을 dp 로 풀었을때는 O(n^2) 의 시간 복잡도로 풀었다.

 

하지만, 이 문제는 N 이 100만 까지의 범위이므로 시간 초과가 나서 풀 수 없다.

 

이럴때 LIS 를 적용한건데 dp 에서 이진 탐색 으로 바꿔 접근하여 푸는 방식이다.

 

이진 탐색은 보통 O(lgn) , 최악인 경우에는 O(n) 의 시간 복잡도를 가진다.

 

 

여기서는 O(nlgn) 의 시간 복잡도로 접근 할 수 있다.

 

이는 dp 보다 빠른 시간복잡도로 접근할 수 있기에 이 문제에 알맞은 접근 방식이다.

 

 

 

 

이걸 여기 문제 예시를 적용 시켜보면

 

 

이렇게 6번의 루프를 돌면서 결과 값을 추출한다.

 

여기서 특이한점은 이 예시로보면 그냥 값들이 차근 차근 들어오기만 한것처럼 보이지만

 

사실 10 20 10 30 20 50 에서 10 20 이 한번씩 교환되었다는 점이다.

 

다만, 원래 있던 10 과 20 자리에 교환된거라 달라지는 것은 없다.

 

 

 

 

무슨 말일까?

 

 

이해되게 다른 예시를 임의대로 출력해 보겠다.

 

입력값은

 

9

 

80 10 50 20 40 90 70 100 120 이다.

 

 

 

출력전 한번 예상해보자.

 

가장 최장 길이는 아마

 

80 10 50 20 40 90 70 100 120

 

이렇게 될 것 같다.

 

그럼 값이 리스트에

 

10 20

 

10 20 40 

 

10 20 40 70

 

 

이런식으로 저장이 바로바로될까?

 

 

 

 

 

체크부분을 확인 해보면 값이 몇번씩 변경되는 점을 알 수 있다.

 

앞전에 들어왔던 수들을 새로운 숫자로 변경하는 식으로 쭉 단계를 이어 나간다.

 

 

코드에서

 

binary[end]=num

 

의 코드가 이러한 역할을 해주고 있다.

 

 

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

 

 

 

import sys 
input=sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
binary=[0]

for num in A:
    if binary[-1] < num:
        binary.append(num)
    else:
        start, end = 0, len(binary)
        
        while start < end: 
            divide=(start+end)//2

            if binary[divide] < num:
                start = divide+1
            else:
                end = divide

        binary[end]=num
  
print(len(binary[1:]))