[알고리즘] 동적 계획법(Dynamic Programming) - 백준 11053번 가장 긴 증가하는 부분 수열

LIS 란?

Longest Increasing Subsequence
최장 증가수열 = 최대 증가 부분수열

LIS는 어떤 수열에서 특정 부분을 지워서 만들어낼 수 있는 증가 부분수열 중 가장 긴 수열을 말한다.

증가에는 순증가와 단조증가가 있는데, 순증가는 앞의 숫자가 무조건 큰 경우 단조증가는 뒤의 원소가 앞의 원소 이상인 것을 말한다.

LIS는 보통 순증가하는 부분수열을 대상으로 한다.
원 배열이 [1, 2, 5, 3, 4] 일때, 부분 수열에는 [1, 2], [1, 2, 3, 4], [2, 3, 4] 등이 있고 여기서 가장 긴 부분열은 [1, 2, 3, 4] 이다.

코드

import sys
input = sys.stdin.readline

n = int(input().rstrip())
seq = list(map(int, input().rstrip().split()))
dp = [1] * n

for i in range(n):
    for j in range(i):
        if seq[i] > seq[j]:
            dp[i] = max(dp[i], dp[j]+1) # dp[i]는 중복 제거 위함

print(max(dp))

풀이과정

1. seq 배열에 주어진 숫자를 넣는다. 각 원소에서 가장 작은 수열의 크기는 1임으로 n 개수 만큼 dp 배열을 만든다.
2. 이중 for 문을 돌면서 해당 원소와 앞의 원소들을 비교한다. 만약 해당 원소가 앞의 원소보다 크다면, dp 원소 값을 바꾼다.
3. 이때 dp[i]와 dp[j]+1을 비교하여 더 큰 값을 넣는데, dp[i]를 비교하는 이유는 중복된 값을 제거하기 위함이다. 예를들어, [10, 20, 10, 30] 이 있을 때, 30을 기준으로 10은 2번 있기 때문에 하나는 세지 않아야 한다.