[BOJ] 12015, 12738. 가장 긴 증가하는 부분 수열 2, 3

www.acmicpc.net/problem/12015

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

www.acmicpc.net/problem/12738

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

 

문제: 수열이 주어지면 가장 긴 증가하는 부분 수열의 크기를 찾아라.

 

문제 이해하기!!

LIS 문제입니다.

딱 알고리즘 분류를 문제 제목에 나타내는 문제였어요.

다만, 이 LIS 문제가 되게 많은데, 계속 업그레이드되는 알고리즘을 써야된다는 ㅠㅠ

처음엔 O(n^2)으로 풀었다가 호되게 혼나고 O(nlogn)방법을 찾아야 했습니다.

찾은 방법은 dp와 이분탐색을 활용한 방식인데요.

 

그 방식을 설명하자면!!

1. 하나의 빈 배열을 만듭니다.

2. 입력된 배열을 하나씩 탐색하며 빈 배열에 이분탐색을 이용하여 자리를 찾습니다.

3. 해당 자리에 숫자를 바꾸거나 제일 크다면 1번에서 만든 배열에 추가합니다.

끝~~!!

 

이분탐색은 lower_bound를 사용해야합니다.

bisect_left로 사용하시면 됩니다. right로 사용지마세요 ㅎㅎ

 

그런데 위에거 2를 푸니까 3도 풀리더라구요? 개꿀 ~~

코드는 밑에 있습니다 ㅎㅎ

 

코드:

import bisect

N = int(input())
arr = list(map(int, input().split()))
dp = [arr[0]]
for j in range(1, N):
    idx= bisect.bisect_left(dp, arr[j])
    if idx == len(dp):
        dp.append(arr[j])
    else:
        dp[idx] = arr[j]

print(len(dp))