백준 14003번: 가장 긴 증가하는 부분 수열 5 (Python)

접근

바로 직전 문제와는 다르게 수열의 크기가 매우 커져서 2중 for문을 순환하는 알고리즘은 사용할 수 없다. 이전에 풀었던 '가장 긴 증가하는 부분 수열 2' 문제는 동일하게 수열의 크기가 매우 커서 dp 수열을 이분탐색하여 갱신하는 알고리즘을 사용하였는데, 이 방법을 발전시켜 이번 문제를 풀 수 있다.

2021.04.05 - [코딩/백준 (Python)] - 백준 12015번: 가장 긴 증가하는 부분 수열 2 (Python)

백준 12015번: 가장 긴 증가하는 부분 수열 2 (Python)

이전에는 이분탐색을 직접 코딩해서 썼지만 같은 역할을 해주는 bisect 모듈이 연산 시간을 줄이는데 도움이 될 것이라고 하여 이번에는 bisect 모듈을 불러와서 사용해보기로 했다.

이번 코드에는 dp와 tmp라는 두개의 리스트를 작성하여 문제를 해결한다. dp[i] 에는 a[i] 가 가장 마지막인 증가하는 부분 수열의 길이가 저장되게 된다. 그리고 tmp에는 이진탐색을 수행할 부분 수열을 저장하게 된다.

1. for 문을 순환하면서 현재 값이 tmp에 저장된 부분 수열의 마지막 값보다 크다면, tmp에 현재 값을 추가하고 가장 긴 부분 수열의 길이를 갱신한다.
2. 그렇지 않다면 현재 값이 tmp 부분 수열의 어느 위치에 있는지 이분탐색으로 찾아 해당 값을 갱신해준다.

코드를 보면 이해하기 좀 더 쉬울 것 같다.

코드

import sys
from bisect import bisect_left

n = int(sys.stdin.readline())
a = [0] + list(map(int, sys.stdin.readline().split()))
dp = [0 for _ in range(n + 1)]
tmp = [-1000000001]
maxVal = 0

for i in range(1, n + 1):
    if tmp[-1] < a[i]:  # tmp에 저장된 부분 수열 마지막 수보다 현재 수가 크다면
        tmp.append(a[i])  # 부분 수열의 마지막에 현재 수를 추가하고
        dp[i] = len(tmp) - 1  # 부분 수열의 길이를 dp에 저장해주고
        maxVal = dp[i]  # 부분 수열의 최대 길이를 갱신해준다.
    else:
        dp[i] = bisect_left(tmp, a[i])  # tmp에서 현재 수가 어디에 위치하는지 찾아서
        tmp[dp[i]] = a[i]  # 해당 위치의 수를 현재 수로 갱신해준다.

print(maxVal)

# 연산이 완료되면 dp[i]에는 a[i]가 마지막인 부분 수열의 최대 길이가 저장되어있다.
tmp2 = []
for i in range(n, 0, -1):
    if dp[i] == maxVal:
        tmp2.append(a[i])
        maxVal -= 1
print(*tmp2[::-1])

더 생각해 볼 것?

처음에는 dp를 하나만 써서 dp[i]에 길이가 i인 부분 수열을 모두 저장하는 식으로 했더니 바로 메모리 초과가 발생하여 위와 같이 수정하게 되었다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!