[Python] 백준 - 11053 가장 긴 증가하는 부분 수열

출처: 백준 온라인 저지
https://www.acmicpc.net/problem/11053

---

못 풀어서 나중에 다시 풀어보려고 했는데, 비슷한 유형의 문제에서 계속 막혔다. 그래서 일단 이 문제를 푸는 방법을 이해한 뒤, 비슷한 문제들을 다시 풀어보기로 했다.

찾아보니 LCS 알고리즘처럼 가장 긴 증가하는 부분 수열을 구하는 알고리즘도 LIS 알고리즘이라는 독립적인 이름을 가진 알고리즘이었다.

LIS 알고리즘

위 영상의 내용을 간단하게 정리하면 아래와 같다.

증가하는 부분수열은 마지막 원소를 제외해도 증가하는 부분수열이다.

증가하는 부분수열에 원소 (n)을 붙이기 위해서는

i) 증가하는 부분수열이 n보다 앞에 있고
ii) 증가하는 부분수열이 n보다 작은 수로 끝나야 한다.

그래서 $D[i]$를 마지막으로 뽑은 수가 $a_i$일 때 가장 긴 부분수열의 길이라고 하면,

$D[i] = {\underset {i{\le}j<i, a_j < a_i} {\max} } = max(D[j] + 1)$

이 성립한다.

i가 증가하는 순서대로 $D[i]$를 쉽게 구할 수 있지만, 이때의 시간 복잡도는 $O(N^2)$가 된다.

더 효율적인 방법은 $a_i$가 증가하는 순서대로 $D[i]$를 구하는 것이다. 이렇게 할 경우 위의 수식에서 $a_j < a_i$ 조건은 자동으로 만족되기 때문에, 수식이 아래와 같이 보다 간단해진다.

$D[i] = {\underset {i{\le}j<i} {\max} } = max(D[j] + 1)$

매번 [1, i - 1] 구간에서 $D[j] + 1$의 최대값을 구하면 된다.
이는 세그먼트 트리와 같은 자료구조를 이용하면 $O(log N)$의 시간 복잡도로 할 수 있으므로, 결국 전체 시간 복잡도가 $O(Nlog N)$이 된다.

위 내용을 바탕으로 코드를 구현해보았다. 세그먼트 트리로도 구현해보고 싶었으나, 세그먼트 트리를 구현하는 방법을 아직 몰라서 일단 $O(N^2)$의 쉬운 방법으로 구현해 보았다.

최종 풀이

from sys import stdin


n = int(stdin.readline())

numbers = [int(x) for x in stdin.readline().split()]
lis = [1] * n

for i in range(1, n):
    for j in range(i):
        if numbers[j] < numbers[i]:
            lis[i] = max(lis[i], lis[j] + 1)

print(max(lis))