[소프티어][이분탐색][최장증가수열] 징검다리

징검다리

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

• 풀이 - DP방식 (O(N^2))
  • 최장증가수열 기본 풀이
  • i 이전값들 중 작은 값들의 횟수+1과 비교해서 더 큰 값으로 저장
  • j번째부터 시작하는 경우의 횟수를 LIS에 저장하는것

import sys
input=sys.stdin.readline

n=int(input())
stone=list(map(int,input().split()))

LIS=[0]*n

result=0
for i in range(0,n):
    LIS[i]=1
    for j in range(0,i):
        if stone[j]<stone[i] and LIS[i]<LIS[j]+1:
            LIS[i]=LIS[j]+1
    result=max(result, LIS[i])

print(result)

 

• 좀더 간단한 코드

def lis_dp(arr):
    n = len(arr)
    dp = [1] * n

    for i in range(n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

 

• 풀이 - 이분탐색 방식 O(NlogN)
  • LIS 자체를 구하는건 아님
  • 길이만 유지하는 것

import sys
from bisect import bisect_left
input=sys.stdin.readline

n=int(input())
stone=list(map(int,input().split()))

def lis_binary_search(arr):
    sub = []

    for num in arr:
        idx = bisect_left(sub, num)
        if idx == len(sub):
            sub.append(num)
        else:
            sub[idx] = num

    return len(sub)

answer=lis_binary_search(stone)
print(answer)