가장 긴 증가하는 부분수열2
출처 : 백준 #12015
| 시간 제한 | 메모리 제한 |
|---|---|
| 1초 | 512MB |
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
입출력 예시
예제 입력 1
6
10 20 10 30 20 50
예제 출력 1
4
풀이
생각
- 전형적인 LIS(Longest Increasing Sequences) 문제이다.
- 가장 긴 증가하는 부분 수열과 동일한 문제이나 주어지는 수열 A의 크기의 최댓값이 100만이다.
- 따라서 DP로는 풀 수 없음이 자명하다. (
O(N^2)의 시간 복잡도라서) - 이진탐색으로 이 문제는 접근해야 한다.
풀이 설명
가장 긴 증가하는 부분 수열 (DP 풀이) - O(N^2)
- for 문을 두 개 돌면서 가장 바깥쪽 for 문의 현재 인덱스
i가 있는 위치보다 이전에 있는 인덱스들 (j)을 돈다. - 만약
i에 위치한 수가j에 위치한 수보다 클 경우(오름차순이므로 커야 함)- dp[i] = max(dp[i], dp[j] + 1)
- 위 식의 의미 :
- dp[i]가 클 경우에는 과거 누적된 수가 많다는 말
- dp[j]+1이 클 경우에는 새로운 수가 원래 dp에 추가 된다는 의미
가장 긴 증가하는 부분 수열 (이진탐색 풀이) - O(NlogN)
- 임시로 값을 넣어줄
temp라는 리스트를 하나 만들고 그 안에 수열 첫 번째 값을 넣어준다. - for 문을 통해 수열을 탐색한다. (target은 수열 속의 값)
- 그러는 중에 start = 0, end = len(temp)-1 을 정해놓고 이진탐색을 통해 temp안에서 target 값에 근접한 원소의 인덱스를 찾는다.
- (start, end 둘 중 어느 것을 써도 상관 없음)
- 결국엔 while문을 벗어나는 시점에는 start와 end가 겹치기 때문
- while문을 벗어나면 temp의 마지막 원소가 target보다 작은지 확인한다.
- 만약 target이 크다면, temp를 그대로 유지하고 끝에 붙임으로써 증가하는 부분수열이 완성될 수 있다.
- 만약 target이 작거나 같다면, 끝에 붙인다고 해서 증가하는 부분수열이 될 수는 없으므로, 이전에 이진탐색으로 찾았던 인덱스 (start or end)에 target 값을 넣어준다.
- 이렇게 넣어주더라도 temp의 길이에는 지장이 생기지 않고, 다음에 찾을 수열 값이 지금 넣었던 target과 더욱 가까울 때, 비교를 하더라도 이상이 생기지 않는다. (매우 중요 point!)
- 예를 들어 target을 넣지 않았을 때, temp = [1, 2, 4, 7]이라고 해보자.
- temp의 끝 값이 7이고 새로운 수열의 값이 6, target의 값이 5라고 해보자.
- 그렇게 되면 temp에 target이 대체되지 않았다면, 새로운 수열의 값이 들어갈 자리가 없다.
- 허나 temp[3] = target으로 대체가 된다면 새로운 수열의 값이 들어가게 되어 temp[1, 2, 4, 5, 6]으로 가장 긴 증가하는 부분수열을 완성할 수 있게 된다.
python code(Bottom UP)
# 백준 12015번 가장 긴 증가하는 부분 수열 2(이진탐색)
from sys import stdin
f = stdin.readline
n = int(f())
numbers = list(map(int, f().split()))
def solution(n, arr):
temp = [arr[0]]
for target in arr:
start = 0
end = len(temp)-1
while start < end:
mid = (start+end)//2
if temp[mid] < target:
start = mid + 1
else:
end = mid
if temp[-1] < target:
temp.append(target)
else:
temp[end] = target # idx 값으로 start나 end나 상관 없음
return len(temp)
print(solution(n, numbers))
나는 날마다 모든 면에서 점점 더 나아지고 있다.