* 겪고 있는 문제 상황을 최대한 자세하게 작성해주세요.

* 문제 해결을 위해 어떤 시도를 해보았는지 구체적으로 함께 알려주세요.

https://www.acmicpc.net/problem/12015 (증가하는 부분수열 2)

python 실행속도가 같은 로직임에도 불구하고, 하나는 통과 / 하나는 시간초과가 납니다.

아무래도 python 에서 변수 등을 참조하는 데 있어서 내부 구현 때문에 (스코프가 중첩되면 비효율적이라든지) 그런것 같은데

명확한 이유가 알고 싶어서요.

작성한 코드 및 에러 메세지

통과한 코드

import sys
input = sys.stdin.readline
n = input()
arr = list(map(int, input().split()))
dp = []
ans = 0
cursor = 0
def bs_left(dp, target):
    left = 0
    # 중요 !! dp 내 삽입 위치 정하기
    right = len(dp) - 1
    while(left <= right):
        mid = (left + right) // 2
        if(dp[mid] < target):
            left = mid + 1
        else:
            right = mid - 1
    return left
for i in range(0,len(arr)):
    # 현재 요소가 dp 내 어느 위치에 있어야 할지 반환
    # 항상 dp의 끝부분은 가능한한 큰 수가 있으니까, 만약 그 수 보다 크다면 새로 덧붙이고
    # 만약 그것보다 작다면 적합한 위치를 찾아 대체 (값도, 키도 둘다 오름차순 임을 전제로)
    left = bs_left(dp, arr[i])
    if(left == len(dp)):
        dp.append(arr[i])
        ans += 1
    else:
        dp[left] = arr[i]
print(ans)

통과 못한 코드

import sys
input = sys.stdin.readline
n = input()
arr = list(map(int, input().split()))
dp = []
ans = 0
cursor = 0
for i in range(0,len(arr)):
    left = 0
    # 중요 !! dp 내 삽입 위치 정하기
    right = len(dp) - 1
    # 현재 요소가 dp 내 어느 위치에 있어야 할지 반환
    # 항상 dp의 끝부분은 가능한한 큰 수가 있으니까, 만약 그 수 보다 크다면 새로 덧붙이고
    # 만약 그것보다 작다면 적합한 위치를 찾아 대체 (값도, 키도 둘다 오름차순 임을 전제로)
    while(left <= right):
        mid = (left + right) // 2
        if(dp[mid] < arr[i]):
            left = mid + 1
        else:
            right = mid - 1
    if(left == len(dp)):
        dp.append(arr[i])
        ans += 1
    else:
        dp[left] = arr[i]
print(ans)