LIS (longest increasing subsequence)

많은 변형을 양산하는 구조이다. 컨셉을 제대로 이해할 필요가 있다. 결론적으로, DP 이지만 더 발전된 형태로 풀도록 하는 것이 요즘의 경향인 것 같다.

아래 array에서 가장 긴 subsequence (연속될 필요는 없는 배열 원소들의 부분 수열) 의 길이를 찾는 문제가 있다고 하자.

nums = [5, 6, 7, 8, 1, 2, 3]

https://leetcode.com/problems/longest-increasing-subsequence/

Longest Increasing Subsequence - LeetCode

이를 어떻게 골라야 할까.

DP

def lengthOfLIS(nums: List[int]) -> int:
    n = len(nums)
    dp = [1 for _ in range(n)]
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

각 원소가 위치한 곳이 부분열이 끝나는 점이라고 정의하고, 각 부분열의 최대 길이를 dp에 저장하자. 부분열이 끝나는 점에 따라 dp의 원소를 정의했으므로, 부분열이 끝나는 점의 원소 하나만(앞의 것들은 포함하지 않고) 포함한다고 보고 그 최소 길이는 1로 두어도 무방하다.

1번째 위치(즉 두번째 원소) 부터 진행[i]하면서, 자기보다 더 앞의 것들을 모두 탐색[j]하여 만일 작은 것이 있다면 그 위치의 dp값에 1을 더하여 dp[j] + 1 나의 dp값인 dp[i] 보다 크다면 그 값으로 업데이트 한다. 자기 위치에서 끝나는 부분열 중 최대 길이를 담은 것이 dp이므로, 그 끝값만 보면, 더 나중의 위치에서 볼 때 해당 부분열을 내 앞에 붙일지 여부를 결정하는데 충분하다. 왜냐면 부분열의 최대 '길이'만 관심이 있기 때문이다.

시간복잡도는 O(n2) 이다.

Patience Sorting I (sequential search)

카드게임 이름에서 유래했다. 예를 들어, nums = [0, 8, 4, 12, 2, 10, 6, 14] 가 있다고 하면, 다음과 같이 계산하는 것이다. 역시 O(n2).

# nums의 원소를 앞에서부터 계속 살펴보면서 아래와 같이 subs를 형성한다.
# 이 subs는 LIS의 길이를 구하기 위한 것이지 그 자체로 LIS인 것은 아니다.
0		# 맨 처음은 그냥 추가한다
0 8		# 0 < 8 이므로 추가한다
0 4		# 4를 subs[-1]과 비교하면 더 작으므로 8과 바꿈
0 4 12		# 12 > subs[-1] 이므로 뒤에 붙임
0 2 12		# !! 여기서 주의 !! 2는 subs의 앞에서부터 찾다보면 4가 처음으로 4>2 이렇게 되는 원소이다. 바꾼다.
0 2 10		# 10도 마찬가지로 12를 바꾼다
0 2 6		# 6도 마찬가지
0 2 6 14	# 14는 6보다 크므로 바꿈

Patience Sorting II (binary search)

위의 방법은 nums를 차례로 보는 와중에 subs도 앞에서 부터 순차적으로 탐색해야 한다는 단점이 있다. nums에서 뽑은 새 원소 대비 subs에서 최초로 더 커지는 원소를 찾을때(맞바꾸기 위해) O(n) 시간이 든다는 말이다. 이를 이분탐색으로 O(logn)으로 바꿀 수 있다.

from bisect import bisect_left
def lengthOfLIS(nums):
    subs = []
    for n in nums:
        if len(subs) == 0: subs.append(n)
        if subs[-1] < n:   subs.append(n)
        else:
            i = bisect_left(subs, n)   # subs 내에서 n보다 큰 값 중 가장 작은 값의 index를 찾음
            subs[i] = n                # 조직에서 나의 바로 윗 선임의 자리를 찾는다고 생각하자
    return len(subs)

결국 시간복잡도는 O(nlogn) 이다.

연관문제

https://leetcode.com/problems/russian-doll-envelopes/

Russian Doll Envelopes - LeetCode