[Algorithm] 가장 긴 증가하는 부분 수열(longest increasing subsequence)

가장 긴 증가하는 부분 수열이라는 알고리즘이 있습니다.

 

어떠한 수열의 부분수열에서 증가하는 부분수열 중 가장 긴 부분수열을 의미합니다.

 

다이나믹 프로그래밍 문제를 해결할때 주로 사용됩니다.

 

특정 수열 A가 주어졌을때 가장 긴 증가하는 부분 수열의 길이를 찾는 문제가 있습니다.

 

A = [ 10 20 10 30 20 50 ] 

 

가장 긴 증가하는 부분 수열은 두가지 방법으로 해결할 수 있는데 하나는 시간복잡도 O(N²)로 해결하는 방법이고 다른 하나는 시간복잡도 O(NlogN)으로 해결하는 방법입니다.

 

1. 시간복잡도 O(N²)

 

가장 긴 증가하는 부분수열 문제에서 각 dp[i]값은 주어진 수열의 특정 값을 마지막 원소로 가지는 부분 수열의 최대 길이를 의미합니다. 여기서 특정값은 인덱스 i를 의미하고 A[i]의 값을 마지막으로 가지는 부분수열이어야 합니다.

 

dp[i] : A[i]로 끝나는 가장 긴 증가하는 부분수열의 길이

 

	1	2	3	4	5	6
A[i]	10	20	10	30	20	50
dp[i]	1	2	1	3	2	4

 

dp[i]는 값을 결정할때 이전 값인 dp[0] ~ dp[i-1]까지의 값을 참고한다. 즉 dp[i]는 0 ~ i-1번 인덱스를 가지는 원소 중 값은 A[i]보다 작으면서 가장 큰 dp값을 가지는 원소에 1을 더한것이 됩니다.

 

점화식으로 표현하면 다음과 같습니다.

 

dp[ i ] = max(dp[ i ], dp[ j ]+1), if A[ j ] < A[ i ] (0 <= j <= i-1)

이 알고리즘의 시간복잡도는 O(N²)이 됩니다. dp[i] 값을 계산하기 위해 dp[0] ~ dp[i-1]까지 모두 확인해 줘야 하기 때문입니다.

 

2. 시간복잡도 O(NlogN)

 

1번 방법에서 dp[i]를 갱신하는데 시간복잡도 O(N)이 걸리는데 이를 이진 탐색을 이용하여 O(logN)으로 바꾸는 방법이 있습니다. 그렇게되면 O(N)과 O(lonN)이 되기 때문에 전체 시간복잡도는 O(NlogN)이 됩니다.

 

dp[ i ] : 길이가 i인 증가하는 부분수열 중 끝점의 최솟값

 

동일한 길이의 증가하는 부분수열은 끝점이 작은 것이 효율적입니다.

 

A = [ 10, 20, 30 ], B = [ 10, 20, 25 ]

 

위와 같이 2개의 리스트가 있는 경우 같은 길이의 A, B에서 끝점이 더 작은 B가 유리합니다.

 

다음과 같은 2가지 규칙을 지키면서 dp테이블을 갱신하면 됩니다.

 

1. 새로운 원소가 들어올때 dp[-1]보다 큰 숫자면 dp의 끝에 삽입한다.

2. 그렇지 않은경우라면 오름차순을 깨면 안되기 때문에 dp[n] < A[ i ] <= dp[n+1]을 만족하는 인덱스를 찾아 dp[n+1]에 A[ i ]을 대체한다.

 

A = [ 10 20 10 30 20 50 ]으로 예시를 들겠습니다.

 

dp의 처음에는 아무것도 없으므로 A[0]을 그대로 삽입합니다

	0	1	2	3	4	5
A[i]	10	20	10	30	20	50
dp[i]	10

 

두번째도 dp[-1]보다 큰 수가 다음 인덱스로 찾아오므로 dp의 끝에 삽입해줍니다

	0	1	2	3	4	5
A[i]	10	20	10	30	20	50
dp[i]	10	20

 

세번째에는 dp[-1]보다 작은값이 나왔습니다. 오름차순을 깨지 말아야하므로 들어갈수 있는 인덱스는 0번입니다. 0번에 새롭게 10을 삽입해줍니다.

	0	1	2	3	4	5
A[i]	10	20	10	30	20	50
dp[i]	10	20

 

네번째는 30이 나왔는데 dp[-1]보다 큰 수이므로 dp의 끝에 삽입해줍니다.

	0	1	2	3	4	5
A[i]	10	20	10	30	20	50
dp[i]	10	20	30

 

다섯번째는 20이 왔습니다. 오름차순을 깨면 안되기 때문에 오름차순을 유지할 수 있는 인덱스를 찾아야 합니다. 인덱스 1번에 다섯번째 원소인 20을 삽입합니다.

	0	1	2	3	4	5
A[i]	10	20	10	30	20	50
dp[i]	10	20	30

 

여섯번째는 50입니다. dp[-1]보다 큰 숫자이므로 dp의 끝에 삽입해줍니다.

	0	1	2	3	4	5
A[i]	10	20	10	30	20	50
dp[i]	10	20	30	50

 

이렇게 A[i]를 한바퀴 순환하면서 dp테이블을 채웠습니다. 그 결과 dp는 오름차순을 유지했고 이것이 가장 긴 증가하는 부분수열이 됩니다. 즉, dp테이블의 길이가 가장 긴 증가하는 부분수열의 길이가 됩니다.

 

파이썬은 위와 같은 과정을 bisect 내장함수를 이용하여 쉽게 구현할 수 있습니다. 

 

# O(N log N)
from bisect import bisect_left

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

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

 

O(NlogN) 파이썬 코드 출처 블로그