Python-11053-가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열 click

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 찾는 문제이다.

 

• 가장 긴 증가하는 부분 수열 포스팅

• 가장 긴 증가하는 부분 수열 3 포스팅

 

이전에 포스팅을 하긴 했지만, 진정으로 이해하고 포스팅한 것들이 아니라서 굉장히 부실했다. 이번 기회에 보다 자세하게 이분 탐색을 어떻게 사용하는지, Lower Bound는 왜 사용하는지 설명해보려고 한다.

 

이분 탐색을 이용한 구현을 설명하기 전에 DP로 푸는 방식에 대해서 간단히 짚고 넘어가자.

 

 

 

DP - O(N^2)

 

가장 긴 증가하는 부분수열 - DP

DP에는 해당 숫자가 증가하는 부분 수열을 만들 때, 최대 몇 번째 칸에 위치할 수 있는지에 대한 정보를 저장한다.

DP[i]에는 [0, i-1]의 범위에서 value[i] > value[i-1]을 만족하는 숫자들의 DP값의 최댓값 + 1을 저장한다.

 

위의 그림을 보며 이해해보자.

 

1. 첫 번째 값 0 은 처음으로 등장한 수 임으로, 0번째 칸에 바로 들어갈 수 있다.
2. 두 번째 값 7은 0보다 큼으로, DP[1] = DP[0] + 1 
3. 세 번째 값 5보다 작은 숫자는 0 뿐이다. DP[2] = DP[0] + 1
4. 네 번째 값 6보다 작은 숫자들은 0, 5가 있다. 이들의 DP값 중 최댓값은 1이다. 따라서 DP[3] = max(DP[0], DP[2]) + 1
5. 4보다 작은 숫자는 0 뿐이다. DP[4] = DP[0] + 1
6. 8보다 작은 숫자는 0,7,5,6,4이다. 이들의 DP값들 중 최댓값에 1을 더하자. DP[5] = max(DP[:5]) + 1
7. 9보다 작은 숫자는 0,7,5,6,4,8이다. 이들의 DP값들 중 최대값에 1을 더하자. DP[6] = max(DP[:6]) + 1
8. 1보다 작은 숫자는 0 뿐이다. DP[7] = DP[0] + 1
9. DP에 저장된 값들의 '최대값 + 1'(0번 index부터 시작했으므로)이 가장 긴 증가하는 부분 수열의 길이가 된다.

그림의 왼쪽에 빨간색 글씨로 쓰여진 숫자가 value[i] > value[i-1]을 만족하는 숫자들의 DP값의 최댓값이다. 이 숫자에 1을 더한 숫자가 DP[i]의 값으로 들어간다.

그림의 왼쪽에 빨간색으로 칠해진 칸은 DP[i]를 찾기 위해서 탐색해야 하는 칸들의 범위이다.

따라서 DP를 사용한 방법은 시간복잡도가 O(N^2)이 된다.

 

Code

import sys
n=int(input())
value=list(map(int,sys.stdin.readline().split()))

dp=list(0 for _ in range(n))
dp[0]=1

for i in range(1,n):
    for j in range(i):
    	#value[i]보다 값이 작은 숫자들의 dp값들 중 최대값을 dp[i]에 저장
        if value[j]<value[i] and dp[j]>dp[i]:
            dp[i]=dp[j]
    dp[i]+=1

print(max(dp))

 

 

 

 

이분 탐색 활용 - O(NlogN)

 

 

DP를 활용한 방법에서 DP[i]를 구하기 위해 0부터 i-1까지 DP를 탐색해야 했다.

어떻게 이분 탐색을 활용해 시간복잡도를 줄일 수 있는지 알아보자.

 

가장 긴 증가하는 부분수열의 x번째 칸에 위치할 수 있는 숫자들 중 가장 작은 수를 알고 있으면, 이분 탐색을 활용해 value[i]는 몇 번째 칸에 위치할 수 있는지 찾아낼 수 있다.

 

이 말이 무슨 뜻인지 그림을 보며 이해해보자. 

 

 

가장 긴 증가하는 부분수열 - 이분 탐색

 

이해를 돕기 위해 DP에서 활용한 표와 함께 그려놓았다.

왼쪽 표는 위에서 수행했던 DP 과정을 담은 표이다. 오른쪽 표에는 i번째 위치할 수 있는 숫자들 중 가장 작은 수에 대한 정보를 담는다. 

 

1. 0은 첫 번째 수임으로, 바로 0 번째 칸에 넣어준다.
2. 7은 0보다 큼으로 0 다음칸에 위치할 수 있다. 1 번째 칸에 넣어준다.
3. 5는 0보다는 크고 7보다는 작다. 따라서 1 번째 칸에 위치하게 된다. 그런데 이미 1 번째 칸에는 7이 삽입되어있고, 이는 5보다 크기 때문에 값을 5로 경신해준다.
4. 6은 가장 끝에 위치하는 5보다 크기 때문에 5 다음 칸에 위치할 수 있다. 따라서 2 번째 칸에 넣어준다.
5. 4는 0보다 크고 5보다 작음으로, 1 번째 칸에 위치할 수 있다. 이미 1번째 칸에 삽입되어 있는 5를 4로 갱신해준다.
6. 8은 가장 끝에 위치하는 6보다 크기 때문에 6 다음 칸에 위치할 수 있다. 따라서, 3 번째 칸에 넣어준다.
7. 9도 동일한 이유로 4 번째 칸에 넣어준다.
8. 1은 0보다 크고 4보다 작음으로, 1 번째 칸에 위치할 수 있다. 이미 1번째 칸에 삽입되어 있는 4를 1로 갱신해준다.

오른쪽 표에 저장된 숫자의 길이가 가장 긴 증가하는 부분 수열의 길이가 된다.

설명을 위해 DP표를 함께 활용했지만, 바로 이진 탐색을 활용해 숫자를 위치시킬 수 있다.

숫자 x는 x 보다 작은 값을 가지는 숫자들 중 최댓값의 다음 칸에 삽입된다.

 

이때, 저장되어있는 숫자와 가장 긴 증가하는 부분 수열을 구성하는 숫자는 다르다는 점에 유의하자!

 

Code

import sys
read=sys.stdin.readline

#이진 탐색
#n보다 작은 숫자들 중 최대값의 다음 칸에 위치시킨다.
def lower_bound(n):
    l,r = 0,answer_len
    while l<=r:
        mid = (l+r)//2
        if answer[mid] < n:
            l = mid + 1
        else:
            r = mid - 1
            save = mid
    answer[save] = n

N=int(read())
num=list(map(int,read().split()))

answer = [num[0]]

answer_len=1
for n in num[1:]:
    if n > answer[-1]: 
        answer.append(n)
        answer_len += 1
    elif n < answer[-1]: 
    	lower_bound(n)

print(len(answer))

 

DP vs 이분 탐색(Lower Bound)

가장 긴 증가하는 부분수열 - DP vs Lower Bound

 

DP를 활용한 방법에서는 DP[i]를 구하기 위해 0부터 i-1까지 DP를 탐색했다.

 

이진 탐색을 활용한 방법에서는 i번째 위치할 수 있는 숫자의 최댓값을 저장해 놓았다. 추가하고 싶은 숫자 x를 x보다 작은 숫자들 중 최대값을 가지는 수 다음 칸에 위치시키면 i 번째 위치할 수 있는 숫자의 최대값을 갱신시켜 나갈 수 있다. 

 

다음 주에는 가장 긴 증가하는 부분 수열을 구성하는 숫자들을 알아내는 방법에 대해 포스팅해볼 예정이다.

 

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]