[BOJ] 12015 가장 긴 증가하는 부분 수열2_binary search
Date:
가장 긴 증가하는 부분 수열2
문제
수열이 주어졌을 때, 수열의 순서는 변경하지 않고 증가하는 부분 수열의 길이 구하기
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20 10, 30, 20, 50} 이고, 길이는 4이다.
해결 방법
이 문제는 정확한 수열을 구하는 것이 아니라 길이만 구하면 되는 문제이다. 답이 되는 부분 수열은 여러개가 나올 수 있기 때문에 정확한 수열을 구하는건 크게 의미가 없을 것 같다.
부분수열의 길이를 구하기 위해 이진 탐색과 함께 한 가지 트릭을 사용하려고 한다.
수열의 길이를 구하기 위해 하나의 비어있는 list를 만든다. 그리고 수열 A에서 원소를 하나씩 꺼내며 list에 넣을지, 버릴지, 교체할지를 정해줘야한다.
case 1. list 내부의 max값보다 큰 수일 경우 → list 추가
case 2. list 내부의 수와 같을 경우 → 버려짐
case 3. list 내부의 max값보다 작고, 같은 수가 없을 경우 → 교체됨
예시)
A=[10,20,10,20,15,20,30,20,25,30]
list = []
단계 별 list 변화
- 10, case 1 적용 →
list = [10] - 20, case 1 적용 →
list = [10,20] - 10, case 2 적용 →
list = [10,20] - 20, case 2 적용 →
list = [10,20] - 15, case 3 적용 →
list = [10,15] - 20, case 1 적용 →
list = [10,15,20] - 30, case 1 적용 →
list = [10,15,20,30] - 20, case 2 적용 →
list = [10,15,20,30] - 25, case 3 적용 →
list = [10,15,20,25] - 30, case 1 적용 →
list = [10,15,20,25,30](완료)
하지만 여기서 우리는 list가 늘어남에 따라 Case를 비교하는게 점점 어려워 질 것이다. 숫자 하나를 정해서 find로 찾아서 비교할 경우 복잡도가 O(n^2)으로 되어, N = 1,000,000 일 경우 제한 시간 1초 내에 대응이 어렵다.(python에서 O(n^2)복잡도로 제한시간 1초를 뚫으려면 N = 2,000 정도)
우리는 여기서 binary search를 통하여 O(nlong)으로 문제를 풀어보고자 한다.
풀이
이진 탐색은 오름차순, 내림차순으로 정렬된 상태에서만 가능한데, 여기서 정렬된 행렬은 새롭게 만든 dp 행렬이다. 수열 A에서 뽑아낸 원소가 어디로 들어갈지를 탐색할 때 이진 탐색을 사용해보려고 한다.
def f(i): #이진 탐색
low=1
high=len(dp)-1
while low<high:
mid=(low+high)//2
if dp[mid]<i: # 오른쪽 탐색
low=mid+1
elif dp[mid]==i: # case 2 버리기(덮어쓰기)
low=high=mid
else: # 왼쪽 탐색
high=mid
return high
import sys
a=int(sys.stdin.readline())
l=list(map(int,sys.stdin.readline().split()))
dp=[0] #list
for i in l:
if dp[-1]<i: # case 1
dp.append(i)
else : dp[f(i)]=i # case 2,3
print(len(dp)-1)
💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡
댓글