[백준 알고리즘] 가장 긴 증가하는 부분수열1~4. 파이썬(python)

 

---

가장 긴 증가하는 부분 수열 1 (길이 구하기, n≤1,000, 1초)

n의 크기가 상대적으로 작기 때문에 기존의 dp방식인 이중 for문 O(n^2)을 사용해도 통과할 수 있다.

 

가장 긴 증가하는 부분 수열 2 (길이 구하기, n≤1,000,000, 1초)

가장 긴 증가하는 부분 수열 3 (길이 구하기, n≤1,000,000, 3초)

n=int(input())
arr=list(map(int, input().split()))
dp=[arr[0]]

def binarySearch(target,s,e):
    while s<=e: # 시작 지점이 끝보다 작을 때까지
        mid=(s+e)//2 # 중간값

        if dp[mid]>=target: # 비교하는 값이 중간값보다 작으면
            e=mid-1 # 끝지점을 중간값-1로 바꾼다
        else: # 중간값보다 크면
            s=mid+1 # 시작지점을 중간값+1로 바꾼다
    return s

for i in arr:
    if dp[-1]<i: # dp의 마지막값(제일 큰 값)보다 현재값이 크면
        dp.append(i) # 값을 추가한다
    else: # 작으면 교체한다(더 긴 수열을 만들 가능성이 있으므로 버리는 것이 아님)
        dp[binarySearch(i,0,len(dp)-1)]=i # 이진탐색으로 한단계 큰 값을 찾아 현재값으로 변경한다

print(len(dp))

1, 2, 3의 차이는 시간 제한과 n의 크기이다.

n의 크기가 크기 때문에 이분탐색을 이용한다.

위 코드는 이분탐색의 O(logn) 에 반복문 한 번으로 O(n)이 합쳐져 O(nlogn)의 시간복잡도를 갖는다. 

 

[10, 20, 15, 30, 40, 18, 50]

10	10 추가
10 20	20 추가
10 15	20을 15로 교체
10 15 30	30 추가
10 15 30 40	40 추가
10 15 18 40	30을 18로 교체 → 원래 있던 30을 바꿔줌으로써 길이는 그대로 고정한 채 더 작은 값으로 바꾸어 길이를 더 길게 만들 수 있는 상태가 된다.
10 15 18 40 50	50 추가

10 15 18 40 50는 처음 수열을 보면 만들어질 수 없는 순서이지만 길이가 고정되있다.

 

 

가장 긴 증가하는 부분 수열 4 (길이와 수열 구하기, n≤1,000, 1초)

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

for i in range(n):
    for j in range(i): # 현재값의 전값까지 돈다
        if arr[i]>arr[j]:# 현재값이 전값보다 크면
            dp[i] = max(dp[i],dp[j]+1)

print(max(dp))

sq=[]
value=max(dp)
for i in range(n-1, -1, -1): # 끝부터 시작까지 -1씩 감소
    if dp[i]==value:
        sq.append(arr[i])
        value-=1

sq.reverse()
print(*sq)

 

---

참고

https://velog.io/@ledcost/%EB%B0%B1%EC%A4%80-12015-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-2-%EA%B3%A8%EB%93%9C2-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89

https://suri78.tistory.com/199

https://ji-gwang.tistory.com/278