[알고리즘] 최대 부분 증가수열

(문제) 최대 부분 증가수열

---

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

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

입력설명

첫째 줄은 입력되는 데이터의 수 N(2≤N≤1,000, 자연수)를 의미하고,

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

출력설명

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

테스트케이스

입력예제	출력예제
8 5 3 7 8 6 2 9 4	4
11 5 2 18 3 4 7 10 9 11 8 15	7
5 5 4 3 2 1	1

---

해결방법

다이나믹 프로그래밍 이용한다.

다이나믹 프로그래밍 : 작은 시점에서 생각하여 기존의 정보를 저장하는 배열을 생성하여 문제를 해결하는 방식

예로 [5, 3, 7, 8, 6, 2, 9, 4]의 값을 가진 arr 배열과 같은 크기의 배열 dy = [0, 0, 0, 0, 0, 0, 0, 0] 다이나믹 프로그래밍을 이용할 배열로 생성한다.

첫 인덱스의 최대 부분 증가 수열로는 1개 밖에 없으므로 dy[0] = 1로 초기화 시켜준다.

그 후, 인덱스 1 부터 전의 인덱스 들의 값들과 비교하여 보다 작을 경우

dy[시작한 인덱스 전]에 해당 인덱스에 접근하여 반복을 통해 가장 큰 값을 가지고 오고,

거기에 자기 자신은 합쳐서 dy[시작한 인덱스 전] + 1을 하여 최대 길이 수열로 나타내 자기 위치의 dy[자신] 에 해당 값을 대입한다.

---

코드

n = int(input())

seq = list(map(int,input().split()))

# 다이나믹 배열안에 들어가는 것은
# 각항이 만들고자하는 증가 수열은
# 마지막 항일 때의 가장 긴 수열의 길이 값
dy = [0] * (n)

# [5, 3, 7, ...]
# 초기화 처음은 무조건 1개이므로
dy[0] = 1

for i in range(1, n):
    _max = 0
    # 뒤에 자기보다 작은 것이 있는지 확인
    for j in range(i-1, -1, -1):
        if seq[j] < seq[i]:
            # 그 작은 것들 중에서 가장 큰 dy 값을 얻기
            if _max < dy[j]:
                _max = dy[j]
    # 찾은 것에 자기 스스로를 수열에 추가
    _max = _max + 1
    # 경우의 값을 넣는다
    dy[i] = _max

print(max(dy))