1. LIS
  2. BOJ 11723 가장 긴 증가하는 부분수열

처음에 알고리즘을 어떻게 짜야하지 고민하다가, 검색해본 결과 아주 유명한 dp문제였다.
LIS, Longest Increasing Subsequence라고도 불린다.

LIS

주어진 행렬 A가 있으면, A[i]를 마지막으로 가지는 가장 긴 증가하는 부분수열의 길이를 D[i]에 할당한다.

즉, A[i]를 찾는 알고리즘은 아래와 같다.

  1. A[0] = 0, D[0] = 0
  2. A[0] ~ A[i-1]중 대응하는 A[i]보다 작으면서(그래야 마지막에 올 수 있으니까), 대응하는 D중 가장 큰 값을 찾는다.
  3. 그 값에 1을 더한 값울 D[i]에 할당한다.
  4. 이렇게 D를 완성하면, D[0]~D[N]중 최댓값을 찾으면 된다.
    O(n^2)이라 느려서, 더 좋은 방법도 존재한다.

BOJ 11723 가장 긴 증가하는 부분수열

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Longest Increasing Subsequence
import sys
N = int(sys.stdin.readline())
A = [0]
A.extend(list(map(int, sys.stdin.readline().split())))
D = [0]*(N+1)

for i in range(1, N+1):
  max_D = 0
  for j in range(0, i):
    if A[j] < A[i]:
      max_D = max(max_D, D[j])
  D[i] = max_D + 1

print(max(D))

참고자료
https://namu.wiki/w/최장 증가 부분 수열