[코딩 테스트 연습(파이썬/Python)] 백준 11053번 _ 가장 긴 증가하는 부분 수열(LIS)

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

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

LIS(Longest Increasing Sequence)라 불리는 동적프로그래밍의 대표적인 문제라고 한다.

[문제]

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

[입력]

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

[출력]

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

[아이디어]

1) 수열이 최대 1000개로 이중 for문도 통과할 수 있다.

2) i번째 수에 대해 이전 모든 수에 대해 탐색하며 나보다 작은 경우에는 해당 (이전 수까지의 부분 수열의 길이 +1 vs 현재 i에 저장된 부분 수열의 길이) 중 긴 것을 택한다.

# 틀림. 반례: 1 5 6 2 3 4
n = int(input())
s = list(map(int, input().split()))
dp = [1]*n
for i in range(n):
    cnt = 1
    tmp = s[i]
    for j in range(i,n):
        if tmp <s[j]:
            cnt +=1
            tmp = s[j]
    dp[i] = cnt
print(max(dp))

처음에 했던 잘못된 접근이다. 늘 더 큰 수 만을 저장하고 이어가므로, 중간에 작은 숫자가 나왔다가 더 긴 증가 수열이 만들어지는 케이스를 커버하지 못한다.

n = int(input())
s = list(map(int, input().split()))
dp = [1]*n
for i in range(n):
    for j in range(i):
        if s[j] <s[i]:
            dp[i] = max(dp[j]+1, dp[i])
    print(dp)

 이렇게 하면 시간 복잡도가 O(n^2)이고, 이분 탐색을 통해 O(n*logn)까지 낮출 수 있다고 한다.