[백준] 11053번 가장 긴 증가하는 부분 수열(LIS)(DP)(Python - 파이썬)

백준 11053번 문제입니다. (solved.ac)기준 실버 2 문제입니다.

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 부분 수열이란? 

 원소가 n개인 수열의 일부 원소를 골래내어 만든 수열이 부분 수열입니다. 

seq = [ 10, 20, 10, 30, 20, 50]이라는 수열이 존재할 때 이 수열의 부분 수열로는 

[10,20], [20, 10, 50], [30, 50] ... 등이 있습니다.

문제 접근

수열을 입력 받고 그 중 가장 긴 증가하는 부분 수열(LIS)의 길이를 출력하는 문제입니다. 

LIS(Longest Increasing Subsequence)는 부분 수열 중 각 원소가 이전 원소보다 크고 길이가 최대인 부분 수열을 말합니다.

예제 입력 1의 최장 증가 수열(LIS)은 [10, 20, 30, 50]이며 길이는 4입니다. 

11053번 문제를 해결하기 위하여 O(N^2)의 시간복잡도를 가지는 DP(다이나믹 프로그래밍)방식을 이용하여 문제를 해결하였습니다.

seq[i]는 수열(seq)의 i번째 인덱스를 가리킵니다.(헷갈리지 않도록 1번째 인덱스부터 세기위하여 맨 앞에 0을 넣어줬음 [seq.insert(0,0)] )

 d[i]는 i번째 인덱스에서 끝나는 최장 증가 부분 수열(LIS)의 길이입니다.  ex ) d[5]는 seq[5]로 끝나는 부분 수열의 LIS

 d[i]를 구하기 위해서는 수열의 i번째 인덱스에 있는 값(seq[i]) 이 최대가 되어야하기 때문에 그보다 작은 값(작은 값의 인덱스를 j라고 가정)을 찾아 그중 가장 큰 LIS( d[j] )에 +1을 해주면 됩니다. 만약 i번째 인덱스의 크기가 1  ~ i-1번째 인덱스 사이의 모든 값보다 작다면 d[i]는 1이 됩니다(부분 수열이 seq[i]로만 이루어짐).

 

과정 설명 (예제 입력 1)

예제 입력 1번으로 간단하게 예시를 들어보겠습니다. 수열은 seq = [0, 10, 20, 10, 30, 20, 50] 으로 구성되어있습니다. 가장 앞에 0이 들어간 이유는 편하게 1번째 인덱스부터 세기 위하여 맨 앞에 0을 넣어 주었습니다.

d[1]은 당연히 [10]이기 때문에 1이고 d[2]는 [10, 20]인 2입니다.  d[3]또한 [10]이기 때문에 1입니다. d[4]를 살펴 보겠습니다. 

d[4]는 seq[4]의 값인 30으로 끝나는 LIS입니다. 1번째 인덱스부터 현재 인덱스보다 하나 작은 3번째 인덱스까지의 수열 값중(seq[1]~seq[3]) 현재 인덱스의 수열값(seq[4] = 30)보다 작은 값들을 찾습니다. 그 후 그 인덱스(j인덱스라고 가정)의 LIS(d[j])중 최 댓값에 +1을 하여주면 됩니다.([10, 20] + [30])

 따라서 d[4]는 [10, 20, 30]으로 이루어진 부분 수열의 길이이므로 3이 됩니다. 마찬가지로 동일한 방법을 반복하여

d[5]가 [10, 20, 30, 50]인 LIS이며 길이는 4가 됩니다.

정답 코드

# 수열의 길이
a = int(input())

# 수열을 입력 받음
seq = list(map(int, input().split()))
# 1번째 인덱스부터 편하게 세기 위하여 맨 앞에 0을 넣어줌
seq.insert(0, 0)
# 미리 최대 수열의 길이만큼 리스트 초기화
d = [0] * 1001

for i in range(1, len(seq)):
    # 만약 i번째 인덱스의 크기가 1  ~ i-1번째 인덱스 사이의 모든 값보다 작다면 d[i]는 1
    d[i] = 1
    # j는 1 ~ i-1의 범위를 탐색
    for j in range(1, i) :
        # i번째 인덱스의 수열값(seq[i])이 탐색중인 j번째 인덱스의 수열값(seq[j]) 보다 크다면
        if seq[i] > seq[j] :
            # d[i]값 갱신
            d[i] = max(d[j]+1,d[i])

# LIS 출력
print(max(d))