[DP] 가장 긴 증가하는 부분 수열 (LIS)

가장 긴 증가하는 부분 수열

• 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)은 대표적인 다이나믹 프로그래밍 문제이다.
• {10, 20, 10, 30, 20, 50} 과 같은 수열이 주어졌을 때, 수가 점점 증가하는 수열의 가장 긴 길이를 구한다.

 

1) Dynamic Programming 풀이법 - O(N^2)

• 파라미터 설명:
  • n = 수열의 길이
  • arr = 수열을 이루는 숫자가 담긴 배열
  • d = arr[i]를 마지막 원소로 가질 때 LIS의 길이

1. d[i] 값을 1로 초기화한다.
2. 현재 위치(i)보다 이전에 위치한 원소(j)가 작은지 확인한다. (i는 기준이 되는 인덱스, j는 i보다 작은 인덱스)
3. arr[i] > arr[j] 이면, 현재 위치 숫자 중 d의 최댓값을 구하고, 그 길이에 1을 더한다.

백준 11053번 - 가장 긴 증가하는 부분 수열

11053번: 가장 긴 증가하는 부분 수열

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

d = [1] * n
for i in range(n):  # 기준이 되는 인덱스
    for j in range(i):  # 이전에 있는 숫자들
        # 현재 위치(i)보다 이전에 있는 원소(j)가 작은지 확인
        if arr[i] > arr[j]:
            d[i] = max(d[i], d[j]+1)

print(max(d))

 

2) Binary Search 풀이법 - O(NlogN)

d[i]를 구할 때 d[0] ~ d[i-1]의 최댓값을 미리 알고 있다면 이전의 모든 수를 확인할 필요가 없다.

→ N개의 원소에 대해 이진 탐색을 수행했기 때문에 시간복잡도는 O(NlogN)이다.

1. d를 수열의 첫 번째 요소인 arr[0]으로 초기화한다.
2. 현재 위치(i)가 이전 위치의 원소들보다 크면 d에 추가한다.
3. 현재 위치(i)가 이전 위치보다 작거나 같으면, bisect_left()로 이전 위치의 원소 중 가장 큰 원소의 idx값을 구한다. d[idx] = arr[i]로 바꾼다.

백준 12015번 - 가장 긴 증가하는 부분 수열 2

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

from bisect import bisect_left

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

d = [arr[0]]
for i in range(n):
    if arr[i] > d[-1]:
        d.append(arr[i])
    else:
        idx = bisect_left(d, arr[i])
        d[idx] = arr[i]

print(len(d))