[BOJ] 11053. 가장 긴 증가하는 부분 수열(Python) / DP

www.acmicpc.net/problem/11053

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

LIS(Longest Increasing Subsequence, 최장 증가 부분 수열 문제)는 가장 전형적인 Dynamic Programming 문제!

• 수열의 크기가 N일 때, 기본적인 DP 알고리즘으로 시간 복잡도 O(N^2)으로 해결할 수 있다.

• dp[i] = array[i]를 마지막 원소로 가지는 부분수열의 최대 길이

• 모든 0 <= j < i에 대해, dp[i] = max(D[i], D[j] + 1 if A[j] < A[i]

평생 이해 못할 것 같은 이 LIS문제... i가 1~N일 때까지 구성되는 dp 테이블 손으로 그려보며 겨우 이해했다!

 

 

파이썬 코드는 다음과 같다.

---

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

dp = [1] * N
for i in range(1, N):
    for j in range(i):
        if A[j] < A[i]:
            dp[i] = max(dp[i], dp[j] + 1)
    # print(i, dp)
print(max(dp))

---

• 고찰 : 어려워도 피하지 말자! 나의 의지가 부족한 것이니, 더욱 깊게 파고들어 내 것으로 만들자.