[백준/Python] 12015 가장 긴 증가하는 부분 수열 2

문제

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

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

---

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

---

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

---

풀이

또 다시 돌아 온 가장 긴 부분 수열(LIS) 문제
근데 이번엔 동적 계획법 카테고리가 아니라 이분탐색 카테고리에 있는 LIS 문제다.

동적 계획법은 참 해도해도 익숙해지지 않았었는데 얄궂게도 이 문제를 맞닥뜨리니 제일 먼저 생각나는 것도 동적 계획법이었다.
당연히 동적 계획법을 사용하면 안 될 걸 알면서도 한 번 코드를 짜 본다.

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


n = len(sequence)
dp = [1] * n 
    
for i in range(1, n):
    for j in range(i):
        if sequence[i] > sequence[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

역시나 실패, 사유는 시간초과
O(N2)인 lis 알고리즘에 106까지인 N을 넣으니 당연하게 될 리가 없었다.

그러면 어떻게 해야할까?
일단 카테고리 대로 이분탐색을 활용해보기로 했다.

이 문제로 돌아와서 만약에 내가 주어진 수열을 보고 LIS를 구해야한다면 어떤 과정을 통해 구하게 될까 생각을 해봤다.

예를들어

[5, 3, 10, 20, 4, 6, 7, 30, 21, 25]

이런 수열이 있다고 생각을 해보자

일단 처음엔 수열의 첫 번째 요소 즉 5부터 시작하게 될것이다.

그리고 수열을 차례대로 훑기 시작하는데 다음 수인 3을 보면 '아 5보다는 3으로 시작하는 게 더 큰 수열을 만들기에 유리하겠구나'생각하고 머리속의 lis를 3부터 다시 시작한다.

뒤이어 10과 20까지는 쭉쭉 가다가 4를 본 순간 생각이 달라진다.
'3다음 10, 20보다는 4가 들어오는 게 맞겠구나' 그럼 10과 20 대신에 4부터 6, 7까지 가장 긴 수열을 갱신하게 된다.

그리고 이어서 30을 붙이려다 21과 25를 보고 3, 4, 6, 7에 21, 25를 더한
[3, 4, 6, 7, 21, 25]를 최종적인 답으로 결정하게 될 것이다.

이런 과정을 규칙성을 가질 수 있도록 정리를 해보자.

1. 원래 수열의 첫 번째 요소를 LIS의 첫 번째 요소로 담는다
   => lis = [5]
2. 이어서 원래 수열의 탐색을 하며 LIS에 담겨 있는 요소보다 작다면 그 요소를 대체한다
   => lis = [3]
3. 원래 수열의 요소가 LIS에 담겨 있는 요소보다 크다면 LIS의 새로운 요소로 추가한다
   => lis = [3, 10, 20]
4. 원래 수열의 요소가 LIS에 담겨 있는 요소 중 A보다는 큰데 그 다음 요소 B보다는 작다면 B를 탐색한 원래 수열의 요소로 대체한다
   => lis = [3, 4, 20]

이런 과정을 끝까지 진행하게 되면
[3, 4, 20] -> [3, 4, 6] -> [3, 4, 6, 7] -> [3, 4, 6, 7, 30] -> [3, 4, 6, 7, 21] -> [3, 4, 6, 7, 21, 25]가 되어 결과적으로 답을 도출할 수 있게 된다.

그리고 과정 중 제일 중요한 LIS를 탐색하는 부분을 이분탐색으로 구현하면 된다는 결론에 다다랐다.

import sys

input = sys.stdin.readline

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

lis = []

for num in sequence:
    left = 0
    right = len(lis)

    while left < right:
        mid = (left + right) // 2

        if lis[mid] < num:
            left = mid +1
        else:
            right = mid

    if left < len(lis):
        lis[left] = num
    else:
        lis.append(num)

print(len(lis))

입력받은sequence의 요소 num과 새로 만든 lis 리스트의 요소들을 이분 탐색을 통해 비교한다.
이분탐색은 어려울 것 없는 스탠다드한 방식이고 left가 len(lis)보다 작다면 즉 num보다 큰 lis의 요소가 존재한다면 그 중 가장 작은 요소를 num으로 대체하고 아니라면 lis에 num을 추가해준다 그리고 마지막으로 len(lis)를 출력해준다.

이렇게 진행하면 시간복잡도가 O(NlogN)으로 기존의 동적 계획법보다 상대적으로 빠르게 실행을 마칠 수 있다.