[백준/Python] 🥇 12015번 가장 긴 증가하는 부분 수열 2

문제

수열 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~5까지 있는 것을 보면 시리즈물인가

다음 단계로 갈수록 이것저것 고려하거나, 다른 알고리즘으로 풀어야 하는 것 같다.

이미 단계별로 풀어보기에서 이분탐색 알고리즘인 것을 알았지만.....

아직 경험치가 부족한거지? 지능이 낮은건 아니지???

 

 

 

문제의 포인트 !

1. 현재 target을 제외하고, 그 전 배열까지는 정렬된 수열이다. target이 삽입 정렬과 유사하게 들어간다고 생각하자

2. 이분탐색으로 target이 삽입된 위치를 탐색한다. 여기서 n개의 원소에 대한 탐색 시간복잡도를 log n으로 줄여낼 수 있다.

    11053번 문제의 경우 n개의 원소에 대해서 각각 n번 탐색(배열 처음부터 idx-1까지 탐색)하기 때문에 O(n^2)

 

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

# 이분탐색 : 수가 들어갈 수 있는 위치 탐색
def binary_search(target):
    # print("==================")
    # print("target: " + str(target))
    if len(sorted_arr) == 0: # 비어있는 수열이라면 아묻따 추가
        sorted_arr.append(target)
        return
    
    if sorted_arr[-1] < target:
        sorted_arr.append(target) # 현재 숫자가 정렬된 수열의 가장 큰 값보다 크면 끝에 추가
        return
    
    # sorted_arr 수열에서 현재 숫자가 들어갈 자리에 나보다 큰 수가 있다면 나로 덮어쓰기
    # 1 2 4 3 의 경우 1 2 3으로 만들어 짐
    left = 0
    right = len(sorted_arr)-1
    while(left < right):
        mid = (left+right)//2
        # print("left: " + str(left) + ", right: " + str(right) + ", mid: " + str(mid))
        if sorted_arr[mid] < target: # 찾는 수가 mid 위치의 수보다 크다면 범위를 우측으로 조정
            left = mid+1
        else:                        # 찾는 수가 mid 위치의 수보다 작거나 같다면 범위를 좌측으로 조정
            right = mid
    sorted_arr[right] = target
        
sorted_arr = []
for num in arr:
    binary_search(num)
# print(sorted_arr)
print(len(sorted_arr))

 

 

 

느낀점

 

인고와 고통의 시간을 지나.............

처음에는 while문으로 안 돌려줘서 target이 들어갈 위치를 제대로 이분탐색하지 못했다...

 

지나고 나면 항상 간단한 이분탐색 원리...

target이 mid 위치보다 크면 탐색 범위를 오른쪽으로 조정 ( left ~ right     →     mid+1 ~ right )

target이 mid 위치보다 작으면 탐색 범위를 좌측으로 조정 ( left ~ right     →     left ~ mid 혹은 left ~ mid-1 )

 

문제따라 while문 조건 설정이나 (left<=right로 갈지, left<right로 갈지)

탐색 범위를 mid로 할지 mid-1 혹은 mid+1로 할지... 많은 예제로 시뮬레이션 돌려서 정해보도록 하자.