💡 문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 A가 주어진다. (1 ≤ A ≤ 1,000,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
💭 접근
이 문제는 11053번 가장 긴 증가하는 부분 수열 문제와 똑같지만, 이 문제는 입력의 최대가 1,000,000이므로 DP를 활용한 LIS 알고리즘은 O(N)이기 때문에 DP를 사용할 순 없다. 따라서 시간복잡도가 O(logN)인 이진 탐색 알고리즘을 사용하여 문제를 해결할 수 있다.
우선 이 문제를 해결하는 방법으로 결론부터 서술하자면, 주어진 수열 A에서 만들 수 있는 가장 긴 증가하는 부분 수열을 만들기 위해선, 먼저 리스트 A의 첫번째 요소(A[0])이 들어있는 LIS 리스트에서 시작하여 리스트 A 탐색하며 LIS 리스트의 마지막 원소보다 A[i]가 크다면 LIS 리스트의 마지막에 append해주고, 만약 마지막 원소보다 작거나 같은 A[i]가 있다면 A[i]로 LIS 리스트의 요소 중 처음으로 크거나 같은 수 자리를 대체시킨다.
위와 같은 방법을 사용하는 이유를 설명하기 위해 한가지 간단한 예를 들어보자.
여기 [1, 3, 8, 4, 5] 라는 수열 A가 주어졌다고 가정해보자.
단순히 첫번째 요소부터 탐색하며 LIS를 구성한다면 [1, 3, 8] 즉 길이 3인 리스트가 만들어질 것이다. 그러나 실제 LIS는 [1, 3, 4, 5]로 구성된 길이 4인 리스트가 정답인데, 이처럼 4를 만났을 때 8보다 작다고 버리는 것이 아닌, 3보단 크고 8보단 작으므로 4 뒤에 있을 수도 있는 4보다 크고 8보다 작은 수를 더 이을 수 있도록 이전 요소보다는 크되, 최대한 작은 수로 대체시키는 것이다.
그렇다면 위에서 말한 방법을 통해 [1, 3, 8, 4, 5] 리스트로 LIS를 구성해보자. 먼저 LIS는 A[0] 요소를 포함한 채로 시작한다.
-
LIS의 초기상태
-> LIS = [1] -
A[1] = 3: A[1]은 LIS의 마지막 요소(1)보다 크므로 그냥 뒤에append
-> LIS = [1, 3] -
A[2] = 8: A[2]는 LIS의 마지막 요소(3)보다 크므로 그냥 뒤에append
-> LIS = [1, 3, 8] -
A[3] = 4: A[3]은 LIS의 마지막 요소(8)보다 작으므로 LIS 리스트의 요소를 탐색하며 처음으로 4보다 큰 수의 자리를 대체한다.
-> LIS = [1, 3, 4] -
A[4] = 5: A[4]는 LIS의 마지막 요소(4)보다 크므로 그냥 뒤에append
-> LIS = [1, 3, 4, 5] -
따라서 정답은 [1, 3, 4, 5]로 구성된 길이 4인 LIS가 된다.
그러나 한가지 의문점이 들게 된다. 입력이 [1, 3, 4, 2, 5]인 리스트 A를 생각해보자.
이 리스트 A에 대해 위와 같은 방법을 적용하면 LIS가 [1, 2, 4, 5]와 같이 구성되게 되는데, 이는 리스트 A에서 나올 수 없는 부분 수열이다.
하지만 이는 진짜 LIS를 구성하는 것이 아닌, LIS의 길이만 구하면 되는 것이기에 LIS의 중간 값을 대체하는 것은 길이를 구하는 데에 전혀 지장을 주지 않고, 이러한 방법은 이전에 보았던 [1, 3, 8, 4, 5]처럼 마지막 값을 바꿈으로 길이를 더 늘리는 데에 더 이득이되는 상태를 만들기 위함에 있다.
📒 코드
def binary_search(num):
start = 0
end = len(lis) - 1
while start <= end:
mid = (start + end) // 2
if lis[mid] == num:
return mid
elif lis[mid] < num:
start = mid + 1
else:
end = mid - 1
return start
n = int(input())
a = list(map(int, input().split()))
lis = [a[0]]
for num in a:
if lis[-1] < num: # LIS의 마지막 요소보다 크다면 append
lis.append(num)
else: # LIS의 마지막 요소보다 작거나 같다면 처음으로 크거나 같은 수의 자리에 대체
idx = binary_search(num)
lis[idx] = num
print(len(lis))💭 후기
이 문제 이해를 위해 몇일을 고민했지만 아직 완벽하게 이해가 되지 않는 문제... DP로 풀 때도 그렇고 LIS 유형 문제는 문제를 푸는데도, 이해하는데도 쉽지 않은 것 같다.
🔗 문제 출처
https://www.acmicpc.net/problem/12015
