백준 12015번 가장 긴 증가하는 부분 수열 2

https://www.acmicpc.net/problem/12015
실패이유: 구현실패

def bin_search(nums: list, target: int):    # target이 들어가야 하는 인덱스를 반환
    start = 0
    end = len(nums) - 1

    while start <= end:
        mid = (end + start) // 2
        if nums[mid] < target:
            start = mid + 1
        elif nums[mid] > target:
            end = mid - 1
        else:
            return mid     # target 을 찾은 경우

    return start        # target 이 없는 경우


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

d = []          # 가장 긴 부분 수열 개수를 구하기 위한 리스트

for num in numbers:
    index = bin_search(d, num)      # 숫자가 들어갈 인덱스를 찾는다.
    if index == len(d):                 # 만약 숫자가 리스트에서 가장 큰 값이면 인덱스는 리스트의 길이와 같다.
        d.append(num)                       # 이 경우, 리스트에 숫자를 추가한다.
    else:
        d[index] = num                  # 만약 숫자가 리스트에서 가장 큰 값이 아니면, 인덱스는 리스트 내부의 요소를 가리킨다.
                                            # 이 경우, 해당 인덱스의 요소를 숫자로 변경한다.

print(len(d))   # 리스트의 길이가 가장 긴 부분 수열 개수이다.
                # 리스트가 가장 긴 부분 수열을 의미하진 않는다.

• 주어진 숫자의 범위가 1 ≤ N ≤ 1,000,000 이므로, O(N^2) 으로는 풀 수 없다.
  
  
• bin_search(nums: list, target: int)
  • 이진 탐색 메서드
  • nums 리스트 내에서 target 이 몇 번째 인덱스에 위치해야 하는지를 반환한다.
  • ex) nums = [1, 3, 4, 5]
    - target = 4 인 경우 반환값은 2
    - target = 2 인 경우 반환값은 1
    
    
• d 는 가장 긴 부분 수열 개수를 구하기 위한 리스트이다.
  • 해당 리스트는 오름차순으로 정렬된 상태를 유지한다.
    • 따라서 이진 검색 bin_search 를 사용하여 num 이 위치할 인덱스를 찾는다.
  • 만약 현재 num 이 d 에서 가장 큰 값이면 d 에 그냥 추가한다.
  • 만약 현재 num 이 d 내부에 위치해야 한다면, 해당 인덱스의 값을 더 작은 값인 num 으로 갱신한다.
    - 이를 통해 더 많은 값을 증가하는 부분수열로 묶을 수 있다.
    
    
    
    
• 그러나 d 가 가장 긴 부분 수열을 나타내는 것은 아니다.
  
  
  
  
• 따라서 수열의 모든 원소(O(N))에 대해 이분 탐색 (O(logN)) 을 진행하므로 총 시간복잡도는 O(NlogN) 이다.

출처: 코드플러스 - 알고리즘 중급 1/3 강의
https://code.plus/course/43