가장 긴 증가하는 부분 수열 3 , 4(LIS)
알고리즘 파이썬
문제
사용한 라이브러리
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의 길이는 가장 긴 증가하는 부분 수열의 수가 된다.
문제점
길이만 구할수있고 원소들을 구하지 못함
공부후에 올릴 예정..
후기
알고리즘의 흐름은 이해했지만
문제 유형 , 구현에 미숙함
아직은 답을 보면서 다른사람들의 코드를 이해하면서 공부하는중...
Author And Source
이 문제에 관하여(가장 긴 증가하는 부분 수열 3 , 4(LIS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@slbin-park/가장-긴-증가하는-부분-수열4저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)