[🥇2 / 백준 12015 / 파이썬] 가장 긴 증가하는 부분 수열 2

 

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

예제 입력  6 10 20 10 30 20 50

예제 출력  4

 

풀이

 

이전에 다이나믹 프로그래밍으로 풀었던 문제이다.

 

하지만 이번엔 수열의 크기 입력값이 최대 1,000,000으로, 1,000배 늘었다.

 

알고리즘을 그대로 활용한다면 시간 초과가 걸릴 것이다.

 

따라서 다이나믹 프로그래밍 대신 이분 탐색을 이용해 풀도록 하자.

 

 

핵심 알고리즘은 정답 수열의 마지막 수보다 큰 수가 들어오면 append 하고,

 

아니라면 그 전의 수들과 비교하여 적절한 교체 위치를 찾는 것이다.

 

 

1 4 7 3 4 6 을 예제로 풀어보자.

 

1 4 7 까지는 수열이 그대로 진행된다. 다음 수가 정답 수열의 마지막보다 크기 때문이다.

 

이제 3을 놓을 자리를 찾아야 한다. 1보다 크고, 4보다는 작다. 1을 바꾼다면 얻는 이득이 없다. 

 

4를 바꿔 1 3 7로 만들어주자.

 

다음은 4이다. 3보다 크고 7보다 작다. 1 3 4로 만들어주자.

 

마지막으로 6이 들어왔다. 4보다 크므로 1 3 4 6이 된다.

 

이런 식으로 마지막 수보다 작다면 이전의 수들 중 적절한 것과 바꿔 수열의 수를 작게 만들면서

 

다음에 올 수를 추가할 수 있게끔 하는 것이다.

 

맨 마지막 수가 작아야만 다음에 올 수를 더 많이 추가할 수 있기 때문이다.

 

그리디 알고리즘과도 유사하다고 할 수 있겠다.

 

n = int(input())
A = list(map(int,input().split()))
result = [A[0]]

for i in A[1:]:
    start, end = 0,len(result)
    
    # 현재 수가 결과 수열의 마지막보다 크다면 
    # 그냥 append 해주고 끝내면 된다.
    if i > result[-1]:
        result.append(i)
        continue
    
    # 이분 탐색으로 현재 수가 들어갈 적절한 위치를 찾는다.
    while(start < end):
        mid = (start + end)//2
        
        if result[mid] < i:
            start = mid + 1
        else:
            end = mid
    
    # 들어갈 자리에 있는 수가 i보다 크거나 같다면 i로 교체
    # 작다면 굳이 바꿀 필요가 없으니 다음 수를 i로 교체해준다.
    if result[mid] >= i:
        result[mid] = i
    else:
        result[mid+1] = i
print(len(result))