최장 증가 부분 수열
-
[Python] 최장 증가 부분 수열 구현하기프로그래밍/알고리즘 2022. 9. 22. 09:35
이번 글에서는 파이썬 언어로 최장 증가 부분 수열을 구현한다. 1. 최장 증가 부분 수열 증가 부분 수열이란, 기존의 수열에서 임의의 숫자들을 뽑았을 때 오름차순인 경우를 의미한다. 이때 연속하지 않아도 되며 뽑은 숫자들의 순서를 바꿀 수는 없다. 이렇게 생성될 수 있는 증가 부분 수열중에 가장 긴 길이를 가지는것이 최장 증가 부분 수열이다. 1 -1 2 0 1 1 2 3 -2의 수열이 있다면, 이중에서 -1 0 1 2 3 을 뽑아서 5의 길이를 가지는 최장 증가 부분 수열을 찾을 수 있다. 2. 동적 프로그래밍으로 구현 2.1 코드 예시1 # 제공된는 수열 input_lst = [1,-1,2,0,1,1,2,3,-2] # 동적 프로그래밍을 위한 기록 리스트 T = [0]*len(input_lst) # 첫..