[Python] BOJ 11053 : 가장 긴 증가하는 부분 수열

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

요구사항 

1. 시간제한 1초
   1. N의 크기가 1,000 으로 작아 O(N**2) 까진 무리없다.
2. 메모리 제한 256MB 
   
   1. 1,000 * 4  = 약 0.04MB
3. 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하라.

설계 1

1. 첫째 줄에 수열 A의 크기 N을 입력받는다.
2. 둘째 줄에 수열 A를 이루고 있는 Ai 를 입력받는다. 
3. 마지막 수열 안에 A[-1] 보다 작은 수를 카운트 한다. 
4. DP 테이블에 카운트 개수를 넣어준다.
5. DP 테이블의 max 값을 출력한다.

구현 1

import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
A = list(map(int, input().split()))
dp = [0] * (N+1)

for i in range(N, 0 ,-1):
    count = 0
    for j in range(i):
        if A[i - 1] > A[j - 1]:
            count += 1
    dp[i] = count
    
print(max(dp))

실수 1 [반례가 있다.]

• 수열 A 가 [10, 20, 10, 30, 20, 50] 이라 하자. 
• 그럼 50보다 작은 수는 5개 이다. dp[6] = 5개 
• 하지만 수열 A는 정렬되어 있지 않다. 따라서 가장 긴 부분 수열이 될 수 없을 수도 있다. 

설계 2

• 뒤에서 카운트 하니 저런 반례가 있고 딱히 더 이상 역순으로 뭔가 만들고 싶지 않다. 
• 1이상 수열의 경우 가장 긴 증가하는 부분 수열은 항상 1이상이다.
• 따라서 DP테이블을 1로 초기화 해주었다.
• 만약 앞의 수보다 뒤의 수가 크다면 ( 10 <  20 ) 비교한 자리에서 + 1
• 구현한 내용을 보는 게 더 이해가 빠를 듯 하다.

구현

import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
A = list(map(int, input().split()))
dp = [1] * (N+1)

for i in range(N):
    count = 0
    for j in range(i):
        if A[i] > A[j]:
            dp[i] = max(dp[i], dp[j] + 1)
# print(dp)    # [1, 2, 1, 3, 2, 4, 1]
print(max(dp)) # 4

• 현재 O(N**2) 이다. 더 줄일 수 있는 방법을 찾아보았다.

추가로

import sys, bisect
input = lambda: sys.stdin.readline().rstrip()

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

for num in A:
    pos = bisect.bisect_left(lis, num)

    if pos < len(lis):
        lis[pos] = num
    else:
        lis.append(num)

print(len(lis))

 

• bisect_left는 이진 탐색을 통해 리스트에서 숫자가 들어갈 위치를 빠르게 찾습니다.
• LIS 알고리즘은 이진 탐색을 사용하여 O(n log n) 시간 복잡도로 해결됩니다.
• if pos < len(lis):
  • 찾은 위치 pos가 lis의 길이보다 작은지 확인합니다. 이 조건이 참이라는 것은, num이 현재 lis에서 교체될 수 있는 값이 있다는 뜻입니다.
  • 즉, lis에 있는 기존의 값과 비교해 더 작은 값으로 갱신할 수 있을 때 실행됩니다.