LIS(Longest Increasing Subsquence)

• 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분 수열
• 부분 수열의 각 수는 서로 연속할 필요는 없다.
• 예를 들어, [10, 40, 20, 50, 30, 40, 60] 에서
  • 증가하는 부분 수열은 [10,40,50,60], [10,20,50,60], [10,20,30,40,60], [40, 50, 60] 이 있다.
  • 이 때, 가장 긴 증가하는 부분 수열은 [10,20,30,40,60] 이다.
• LIS를 구하는 두 가지 방법에 대해 알아보자.
  • DP
  • 이분탐색

LIS 알고리즘 with DP

DP 테이블 초기화

• DP 테이블의 원소 값은 주어진 수열의 특정 값을 마지막 원소로 가지는 부분 수열의 최대 길이를 의미한다.
• 초기 DP 테이블 값은 모두 자기 자신의 원소를 의미하므로, 1로 초기화해준다.

array = [10,40,20,50,30,40,60]
n = len(array)
dp = [1] * n

점화식 작성

• 이제 수열에서 2번째 값부터 하나씩 확인해서 직전의 값보다 크다면 DP 테이블 값을 업데이트 한다.
  • 점화식으로 나타내면 다음과 같다.

$DP[i] = max(DP[i], DP[j] + 1), if array[j] < array[i] (0≤ j < i)$

for now in range(1,n): # 맨처음엔 무조건 자기자신 하나이기 때문에 두번째부터 시작
    for before in range(now): # 자기 자신의 앞에 있는 것들하고 비교해 나감
        # 증가하는 값이라면
        if array[before] < array[now]: 
            # 이전 길이에 now 1개를 더한 값이 더 길다면 긴 값으로 변경
            if dp[now] < dp[before] + 1: 
                dp[now] = dp[before] + 1
                
# LIS의 길이는 dp에서 가장 큰 값을 의미함
answer = max(dp)

최종 코드

• N 개의 수에 대해 최대 N의 반복문이 실행되므로 시간복잡도는 $O(N^2)$ 이다

def solution(array):
    n = len(array)
    dp = [1] * n 
    for i in range(1,n): 
        for j in range(i): 
            if array[j] < array[i] and dp[i] < dp[j] + 1: 
                    dp[i] = dp[j] + 1
    return max(dp)

LIS 알고리즘 with 이분탐색

• answer 리스트에 증가하는 부분 수열을 담으려고 한다.
• 주어진 수열의 첫 번째 값을 answer 에 담아 초기화한다.
• 수열의 두 번째 값부터 마지막 값까지(target)를 answer 의 마지막 값과 비교하여
  • target 이 더 크다면 answer에 target 을 추가하고,
  • target 이 더 작다면 이분탐색을 통해 answer 값 중 target 보다 크면서 제일 작은 값을 target 으로 갱신한다.

def binary_search(array, target):
    start, end = 0, len(array)-1 # 초기 시작점과 끝점
    while start < end:
        mid = (start + end) // 2 # 중간값

        if array[mid] == target: # 중간값이 타겟과 같다면 중간값의 위치를 반환
            return mid

        # 타겟보다 큰 값 중 가장 작은 값의 위치는 
        # 아래와 같이 바로 전 값보다 크면서 바로 현재 값(중앙)보단 작은 위치이다
        elif array[mid-1] < target < array[mid]: 
            return mid

        # target이 더 작으면 왼쪽 더 탐색
        elif target < array[mid]:
            end = mid - 1

        # target이 더 크면 오른쪽 더 탐색
        else:
            start = mid + 1

    return start # 만약 시작점과 끝점이 같다면 시작점을 반환

def solution(array):
    n = len(array)
    answer = [array[0]] # A 수열의 첫번째 값
    # A 수열의 두번째 값부터 LIS의 마지막 값과 비교
    for i in range(1,n):
        target = array[i]
        if answer[-1] < target: # 타겟이 더 크다면 LIS 에 추가
            answer.append(target)
        else: # 타겟이 더 작다면 이분탐색을 통해 LIS 갱신
            idx = binary_search(answer, target)
            answer[idx] = target

    return len(answer) # 최종 LIS 길이 반환

• bisect 함수를 사용하면 더 간단하게 코드를 작성할 수 있다.

import bisect
    
def solution(array):
    n = len(array)
    answer = [array[0]]
    for i in range(1,n):
        target = array[i]
        if answer[-1] < target:
            answer.append(target)
        else:
            idx = bisect.bisect_left(answer, array[i])
            answer[idx] = target

    return len(answer)

관련 문제

1365번: 꼬인 전깃줄

References

LIS의 길이를 구하는 3가지 알고리즘
[Python] 가장 긴 증가하는 부분 수열 길이를 찾는 LIS 알고리즘
[알고리즘 / Python] 가장 긴 증가하는 부분 수열 (LIS)