[알고리즘/Algorithm] LIS, LDS

ZenTechie·2023년 3월 27일

알고리즘

Algorithm

목록 보기

1/4

최장 증가 부분 수열(LIS)?

길이가 n인 배열(리스트)의 일부 원소를 골라서 만든 부분 수열 중, 각 원소의 크기가 이전 원소의 크기보다 크다는 조건을 만족할 때 길이가 가장 긴 부분 수열을 최장 증가 부분 수열(LIS)이다.

예시

arr = [10, 20, 10, 30, 20, 50] 인 경우 최장 증가 부분 수열은 [10,20,30,50] 이다.

어떻게 풀 수 있을까?

1. DP
2. 이분 탐색(이진 탐색)

DP를 사용해보자!

DP를 사용했을 때 전체 코드는 다음과 같다.

d = [0] * n
for i in range(n):
    d[i] = 1
    for j in range(i):
        if a[j] < a[i] and d[j]+1 > d[i]:
            d[i] = d[j]+1

d[i] = 1 : 각 원소는 자기 자신을 부분 수열로 삼을 수 있다. 이때는 길이가 1이다.
for j in range(i) : 현재 원소를 가리키는 인덱스는 i이다. j는 i이전 원소의 인덱스를 의미한다. 즉, 현재 인덱스의 값을 기준으로 이전에 등장한 원소의 값을 살펴본다.
if a[j] < a[i] and d[j] + 1 > d[i]: d[i] = d[j] + 1 : 위에서 i는 현재 원소의 인덱스이고 j는 이전 원소의 인덱스라고 했다. 따라서, 현재 원소가 이전 원소보다 크다면(a[i] > a[j])를 만족하고 이전 원소를 포함하는 부분 수열의 길이보다 현재 원소를 포함하는 부분 수열의 길이가 작으면(d[j] + 1 > d[i])을 만족한다면
d[i] = d[j] + 1 : 위의 조건을 만족한다면, 현재 원소를 포함하는 부분 수열의 길이d[i] = d[j] + 1를 업데이트 한다.

이 코드에서 if문을 다음으로 대체할 수 있다.
if a[j] < a[i]:
	dp[i] = max(dp[i], dp[j] + 1)
위 코드와 동일한 기능을 하는 코드이다.

주의 해야할 점

위 코드의 시간 복잡도를 살펴보면, $O(N^2)$ 이다.
만약, N이 10만 이라면, 10억번의 연산(10초)을 해야 하므로, 시간초과가 발생할 수 있다.
이때는 다른 방법을 살펴볼 필요가 있다.

이진탐색을 사용해보자!

이진탐색을 사용했을 때 전체 코드는 다음과 같다.

LIS = [arr[0]] # 최장 증가 부분 수열을 담는 리스트

# 이진 탐색
def binary_search(el):
	l, r = 0, len(LIS) - 1
    
    # el이 어디에 들어갈지, 인덱스 판단
    while l <= r:
        mid = l + (r - l) // 2
        if LIS[mid] == el:
            return mid
        elif LIS[mid] < el:
            l = mid + 1
        else:
            r = mid - 1
            
    return l

for el in arr:
    if LIS[-1] < el: # LIS의 마지막 원소보다 크다
        LIS.append(el)
        
    # LIS의 마지막 원소보다 작거나 같다.
    # 적절한 인덱스 찾는다.(이진탐색 수행)
    else:
        idx = binary_search(el)
        LIS[idx] = el

binary_search(el) : 현재 원소 el이 LIS 리스트의 어디 위치에 들어갈 수 있는지를 찾는 함수이다.
for el in arr : 원소를 하나씩 순회한다.
if LIS[-1] < el: LIS.append(el) : 현재 원소 el이 LIS의 마지막 원소보다 크다면, 그냥 LIS의 끝에 el을 추가한다.
idx = binary_search(el) : 만약, LIS의 마지막 원소보다 작거나 같다면, el이 들어갈 수 있는 위치를 이진 탐색으로 찾는다.
LIS[idx] = el : 위에서 찾은 인덱스에 현재 원소 el을 넣는다.