•
문제 설명 : 주어진 숫자 배열 중, 엄격하게 증가되는 수열의 최대 길이를 반환한다.
•
풀이 방법
◦
결론적으로 말하면, 제목에 그대로 나와있는 LIS(최장 증가 수열)을 푸는 방법은 따로 존재한다.
◦
우선 처음에는 DP 방식으로 풀었다.
•
시간복잡도 :
•
성공 코드(DP) →O(N^2)
현재 숫자보다 작은 경우 가장 긴 수열의 길이를 미리 dp에 저장한 후, 가져와 사용하는 것이다.
하지만 이것은 N^2 만큼 길이가 소요된다. 정확하게는 N(N-1) / 2 → 1 + … + N 이다.
from collections import defaultdict
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[j] + 1, dp[i])
return max(dp)
Python
복사
•
성공 코드(LIS) → O(NlogN)
이 기법을 설명하면, 주어진 배열에서 각 요소를 적절한 위치에 삽입하여 현재까지의 증가하는 부분 수열을 유지하고 그 길이를 반환하는 방법이다.
위 내용을 보면 알 수 있듯, 각 요소마다 현재 부분 수열의 이분 탐색을 진행하는 방식이다.
그래서 Follow Up 힌트처럼, N(각 요소) * logN(이분 탐색)인 것이다.
여기서 binary_search_left 메서드는 bisect 모듈의 bisect_left(iter, value) 메서드로 변경하여 사용할 수 있다.
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
lts = []
def binary_search_left(iter, value):
left, right = 0, len(iter) - 1
while left <= right:
mid = (right + left) // 2
if iter[mid] < value:
left = mid + 1
else:
right = mid - 1
return left
for num in nums:
if not lts:
lts.append(num)
continue
if lts and lts[-1] < num:
lts.append(num)
else:
index = binary_search_left(lts, num)
lts[index] = num
return len(lts)
Python
복사