개구리

우물 안 개구리

가장 긴 증가하는 부분 수열 문제 중 가장 마지막 문제다. 주어진 수열의 길이가 작다면 dp를 이용하여 O(n^2)의 시간 복잡도로 해결하는 것이 일반적인 방법이다.

그러나 백준 12738번, 가장 긴 증가하는 부분 수열 3과 해당 문제의 경우 수열의 길이가 1,000,000이다. dp와 함께 이분 탐색을 활용하여 시간 복잡도를 줄일 수 있다.

O(n log n) 알고리즘 설명

LIS의 길이

O(n log n)으로 LIS문제를 푸는 방법의 핵심은 LIS를 직접 찾지 않는 것이다. 우선 LIS의 길이를 구해보자.

  • 루프에서 주어진 순열을 탐색하며 dp가 비어있거나(원소에 [0,0]만 있는 경우) dp의 마지막 값이 현재 값보다 작다면 현재 값을 dp에 저장한다.
  • dp의 마지막 값이 현재 값보다 크다면 dp의 원소들을 탐색하며 현재 값보다 큰 값들 중 가장 작은 값을 현재 값으로 교체한다. 이 때 이분 탐색을 사용한다.
  • 루프가 종료됐을 때 dp의 길이가 LIS의 길이다. (dp에 LIS가 있는 것은 아니다)

dp가 갱신될 때 항상 인덱스의 순서가 지켜지는 것이 아니다. 그러나 dp의 길이는 항상 유지된다. 다음의 경우를 가정해보자.

예시

주어진 수열 - 10 20 30 15 40

[10] - dp가 비어있으므로 dp에 10이 추가된다.

[10, 20] - 20은 dp의 마지막 값인 10보다 크기 때문에 dp에 20이 추가된다. 이 때 dp에는 증가하는 부분수열이 올바르게 저장되어 있다.

[10, 20, 30] - 30이 추가되고 여전히 인덱스와 원소의 값 모두 증가하고 있다.

[10, 15, 30] - 15는 30보다 작기 때문에 이분 탐색을 통해 교체될 자리를 찾아야 한다. dp의 길이는 교체 전에 구한 LIS의 길이로 유지되고 있다. 그러나 15의 인덱스가 30의 인덱스보다 크기 때문에 증가하는 부분수열은 아니다.

[10, 15, 30, 40] - 40은 30보다 크기 때문에 dp에 추가된다. 이 때 인덱스는 오름차순이 아니지만 15를 20으로 교체한다면 증가하는 부분 수열이다. 루프를 반복하며 인덱스가 오름차순으로 갱신되지 않더라도 상관없다. 교체된 값들을 역으로 추적하여 LIS를 만들 수 있다. 마지막에 추가되는 값이 이전에 dp의 마지막 값보다 큰 것이 중요하다.

원소를 조금 더 추가해보자. 주어진 수열 - 10 20 30 15 40 25 35 38

[10, 15, 25, 40] - dp에 담긴 값들의 인덱스는 [0, 3, 5, 4]이다. 이제는 40만 갱신되면 인덱스가 오름차순이다. 앞에서 설명했듯이 만약 이후에 50이 등장하여 길이가 5인 dp로 갱신된다면 이전에 교체된 값들을 적절히 추적하여 다시 LIS를 만들 수도 있다.

[10, 15, 25, 35] - 마지막 인덱스가 교체되었다.

[10, 15, 25, 35, 38] - 38이 추가되었다. 인덱스는 [0,3,5,6,7]으로 오름차순이고 값들도 증가하기 때문에 증가하는 부분 수열이다.

LIS의 길이 구하는 법 정리

즉, 루프가 진행되며 dp가 갱신될 때 다음과 같은 경우가 존재한다.

  1. dp의 길이가 유지될 때 모든 인덱스가 오름차순이 아니더라도 교체하기 전 값들로 추적하면 LIS를 알 수 있다.
  2. dp에 새로운 값이 추가될 때 오름차순이 아닌 인덱스가 존재한다면 해당 인덱스들을 교체하기 전 값들로 추적하면 올바른 LIS를 알 수 있다.
  3. dp에 새로운 값이 추가될 때 모두 오름차순이라면 LIS가 dp에 저장되어 있다.

그러므로 dp가 모두 갱신되면 dp의 길이는 LIS의 길이와 동일하다.

문제 풀이

LIS 구하기

dp가 갱신되며 인덱스의 값들을 적절히 추적하면 LIS를 구할 수 있다는 점을 이용한다.

코드

N= int(input())
arr = list(map(int, input().split()))

dp=[[0,0]] # index도 저장
tracking=[0 for _ in range(N+1)]
idx=0

for i in range(len(arr)):
    
    target = arr[i]
    if len(dp)==1 or dp[-1][0] < target :

        tracking[i] = dp[-1][1]
        dp.append([target,i])
        idx = i
        
        
    else:
        s,t = 0, len(dp)
        
        while t-s>1:
            
            mid = (s+t)//2      
            if dp[mid][0] >= target :
                ans = mid
                t=mid
            else:
                s=mid
    
        dp[ans][0]=target
        dp[ans][1]=i
        tracking[i] = dp[ans-1][1]
        

sol=[]
for _ in range(len(dp)-1):
    sol.append(arr[idx])
    idx = tracking[idx] 
sol.reverse()
print(len(dp)-1)
print(*sol)

항상 append를 사용하다가 마지막 sol 배열에 추가하는 과정에서 sol.insert(0, arr[idx])로 풀었다. 당연히 시간초과 발생했다. append의 경우 O(1), insert는 O(N)의 시간이 소요된다. 즉 append로 배열을 만든 후 reverse를 사용하여 푸는 것이 효율적인 방법이다.

댓글남기기

참고