백준 14003 가장 긴 증가하는 부분 수열 5

백준 14003 <-클릭

LIS알고리즘을 사용하여 최장 증가 수열을 구하는 문제이다. 1부터 5까지 있는데 5부터 풀어봤다.

1~4를 모두 확인한 것은 아니지만 기본적으로 같은 문제이고, 대신 테스트케이스의 조건이 달랐다.

해당 문제를 dp로 풀게되면 $O$($n^2$)의 시간 복잡도가 필요하다. 위 문제의 수열의 최대 길이는 1,000,000이므로 dp로 풀면 시간 초과가 나게 된다!

고로 위 문제의 경우 이진 탐색을 사용하여 시간 복잡도를 $O$($nlogn$)까지 줄여야 한다!

또한 위 문제는 수열의 길이 뿐 아니라 해당 수열까지 출력해야하므로 역추적을 해야한다.

LIS 란?

어떠한 수열의 증가하는 임의의 부분 수열중 가장 길이가 긴 수열.

예시) 수열[10 20 45 30 55 40 60]의 부분 수열 중 가장 길이가 긴 수열은
[10 20 45 30 55 40 60]으로 길이가 5일 것이다.

LIS 아이디어

LIS를 설명하기 전에, 변수를 다음과 같이 선언했다.
1. ans: 정답 수열.
2. main_branch: 임시 저장 배열정도로 생각하면 된다(자세한 것은 아래에). 이번에 변경(추가 혹은 교체)된 부분의 이전까지는 부분 증가 수열이다. 다만 길이가 최대인지는 모른다.
3. dp: main_branch에 삽입이 된다면 몇번째에 들어가는지 계산 후 저장한다.

• 배열의 원소가 main_branch의 마지막 원소보다 크면 main_branch에 추가(append)한다.
  
  
• 배열의 원소가 main_branch의 마지막 원소보다 작으면 main_branch에 삽입했을 경우 들어갈 인덱스(dp[i])의 원소 대신에 자기 자신을 삽입한다.

아래 예시로 설명하겠다.

idx	0	1	2	3	4	5	6
arr	50	60	70	10	20	30	40
main_branch	50	50,60	50,60,70	10,60,70	10,20,70	10,20,30	10,20,30,40
dp	1	2	3	1	2	3	4
비고	추가	추가	추가	교체	교체	교체	추가

main_branch의 0번 인덱스에 -INF값이 있음을 참고하고 봐야한다.

idx 0부터 2까지는 계속 최대값이 들어갔으므로 원소가 추가된다.
idx 3의 경우 10은 main_branch에 삽입될 경우 첫번째 인덱스에 삽입 될거니까 dp[3] = 1이다. main_branch의 1번 인덱스에 원래 있던 50대신 10을 삽입한다. 같은 방법으로 60과 70이 20과 30으로 대체된다. idx 5인 경우 main_branch가 [10,20,30], dp값이 3이다. 이 말은 branch[3]까지는 실제로 존재하는 증가 부분 수열이라는 것이다.

백트레킹

일단 최장 수열의 길이는 dp값 중 가장 큰 값임을 알 수 있다. 위 예시에서는 4이다. ans[4]는 dp값이 4일 때 추가된 수 중 가장 최근에 추가된 수(40) -> ans[3]은 dp값이 3일 때 추가된 수 중 4가 추가되기 이전에 추가된 수 중 가장 최근에 추가 된 수(30)->...반복

말이 엄청 복잡한데 직접 예시를 써보고 몇번 해보면 이해가 간다!

코드

github

from bisect import bisect_left

N = int(input())
arr = [0] + list(map(int,input().split()))
main_branch = [-float('inf')]
dp = [0]*(N+1)

for i in range(1,N+1):
    if(arr[i] > main_branch[-1]):
        main_branch.append(arr[i])
        dp[i] = len(main_branch)-1
    else:
        dp[i] = bisect_left(main_branch, arr[i])
        main_branch[dp[i]] = arr[i]
        
max_dp = max(dp)
print(max_dp)
ans = []
for i in range(N,0,-1):
    if(max_dp == dp[i]):
        ans.append(arr[i])
        max_dp = max_dp-1
        
print(*ans[::-1])

느낀점

오버워치 플레티넘 달성 기념으로 백준 플레 문제를 푸는데 처음에 C++을 통해 BST를 구현하여 나만의 방법으로 풀었었다.
원소를 BST에 삽입할 때마다 '가장 괜찮은'branch에 삽입하고 나머지는 지우는 방법으로 구현을 하였는데 worst case의 경우 BST가 원소 하나를 삽입하는데 $O$($n$)이 걸려 총$O$($n^2$)이 소요되는 비효율적인 알고리즘이 되었다 ㅠㅠ. 눈물을 머금고 LIS를 공부하여 해당 문제를 푸는데 다시 C++로 구현할 엄두가 나지 않아 파이썬으로 구현하였다.

아래는 상당히 비효율적인 코드 부산물
github

정답~.~