[백준 12015] 가장 긴 증가하는 부분 수열 2 - 파이썬(Python) - 골드2(이분 탐색 알고리즘)

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

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

---

이 문제에서 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)에 대해 공부하게 되었다.

 

최장 증가 부분 수열 문제는 어떠한 수열이 주어졌을 때, 가장 긴 증가하는 부분 수열을 구해야 하는 것이다.

주로 다이나믹 프로그래밍(O(n^2))으로 풀 수 있지만, 수열의 크기가 커지면 이분 탐색 알고리즘(O(logn))으로 풀어야 한다.

이 문제가 바로 그런 문제였다.

 

이분 탐색 알고리즘으로 최장 증가 부분 수열 문제를 푸는 방법은 다음과 같다.

 

1. 정답이 될 리스트를 정의하고 주어진 수열을 처음부터 탐색한다.
2. 현재값이 리스트의 마지막 값보다 크다면 그대로 삽입한다.
3. 리스트의 마지막 값보다 크지 않다면, 이진 탐색 알고리즘으로 리스트에서 현재값보다 큰 수 중 최솟값의 인덱스를 찾아 그 인덱스값을 현재값으로 바꾼다.
4. 정답 리스트의 길이를 출력한다.

 

단, 이분 탐색 알고리즘으로 풀이하는 방법은 최장 증가 부분 수열의 길이만을 알 수 있을 뿐, 그 수열의 내부 요소들은 알 수 없다.

 

 

 

<< 전체 코드 >>

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))

LIS = [a[0]]


def binary_search(e):
    left, right = 0, len(LIS)-1
    while left <= right:
        mid = (left + right) // 2
        if LIS[mid] == e:
            return mid
        if LIS[mid] < e:
            left = mid + 1
        else:
            right = mid - 1
    return left


for v in a:
    if LIS[-1] < v:
        LIS.append(v)
    else:
        idx = binary_search(v)
        LIS[idx] = v

print(len(LIS))