[파이썬 알고리즘 문제풀이] - Section8 / Dynamic programming(동적계획법) - 4

조현수·2023년 2월 13일
0

최대 부분 증가수열

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길이가 5인 최대 부분 증가수열을 만들 수 있다.

▣ 입력설명
첫째 줄은 입력되는 데이터의 수 N(2≤N≤1,000, 자연수)를 의미하고,
둘째 줄은 N개의 입력데이터들이 주어진다.
▣ 출력설명
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.
▣ 입력예제 1
8
5 3 7 8 6 2 9 4
▣ 출력예제 1
4

import sys
# sys.stdin = open("input.text", "rt")

n = int(input())
data = list(map(int, input().split()))
data.insert(0,0) #1번 인덱스부터 확인하기 위해서 앞에 삽입
dp = [0] * (n+1)
dp[1] = 1 #객관적으로 자명한건 미리 쓰자

res = 0
for i in range(2,n+1):
    max_length = 0
    for j in range(i): #i보다 앞에까지 돌면서 최장 부분 증가수열 최댓값을 찾는다.
        if data[j] < data[i] and dp[j] > max_length: #data[i]의 값, 즉 i번째 숫자가 내가 만들고자 하는 증가수열의 마지막 항을 의미해
            max_length = dp[j] #dp[j]는 data[j], 즉j번째 항이 마지막 항인 증가수열의 최대 길이
    dp[i] = max_length + 1
    if dp[i] > res:
        res = dp[i]

print(res)

코멘트

작은 문제를 점점 확장시켜나가는 바텀업 방식으로 LIS 문제 해결. 현재 내 자리까지가 마지막 항이라고 생각하고 증가수열을 만들어야 했다.

profile
back-end, 지속 성장 가능한 개발자를 향하여

0개의 댓글