[Python] 섹션 8 DP(동적계획법) - 최대 부분 증가수열

인프런 - 파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) 강의를 보고 정리한 글입니다.

 

최대 부분 증가수열이란?

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는 (작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라.

예를 들어, 원소가 2,7,5,8,6,4,7,12,3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2,5,6,7,12를 뽑아내어 길이가 5인 최대 부분 증가수열을 만들 수 있다.

 

입력설명

첫째 줄은 입력되는 데이터의 수 N을 의미하고, 

둘째 줄은 N개의 입력데이터들이 주어진다.

 

출력설명

첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.

 

입력예제 1

8

5 3 7 8  6 2 9 4

 

출력예제 1

4

- maybe... 5 7 8 9 의 길이일 듯 하다.

 

아이디어

arr = [5,3,7,8,6,2,9,4]

# 각 수마다, 가장 긴 수열의 길이
dy = []
dy[0] = 1
dy[1] = 1

dy[2] = 2
dy[3] = 3 # 앞에 있는 애들 중에 가장 길이가 긴 얘를 기준으로 따라붙기.
dy[4] = 2 # 앞에 있는 애들 3밖에 없으니 3 뒤에 붙음
dy[5] = 1 # 앞에 있을 수 있는 애들이 없음
dy[6] = 4 # 앞에 있는 애들 중에 dy[3] 이 젤 큼 거기에다가 1 더하기
dy[7] = 2 # 가능한 애가 2,3 인데 둘 다 1이니 1 더해서 2가 됨

# dynamic 중에 가장 큰 값인 4가 답이 된다.

 

dp의 특성 상 구해뒀던 값을 버리지 않고, 다시 재사용하는 것이다.

각 인덱스의 숫자마다. 그 숫자를 마지막 요소로 둔 부분증가수열의 최대 길이를 정한다.

 

이 때, 최대 길이는 마지막 요소로 숫자를 뒀을 때, 앞에 올 수 있는 수 중에서 가장 최대 길이를 가지고 있는 값을 토대로 뒤에 붙으면 된다는 소리 ... 그렇게 되면 가장 최대 길이를 가지고 있는 dy[인덱스]에 해당하는 값에 1을 더 하면 된다.

 

구현 코드

# 구현 코드

n = int(input())
arr = list(map(int, input().split(" ")))

arr.insert(0,0)# 맨 앞에다가 하나 0을 넣어서 index 를 1부터 시작할려고 밀은 것임.

dy = [0] * (n+1) # 리스트 만들기
dy[1] = 1 # 첫 번째 값으로 만들고자 하는 수열의 숫자 개수는 무조건 1일 수 밖에 없다.
res = 0 # 최대 길이에 대한 값

for i in range(2,n+1):
    maxi = 0
    for j in range(i-1,0,-1):
        if arr[j]<arr[i]: # arr[i] 는 내가 만들고자 하는 수열의 마지막 수, arr[j]는 따라붙을 얘를 찾는 것.
            maxi = max(maxi, dy[j])
    dy[i] = maxi + 1

print(max(dy))

 

이런 아이디어는 어떻게 생각해내는 거죠?

정말 인류는 대다나다...