알고리즘 파이썬

문제

사용한 라이브러리

bisect
정렬된 배열에서 특정 원소를 찾을때 사용
bisect_left(a, x)
-> 정렬된 순서를 유지하면서 리스트 a 에서 삽입할 x의 가장 왼쪽 인덱스

정답

import bisect
x = int(input())
arr = list(map(int, input().split()))
dp = [arr[0]]

for i in range(x):
    if arr[i] > dp[-1]:
        #오른쪽에서 왼쪽방향 -1
        dp.append(arr[i])
    else:
        idx = bisect.bisect_left(dp, arr[i])
        dp[idx] = arr[i]
print(len(dp))

설명

arr[i] 가 dp의 마지막 원소 보다 클 경우 즉 앞에 원소들보다 클 경우
dp 마지막 위치에 추가함
arr[i] 가 dp의 마지막 원소보다 작을 경우
증가하는 수열이 있는 베열 dp 안에서 들어갈 위치 index 값을 arr[i]로 교체
dp의 길이는 가장 긴 증가하는 부분 수열의 수가 된다.

문제점

길이만 구할수있고 원소들을 구하지 못함
공부후에 올릴 예정..

후기

알고리즘의 흐름은 이해했지만
문제 유형 , 구현에 미숙함
아직은 답을 보면서 다른사람들의 코드를 이해하면서 공부하는중...

참고블로그