최장증가부분수열 - LIS(Longest Increasing Subsequendce)

최장증가 부분수열 - LIS(Longest Increasing Subsequendce)

 

주어진 수열에서 일부 원소를 골라내어 만든 부분 수열 중, 오름차순으로 정렬된 가장 긴 부분수열을 의미한다. 이때 핵심은 부분수열이 반드시 연속될 필요는 없다는 것이다. 즉 몇 개의 원소를 건너뛰어도 해당 연속으로 정렬만 되면 된다는 것이다.

 

예를 들어 {2, 3, 8, 6, 4, 5, 9, 1}의 경우 가장 긴 증가 부분수열은 {2, 3, 4, 5, 9}이 됨

 

특징

• 부분수열의 각 원소는 원래 수열에서 순서를 지켜야 함, 연속적일 필요는 없음
• 오름차순이므로 앞의 원소보다 뒤의 원소가 크거나 같아야 함
• 한 수열에는 여러 개의 최장 증가 부분 수열이 존재할 수 있음

 

구하는 방법

• 동적계획법 - DP
  • 각 인덱스에서 끝나느 LIS의 길이를 저장, 이전 값과 비교하며 최댓값 갱신
  • O(N^2)
• 이분 탐색
  • 마지막 값보다 큰 수가 나오면 추가, 작은 경우에는 이분 탐색으로 적절한 위치를 찾아 기존 값 교체
  • O(NlogN)

 

동적계획법 - DP

 

n = int(input())
num = list(map(int, input().split()))
if n == 1:
    print(num[0])
    exit()
dp= [1] * n

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

 

각 자신의 길이도 1인 부분수열이기에 dp를 1로 초기화하면서 시작된다. 

for 문이 2번 반복되므로 O(N^2)의 시간복잡도를 가지며 첫 번째 for문의 경우 1부터 n-1까지, 두 번째 for문의 경우 0부터 i까지 돌게 된다. 이때 핵심은 j가 i보다 작으면 dp [i]는 기존의 dp [i]와 dp [j]+1을 비교하여 더 큰 값을 저장하게 된다.

 

이는 0에서부터 i까지의 원소의 크기를 비교하며 각 최장 길이를 구하고 이를 dp[i]에 기록을 하는 것이기에 해당 방법으로 구현이 된다.

 

이분 탐색

 

from bisect import bisect_left

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

def lis_lenght(arr):
    lis =[]
    for num in arr:
        idx = bisect_left(lis, num)
        if idx == len(lis):
            lis.append(num)
        else:
            lis[idx] = num
    return lis

print(lis_lenght(num))

 

파이썬에서는 이분 탐색의 경우 bisect 모듈을 사용해서 구현한다. bisect의 bisect_left의 경우 해당 리스트에 num을 넣고 정렬 시 num의 인덱스 번호를 반환한다. 그렇기에 새로운 숫자가 현재 LIS의 마지막 값보다 크면 LIS 추가, 그게 아니면 이분탐색으로 해당 위치로 해당 num을 교체해서 넣어준다.

Return the index where to insert item x in list a, assuming a is sorted.

 

[Python - BackJoon] 가장 큰 증가하는 부분 수열

 

https://www.acmicpc.net/problem/11055

 

풀이

 

풀이는 DP로 진행했으며 이때의 경우 가장 '긴'이 아닌 '큰'으로 '합'을 구하는 문제였다. 그렇기에 해당 dp 배열을 복사하고 기존의 길이의 시작 1이 아닌 정수로 시작하여 각 원소를 더하며 합을 구해준다.

n = int(input())
num = list(map(int, input().split()))
if n == 1:
    print(num[0])
    exit()
dp= num.copy() # 합이기에 길이에서 사용하던 시작 길이 1이 아닌 각 배열에서의 처음 값을 사용

for i in range(1,n):
    for j in range(i):
        if  num[j] < num[i]:
            dp[i]= max(dp[i], dp[j]+num[i]) # 합이기에 원소를 더함
print(max(dp))