[백준] 12015번 가장 긴 증가하는 부분 수열 2 - 파이썬

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

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

import sys

n = int(sys.stdin.readline())
num_list = list(map(int,sys.stdin.readline().split()))
lis = [0]
for num in num_list:
    # lis 마지막 값보다 현재 num 값이 크다면 그냥 lis에 넣는다. 왜냐 최장 증가 수열이니까 큰값이면 우선 넣음
    if lis[-1] < num:
        lis.append(num)
    # 만약에 작다면?
    else:
        # 이제 우리는 lis 배열 내에서 모든 값을 뒤져보며 더 긴 수열을 만들수 있는지 찾아볼것이다.
        start = 0
        end = len(lis)
        # 반복문 시작
        while start < end:
            # 중간 값을 정한다.
            mid = (start + end)//2
            # 만약에 lis배열 내의 중간 값이 현재 값보다 작다면
            if lis[mid] <num:
                # 시작 값을 중간 인덱스에서 하나 증가
                start = mid +1
            else:
                # 만약에 num값이 작거나 같다면 끝 값을 mid 해줌
                end = mid
        # 반복문이 끝났다면 lis 배열에 인덱스가 end 인위치에 num을 추가해준다.
        lis[end] = num
print(len(lis)-1)

https://zoozoozoo.tistory.com/422

LIS(Longest Incresing Sequence) - 최장 증가 수열

만약에 작은 값이 들어온다면 추가하지 않고 이분 탐색을 진행하면서 안의 값을 수정해주는 과정을 진행하게 된다.

이분 탐색을 진행할때 이미 안에 같은 값이 있다면 수정을 하지 않고 그 인덱스에 덮어 씌우고 진행을 한다.

끝