[Python] 12015 - 가장 긴 증가하는 수열 2

[Gold II] 가장 긴 증가하는 부분 수열 2 - 12015 

[문제 링크](https://www.acmicpc.net/problem/12015)

🗝️알고리즘 분류

• 이분 탐색
• 최장 증가 부분 수열 (LIS, Longest Increasing SubSequence)

---

💻문제 정의

주어진 수열에서 가장 긴 증가하는 부분 수열을 찾아 길이를 출력하는 문제이다.

 

💡접근 및 설계

이전에 가장 긴 증가하는 부분 수열 문제를 풀어본 경험이 있다. 이때는 입력의 크기가 작아 DP를 활용하여 &O(N^2)& 크기로 해결할 수 있었다. 하지만 이번 문제는 입력의 크기가 1,000,000 이기에 최소 &O(NlogN)& 의 복잡도로 문제를 해결할 수 있다. 따라서 이분 탐색을 이용해 최장 증가 부분 수열을 찾도록 하였다.

 

✏️알고리즘 풀이

dp = [seq[0]]

for ix in seq:
    if (dp[-1] < ix):
        dp.append(ix)

    else:
        start, end = 0, len(dp)-1
        while (start < end):
            mid = (start + end) // 2

            if (ix > dp[mid]):
                start = mid + 1

            else:
                end = mid
        dp[end] = ix

dp에 먼저 첫 번째 수를 저장한다. 이후 seq의 원소들을 하나 씩 탐색하며 dp의 원소와 비교한다. dp의 가장 큰 원소보다 큰 원소일 경우 dp에 추가한다. 아닐 경우, 이분 탐색을 통해 해당 원소가 dp 내에 들어갈 위치를 찾는다. 이분 탐색의 결과는 ix가 dp에 들어갈 인덱스 번호가 된다.

 

dp = [seq[0]]

for ix in seq:
    if (dp[-1] < ix):
        dp.append(ix)
    else:
        idx = bisect_left(dp, ix)
        dp[idx] = ix

이분 탐색을 통해 인덱스 번호를 반환하는 bisect_left 라이브러리를 이용하여 다음과 같이 작성할 수도 있다.

🗒️제출 코드

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

import sys
input = sys.stdin.readline

A = int(input())
seq = list(map(int, input().split()))

dp = [seq[0]]

for ix in seq:
    if (dp[-1] < ix):
        dp.append(ix)

    else:
        start, end = 0, len(dp)-1
        while (start < end):
            mid = (start + end) // 2

            if (ix > dp[mid]):
                start = mid + 1

            else:
                end = mid
        dp[end] = ix

print(len(dp))

# 12015 가장 긴 증가하는 부분 수열 2 (bisect_left)

from bisect import bisect_left

A = int(input())
seq = list(map(int, input().split()))

dp = [seq[0]]

for ix in seq:
    if (dp[-1] < ix):
        dp.append(ix)
    else:
        idx = bisect_left(dp, ix)
        dp[idx] = ix

print(len(dp))

---