가장 긴 증가하는 부분 수열 click
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 찾는 문제이다.
이전에 포스팅을 하긴 했지만, 진정으로 이해하고 포스팅한 것들이 아니라서 굉장히 부실했다. 이번 기회에 보다 자세하게 이분 탐색을 어떻게 사용하는지, Lower Bound는 왜 사용하는지 설명해보려고 한다.
이분 탐색을 이용한 구현을 설명하기 전에 DP로 푸는 방식에 대해서 간단히 짚고 넘어가자.
DP - O(N^2)
DP에는 해당 숫자가 증가하는 부분 수열을 만들 때, 최대 몇 번째 칸에 위치할 수 있는지에 대한 정보를 저장한다.
DP[i]에는 [0, i-1]의 범위에서 value[i] > value[i-1]을 만족하는 숫자들의 DP값의 최댓값 + 1을 저장한다.
위의 그림을 보며 이해해보자.
- 첫 번째 값 0 은 처음으로 등장한 수 임으로, 0번째 칸에 바로 들어갈 수 있다.
- 두 번째 값 7은 0보다 큼으로, DP[1] = DP[0] + 1
- 세 번째 값 5보다 작은 숫자는 0 뿐이다. DP[2] = DP[0] + 1
- 네 번째 값 6보다 작은 숫자들은 0, 5가 있다. 이들의 DP값 중 최댓값은 1이다. 따라서 DP[3] = max(DP[0], DP[2]) + 1
- 4보다 작은 숫자는 0 뿐이다. DP[4] = DP[0] + 1
- 8보다 작은 숫자는 0,7,5,6,4이다. 이들의 DP값들 중 최댓값에 1을 더하자. DP[5] = max(DP[:5]) + 1
- 9보다 작은 숫자는 0,7,5,6,4,8이다. 이들의 DP값들 중 최대값에 1을 더하자. DP[6] = max(DP[:6]) + 1
- 1보다 작은 숫자는 0 뿐이다. DP[7] = DP[0] + 1
- 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번째 위치할 수 있는 숫자들 중 가장 작은 수에 대한 정보를 담는다.
- 0은 첫 번째 수임으로, 바로 0 번째 칸에 넣어준다.
- 7은 0보다 큼으로 0 다음칸에 위치할 수 있다. 1 번째 칸에 넣어준다.
- 5는 0보다는 크고 7보다는 작다. 따라서 1 번째 칸에 위치하게 된다. 그런데 이미 1 번째 칸에는 7이 삽입되어있고, 이는 5보다 크기 때문에 값을 5로 경신해준다.
- 6은 가장 끝에 위치하는 5보다 크기 때문에 5 다음 칸에 위치할 수 있다. 따라서 2 번째 칸에 넣어준다.
- 4는 0보다 크고 5보다 작음으로, 1 번째 칸에 위치할 수 있다. 이미 1번째 칸에 삽입되어 있는 5를 4로 갱신해준다.
- 8은 가장 끝에 위치하는 6보다 크기 때문에 6 다음 칸에 위치할 수 있다. 따라서, 3 번째 칸에 넣어준다.
- 9도 동일한 이유로 4 번째 칸에 넣어준다.
- 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를 활용한 방법에서는 DP[i]를 구하기 위해 0부터 i-1까지 DP를 탐색했다.
이진 탐색을 활용한 방법에서는 i번째 위치할 수 있는 숫자의 최댓값을 저장해 놓았다. 추가하고 싶은 숫자 x를 x보다 작은 숫자들 중 최대값을 가지는 수 다음 칸에 위치시키면 i 번째 위치할 수 있는 숫자의 최대값을 갱신시켜 나갈 수 있다.
다음 주에는 가장 긴 증가하는 부분 수열을 구성하는 숫자들을 알아내는 방법에 대해 포스팅해볼 예정이다.
틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍
[꼭 다시 풀어보기]