[Python] 최장 증가 부분 수열 구현하기

이번 글에서는 파이썬 언어로 최장 증가 부분 수열을 구현한다.

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)
# 첫번째 값은 그 자체로 길이 1의 수열
T[0] = 1

# 두번째 인덱스부터 for문으로 접근
# 이전 인덱스의 증가 부분 수열을 이용해 최장 증가 부분 수열 계산
for i in range(1,len(input_lst)):
    # 임시저장 리스트, 0은 max 비교연산 오류 방지 초기값
    tmp = [0]
    # 0 인덱스부터 i인덱스 전까지 반복
    for j in range(i):
        # lst[j]의 값이 lst[i]의 값보다 작다면,
        # lst[j]와 lst[i]는 증가 부분 수열로 이어질 수 있음
        if input_lst[i]>input_lst[j]:
            tmp.append(T[j]) # 인덱스 j까지의 최대 증가 부분 수열 길이 불러오기
        # lst[i]와 증가 부분 수열이 될 수 있는 lst[j] 후보군의 
        # 각 최대 증가 부분 수열 길이가 모두 tmp에 들어있음
        # 이중에서 가장 큰 수열 길이를 선택 후 +1
        T[i] = max(tmp) + 1
    
# 최종적으로 구한 각 자리에서의 최대 증가 부분 수열의 길이들 중에서
# 제일 긴 값을 채택
print(max(T))
#=> 5

2.2 코드 예시2

2.1의 방법과 동일하게 구성

리스트간의 더하기와 컴프리헨션등을 이용하여 코드 간소화

# 제공된는 수열
input_lst = [1,-1,2,0,1,1,2,3,-2]

# 동적 프로그래밍을 위한 기록 리스트
T = [1]+[0]*(len(input_lst)-1)

for i in range(1,len(input_lst)):
    T[i] = max([0]+[T[j] for j in range(i-1,0,-1) if input_lst[i]>input_lst[j]])+1
print(max(T))
#=> 5