[Math] 최장증가부분수열(LIS) 유형 (with DP/이진탐색)

LIS (Longest Increasing Subsequence) 
: 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거한 부분 수열을 만들 수 있다. 이 때 부분 수열들 중 가장 긴 오름차순 수열을 최장 증가 부분 수열이라 한다.
 
LIS를 해결하는 알고리즘으로는 대표적으로 2가지가 있다.

• DP: O(N^2) 
• 이진탐색:  O(logn)

  이진탐색은 정렬된 배열에서 새 값이 삽입되는 위치를 효율적으로 찾는 방법. 따라서 정렬된 배열에 값을 추가해야 하는 경우에는 이진탐색의 정의에 부합한다. 그러나 LIS에서 이진탐색을 활용할 수 있는거지, DP랑 이진탐색이 서로 연관된 기술이라는 의미는 아니다!

 

  DP는 결과값의 저장, 이진탐색은 정렬을 메인으로 하는 알고리즘이다. LIS의 경우 탐색 정렬을 최장 길이 탐색에 이용한 것!

 

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

1) DP를 이용한 해결

#0 나의 풀이
import sys
n = int(sys.stdin.readline().strip())
temp = list(map(int, sys.stdin.readline().strip().split()))
dp = [1]*n

for i in range(1, n): # temp[2]
    for j in range(0, i): # temp[0], temp[1]
        if temp[j] < temp[i]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))


#1: O(n^2)
import sys
n = int(sys.stdin.readline().strip())
temp = list(map(int, sys.stdin.readline().strip().split()))
dp = [1]*n

for i in range(1, n):
    if temp[i] > max(temp[:i]):
        dp[i] = max(dp) + 1
    else:
        dp[i] = dp[i]

print(max(dp))

 

• 우측 과정을 i보다 작은 모든 j에 대해 반복한다.
• 수열의 특정 요소를 끝으로 하는 Longest Increasing Subsequence는 특정 조합의 부분 수열을 갖는다. 이 때, 각 요소에서 부분수열의 길이를 dp에 저장한다.
  • 'temp = [10, 20, 5, 30]'의 수열이 있을 때, 5를 원소로 갖는 최장수열은 5에서 시작해야하는 길이=1인 수열이다.

 

2) 이진탐색을 이용한 해결

#0: 예제
from bisect import bisect_left

array = [5, 2, 1, 4, 3, 5]
dp = [1]
x = [array[0]]

for i in range(1, len(array)):
    # 현재 값이 x 배열의 마지막 값보다 클 경우
    if array[i] > x[-1]: 
    	# x 배열에 현재 값을 추가해 주고
        x.append(array[i]) 
        # 증가 부분 수열의 길이를 1 증가시킨다.
        dp.append(dp[-1] + 1) 
    # 그렇지 않을 경우
    else: 
    	# 현재 값이 x 배열의 몇 번째 인덱스에 들어갈 수 있는지를 찾아서
        idx = bisect_left(x, array[i]) 
        # x 배열의 idx 위치에 현재 값을 넣어준다
        x[idx] = array[i] 
        
        
#1: O(logn)
import sys
import bisect

# 입력 처리
N = int(sys.stdin.readline().strip())
arr = list(map(int, sys.stdin.readline().split()))

# LIS 배열 (실제 LIS가 아니라 길이만 유지)
lis = []

for num in arr:
    idx = bisect.bisect_left(lis, num)  # 이분 탐색으로 위치 찾기
    if idx == len(lis):  # 가장 큰 값이면 추가
        lis.append(num)
    else:  # 기존 값을 대체하여 유지
        lis[idx] = num

# LIS 배열의 길이가 정답
print(len(lis))

  만약 3번 위치(10)에 10보다 작은 수(5)가 들어온다면? 최장길이수열 리스트인 dp의 1번 위치가 5로 대체된다. list dp 리스트는 매 요소가 끝인 가장 긴 LIS로 갱신되는 것이다.

 

 

2. 11722번 가장 긴 감소하는 부분수열

#0 나의 풀이
from bisect import bisect_left, bisect_right
import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())

arr = list(map(int, sys.stdin.readline().rstrip().split()))
dp = deque([arr[0]]) # 긴 수열 저장
len_arr = [1] # 길이 저장

for i in range(1, n):
    if arr[i] < dp[0]: # arr[i]가 현재 최소보다 작다
        dp.appendleft(arr[i]) # 오름차순
        len_arr.append(len_arr[-1]+1)
        #print(arr[i], idx, dp) 
        
    else: # arr[i]가 현재 최소보다 작다
        idx = bisect_right(dp, arr[i]) 
        dp[idx-1] = arr[i] # 증가수열이 아닌 감소순열이므로, 대체가능 값보다 1 작은 수
        #print(idx, dp, len_arr) #8 2 deque([1, 8])

print(len_arr[-1])


# 1: arr 요소에 -1을 곱하거나, sort(reverse=True)를 해주고 증가하는 수열로 풀이
# 시간 초과가 날 줄 알고 안 썼는데:3c
from bisect import bisect_left

n = int(input())
arr = list(map(lambda x: int(x) * -1, input().split()))

dp = [a[0]]

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

print(len(dp))


#2
import sys
from bisect import bisect_left

N = int(sys.stdin.readline().rstrip())
arr = []

for num in map(int, sys.stdin.readline().split()):
    num *= -1 # 증가하는 순열처럼 처리 
    if not arr or (arr[-1] < num): ## not arr라는 유용한 조건!
        arr.append(num)
        continue # back
    arr[bisect_left(arr, num)] = num
    
sys.stdout.write(str(len(arr)))


#3: DP
import sys
n = int(sys.stdin.readline().strip())

arr = list(map(int, sys.stdin.readline().strip().split()))
cnt = [1 for _ in range(n)]

for i in range(1, n): # 1이 중요
    for j in range(0, i):
        #다음 끝점i는 j보다 작기 바라
        if arr[i] < arr[j]: 
            cnt[i] = max(cnt[i], cnt[j]+1) # cnt[i]는 그저 업뎃되는 값

print(max(cnt))

• DP의 결과는 각 자리의 최대값을 저장함
• 이진탐색의 결과는 가장 큰 수열을 저장(갱신)하고

 

3. 14002번 가장 긴 증가하는 부분 수열4

#0
n = int(input().rstrip())
arr = list(map(int, input().rstrip().split()))
dp = [1]*n

for i in range(1, n):
    for j in range(0, i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j]+1)

max_i = max(dp)
print(max_i)
result = []

for i in range(n-1, -1, -1):
    if dp[i] == max_i :
        result.append(arr[i])
        max_i -= 1

print(*sorted(result))


#1
n = int(input()) # 수열의 길이
a = list(map(int, input().split())) # 수열
dp = [[a[i]] for i in range(n)] # 해당 위치에서 끝나는 단일 요소 초기 수열 설정

for i in range(1, len(a)) :
    for j in range(0, i) :
    	# 증가하는 수열인지 and 최장증가수열인지
        # a[i]보다 작은 a[j]에 대하여, 
        # dp[j]들이 dp[i]보다 길테니, 가장 긴 순열들로 지속 갱신
        # 기존의 dp[j]에 a[i]만 덧붙이므로 결국 가장 긴 dp[j]와 a[i]의 합이 dp[i]가 됨
        if a[j] < a[i] and len(dp[i]) <= len(dp[j]):
            dp[i] = dp[j] + [a[i]] # +=가 아니라 지속 교체

answer = max(dp, key = len) # 길이가 최대인 dp의 요소(key = len)
print(len(answer))
print(* answer)


#2
n = int(input())
a = list(map(int,input().split()))
dp = [1] * n
b = [[a[i]] for i in range(n)]

for i in range(1,n):
    for j in range(i):
        if a[j] < a[i] and dp[i] < dp[j] + 1: 
            dp[i] = dp[j] + 1
            b[i] = b[j]+[a[i]]
            
m = max(dp)

print(m)
print(*b[dp.index(m)]) # 가장 긴 순열이 저장된 b list의 요소 출력

 

 

 

 

 
 
 

 
 
참고문헌
[알고리즘]가장 긴 증가하는 부분수열(LIS) 알고리즘
[백준/Python] 11053 - 가장 긴 증가하는 부분 수열 (LIS)
가장 긴 증가하는 부분 수열의 길이