(파이썬) 백준 12015번 "가장 긴 증가하는 부분 수열 2"

---

# 답

bisect_left 라이브러리 없이 풀기

import sys
input = sys.stdin.readline

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

def find_index(x):
    lo = 0
    hi = len(LIS) - 1

    while lo <= hi:
        mi = (lo + hi) // 2
        if LIS[mi] < x:
            lo = mi + 1
        else:
            hi = mi - 1

    return lo

for item in A:
    if LIS[-1] < item:
        LIS.append(item)
    else:
        LIS[find_index(item)] = item

print(len(LIS))

 

bisect_left 라이브러리로 풀기

import sys
from bisect import bisect_left
input = sys.stdin.readline

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

for item in A:
    if LIS[-1] < item:
        LIS.append(item)
    else:
        LIS[bisect_left(LIS, item)] = item

print(len(LIS))

 

 

 

 

---

# 풀이과정

 

LIS 배열에는 Longest Increasing Subsequence, 즉 가장 긴 증가하는 부분 수열을 담을 것입니다. 일단 LIS 배열에 어떤 값들이 담길지 모르므로, 배열 A의 가장 첫 원소를 넣어줍니다.

LIS = [A[0]]

 

이제 배열 A에서 값들을 하나씩 item에 꺼내 담아서 탐색해봅시다.

가장 긴 증가하는 부분 수열(LIS)의 가장 큰 값(LIS[-1])보다 현재 탐색 중인 값(item)이 더 크다면, item은 LIS의 제일 마지막 값에 들어갈 자격이 있습니다. 따라서 item을 LIS에 append 해줍니다.

if LIS[-1] < item:
    LIS.append(item)

 

만일 LIS의 가장 큰 값보다 item이 작거나 같다면, 다음과 같은 명령문이 실행됩니다.

"LIS에서 item보다 크거나 같은 처음으로 등장하는 수를 item으로 바꾼다."

이 명령문은 LIS의 규칙을 해치지 않으면서도 LIS의 요소들을 최대한 작은 값으로 유지시켜줄 수 있습니다.

LIS의 요소들이 최대한 작은 값으로 유지되어야만, 나중에 append할 때 최대한 많은 값들을 append 시켜줄 수 있기 때문입니다.

else:
    LIS[find_index(item)] = item

 

find_index 메서드를 자세히 살펴보겠습니다. find_index(x)는 배열 LIS에서 x보다 크거나 같은 수가 처음으로 등장하는 위치를 반환하는 메서드입니다. 내부가 이분 탐색으로 구현되어 있어 속도가 빠릅니다.

def find_index(x):
    lo = 0
    hi = len(LIS) - 1

    while lo <= hi:
        mi = (lo + hi) // 2
        if LIS[mi] < x:
            lo = mi + 1
        else:
            hi = mi - 1

    return lo

 

find_index 메서드는 사실, bisect_left 라이브러리에서 제공하는 bisect_left 메서드와 정확히 똑같은 역할을 수행하기 때문에 find_index 메서드를 구현하지 않고 풀어도 됩니다.