LIS(최장 증가 수열)
LIS란
LIS를 간단하게 설명하자면, 가장 긴 부분 수열 이라고 해석하면 쉽습니다. 이것의 가장 기본 문제로는 백준2352 번이 있으니, 설명을 듣고 이해가 가거나 안 가더라도 풀어보면 어떤 것을 요구하는지 잘 알 수 있습니다. 사진으로 설명을 할 것이니 다음 사진을 보겠습니다.
이미지1
위의 사진과 같은 배열이 있는데 [1,2,7], [2,7,8], [2,7,6, 15] 같은 부분 배열 중에서 인덱스 순서도 만족하면서, 값도 오름차순을 만족 하는 가장 긴 배열 을 찾는 것이다. 이 그림에서는 답이 [1, 2, 7, 8, 15] 즉 길이가 5인 배열이 답이 될 것이다. 위와 같이 배열의 크기가 작을 때는 내가 직접 하는 것이 빠르겠지만, 만약 배열의 크기가 10,000이 넘는다면 어떡할 것인가?
제일 첫번째 방법인 이중포문으로 재귀를 돌면서 찾는 방법을 생각할 것이다. 만약에 그럴 경우에는 O(N^2)이 되어 큰 수일 수록 더욱 시간이 오래 걸린다는 것은 자명하다.
자, 그럼 2번째 방법이 무엇이냐? LIS를 이용하는 것이다. 아래 그림을 먼저 보고 나면 설명이 더 쉬울 것이다.
이미지2
초기에는 주어진 배열에 있는 수보다 제일 작은수를 먼저 넣어준다. 나중에 인덱스 관리하기도 편하고, 조건에 맞게 쉽게 넣어줄 수 있기 때문이다. 1을 삽입할 경우에는 제일 마지막에 있는 -1보다 크기 때문에 python의 경우에는 append()를 해주면 된다. 그리고 length를 1증가 시킨다. 3을 삽입시킬 경우에도 마찬가지다. 그러나 2를 삽입 하는 경우를 봐보자. 2는 인덱스가 작은 3보다 값이 작다. 그러면 우리가 원하는 부분배열을 만족하지 못한다. LIS에서 1차적으로 구하려는 값은 배열의 길이이기 때문에, 우리는 길이에만 신경을 쓰면된다. 2를 삽입할 경우에는 배열의 마지막 값인 3보다 작으므로, 2가 들어갈 곳을 배열의 처음부터 찾아야한다. 우리가 찾아야할 자리는, 지금의 인덱스가 n이라면, Array[n-1] 값보다는 크고 , Array[n+1] 값 보다는 작은 값을 만족하는 자리를 구하면 된다. 이렇게 하다 보면, 우리가 원하는 길이를 알 수 있을 것이다. 그러나 정확히 어떤 배열의 값들이 그 길이를 만족하는지는 위와 같은 방법으로는 구할 수 없다. 이것에 대해서는 다음에 또 포스팅을 해보겠다.
혹시 이해가 안됐으면, 위에서 언급한 문제를 풀어보면 어느것을 요구하는지 알 수 있을것이다.
array = [1,3,2,7,8,6,15]
new_array = []
length = 0
for i in range(len(array)):
if new_array[-1] < array[i]:
new_array.append(i)
length += 1
else:
lower_bound() #위에서 말한 자리찾는 함수 (직접 구현해보길 바란다)
O(NlogN)의 시간으로 문제를 해결할 수 있다! 재미있는 아이디어 잊지말장~!