알고리즘 - 가장 긴 증가하는 부분 수열 문제 (Longest Increasing Subsequence Problem)

가장 긴 증가하는 부분 수열 문제 (Longest Increasing Subsequence, LIS) 는 다이나믹 프로그래밍의 전형적인 문제 중 하나로써, 다이나믹 프로그래밍의 예시로 자주 나오는 문제이다. 비교적 쉬운 O(N^2) 알고리즘과 좀 더 어렵지만 효율적인 O(N log N) 알고리즘이 있다.

 

부분 수열

어떠한 수열에서 일부 숫자들을 지워서 만들어지는 수열을 부분 수열이라고 한다. 자기 자신도 자기 자신에 대한 부분 수열이라고 볼 수 있다.

 

예를 들어 [1, 2, 3, 5, 2, 8] 에 대한 부분 수열은 [1], [1, 3, 5] 등이 있다.

 

증가하는 부분 수열 

부분 수열 중 오름차순으로 정렬되어 있는 부분 수열을 증가하는 부분 수열이라고 한다.

 

예를 들어 [1, 2, 3, 5, 2, 8] 에 대한 증가하는 부분 수열은 [1], [1, 3, 5, 8] 등이 있다.

 

가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열은 당연히 증가하는 부분 수열 중 가장 긴 것을 뜻한다.

 

예를 들어 [1, 2, 3, 5, 2, 8] 에 대한 가장 긴 증가하는 부분 수열은 [1, 2, 3, 5, 8] 이 될 것이다.

 

O(N^2) 알고리즘

dp 테이블의 i번째 원소 (편의상 0번째 원소는 없다고 가정한다) 를 마지막으로 하는 LIS의 길이를 구하면 될 것이다. 즉 1 ~ i - 1 까지의 원소들 중에서 i번째 원소보다 값이 작은 것들 중 가장 큰 dp값을 가지는 원소의 dp값에 1을 더한 값이된다. 점화식은 다음과 같다.

 

dp[i] = max(dp[i], dp[j] + 1) if array[j] < array[i]

 

모든 원소들에 대해 이와 같은 처리를 해준 후, dp 테이블에서 가장 값이 큰 원소가 곧 가장 긴 증가하는 부분 수열의 길이가 될 것이다.

 

def get_lis_length(sequence):
  length = len(sequence)
  # dp table initialize
  dp = [1] * length
  for i in range(length):
    for j in range(i):
      if sequence[i] > sequence[j]:
        dp[i] = max(dp[i], dp[j] + 1)
  return max(dp)

sequence = [1, 2, 3, 5, 8, 2, 9, 10]

print(get_lis_length(sequence)) # [1, 2, 3, 5, 8, 9, 10], answer = 7

 

O(N log N) 알고리즘

O(N log N) 의 시간 복잡도를 가지는 LIS 알고리즘을 보기 전에 lower bound라는 것을 먼저 알아두자. 어떠한 정렬된 배열 arr에서 어떠한 값 val의 lower bound란 arr을 정렬된 상태로 유지하면서 val이 삽입될 수 있는 위치들 중 가장 인덱스가 작은 것이다. 파이썬을 사용한다면 이를 bisect 모듈의 bisect_left로 구할 수 있을 것이다. 다음 코드를 보자.

 

from bisect import bisect_left
def get_lower_bound(array, num):
  return bisect_left(array, num)

array = [1, 4, 6, 8, 9]
print(get_lower_bound(array, 2)) # 1 출력

 

이를 이용하여 O(N log N) 알고리즘을 구현할 수 있다. 기존 O(N^2) 알고리즘은 i번째 원소 직전에 올 수 있는 원소들 중 가장 길게 만들 수 있는 것을 찾을 때 1 ~ i - 1까지의 모든 원소를 순회했다. 그러나 이 과정을 이진 탐색을 통해 O(log N) 시간 안에 수행하게 하여 O(N log N) 의 시간 복잡도를 갖도록 할 수 있다.

 

이 알고리즘은 새로운 리스트인 L이 필요하다. 리스트 L의 원소 L[i] 는 길이가 i인 증가하는 부분 수열을 만들 수 있는 마지막 원소 중 가장 작은 값을 의미한다. 따라서 L의 크기가 곧 현재까지 만들 수 있는 LIS의 길이이며, 따라서 처음에는 빈 리스트로 시작한다.

 

이제 각 원소들을 앞에서부터 순회하며, 다음과 같은 과정을 통해 L을 업데이트 한다.

 

1. L이 비어있거나 현재 L의 마지막 원소보다 i번째 원소가 더 큰 경우
2. 그렇지 않은 경우

1번의 경우엔 L의 뒤에 i번째 원소를 추가하면 될 것이다. 지금까지 만들 수 있는 가장 긴 증가하는 부분 수열의 마지막 원소보다 i번째 원소가 더 크다는 것은 곧 그것이 가장 긴 증가하는 부분 수열이라는 뜻이기 때문이다.

 

2번의 경우에는 L배열에서 i번째 원소의 lower bound를 찾아서 그 자리를 i번째 원소로 바꿔준다.

 

이 과정을 반복한다면 리스트 L은 정렬된 상태가 깨지지 않는다. 따라서 2번의 과정에 이진 탐색을 사용할 수 있다. 위 과정을 마친 후의 L의 길이가 곧 LIS의 길이가 되는 것이다.

 

이를 파이썬으로 구현하면 다음과 같다.

 

# O(N log N)
from bisect import bisect_left

def get_lis_improved(sequence):
  L = [sequence[0]]
  for i in range(1, len(sequence)):
    if L[-1] < sequence[i]:
      L.append(sequence[i])
    else:
      lower_bound = bisect_left(L, sequence[i])
      L[lower_bound] = sequence[i]
  # print(L)
  return len(L)

sequence = [2, 3, 6, 8, 1, 4, 4, 9] # L = [1, 3, 4, 8, 9]
print(get_lis_improved(sequence)) # 5 출력

 

 

출처

seungkwan.tistory.com/8