백준 11053번 파이썬 문제풀이(DP - 가장 긴 증가하는 부분 수열)

---

위의 문제는 최장 증가 부분 수열(LIS) 알고리즘 이라고 실제로 존재하는 알고리즘이다. 위의 알고리즘은 간단히 얘기하면 입력받은 배열 원소에 하나씩 접근하여 뽑은 원소 직전에 존재하는 원소들과 일일이 하나씩 크기를 비교하며 만약 작은 값이 존재하면 DP에 부분수열값을 +1 씩 해주는 알고리즘이다. 말로설명하면 어려우니 코드를 한번 보면 이해하기 쉽다.

N = int(input())
input_array = list(map(int, input().split()))
dp = [1] * N  # 최장수열 길이를 저장할 dp 리스트선언

for i in range(N):  # 배열 길이만큼돈다.
    for j in range(i):  # 해당 배열 원소의 직전 원소까지 돈다.
        if input_array[i] > input_array[j]:  # 만약 해당 원소가 전 원소보다 크다면
            dp[i] = max(dp[i], dp[j] + 1)
            # 전 원소에 저장되어 있는 최장수열길이에서 +1 값과 저장되어있는 수열길이값을 비교해서 큰값을 대입

print(max(dp))  # 최장수열길이 출력

-> 그런데 위 알고리즘의 시간복잡도는 O(n^2) 이다. 인풋 값이 백만 개 정도만 되어도 O(n^2)의 알고리즘은 실행시간이 10초 이상 소요된다고 알려져 있기때문에 시간복잡도를 개선하기 위해 이분탐색을 활용한다. 이분탐색에 대해서는 기회가 된다면 포스팅하겠다!