๐ ๋ชฉ์ฐจ
๐ค ๋ฌธ์ : Longest Increasing Subsequence | LeetCode 810
์ฃผ์ด์ง ๋ฆฌ์คํธ ๋ด ๊ฐ์ฅ ๊ธด increasing subsequence ์ ๊ธธ์ด๋ฅผ ์ฐพ๋ ๋ฌธ์ ์ ๋๋ค.
subsequence ๋ ๋ฐฐ์ด์์ ๋ช๊ฐ์ ์์๋ฅผ ์ญ์ ํด์ ๋ง๋ค ์ ์๋ sequnce๋ฅผ ๋งํฉ๋๋ค. (์์๋ ๋ฐ๊พธ์ง ์์ต๋๋ค)
์๋ฅผ๋ค์ด, [2, 1, 3]์ subsequence๋ ์๋์ ๊ฐ์ต๋๋ค.
[2, 1, 3], [2, 1], [2, 3], [1, 3], [2], [1], [3], []
increasing subsequence๋ subsequence ๋ด ์ค๋ฅธ์ชฝ ์์๊ฐ ํญ์ ๋ชจ๋ ์ผ์ชฝ ์์๋ณด๋ค ์ปค์ผ ํฉ๋๋ค.
์๋ฅผ๋ค์ด, [2, 1, 3]์ increasing subsequence๋ ์๋์ ๊ฐ์ต๋๋ค.
[2, 1, 3], [2, 1], [2, 3], [1, 3], [2], [1], [3], []
๐ก ํ์ด
1. Dynamic Programming - ํ์ฌ๊ฐ ~ ๋ฐฐ์ด ๋๊น์ง ๋ง๋ค ์ ์๋ LIS๋ฅผ ์ ์ฅ
์ฃผ์ด์ง ๋ฐฐ์ด์ ๊ฐ์ฅ ์ค๋ฅธ์ชฝ ๊ฐ๋ถํฐ ํ์ธํ๋ฉด์
ํ์ฌ๊ฐ ~ ๋ฐฐ์ด์ ๋๊น์ง ์ค ๋ง๋ค ์ ์๋ LIS๋ฅผ ์บ์์ ์ ์ฅํฉ๋๋ค.
ํ์ฌ๊ฐ์ LIS = ํ์ฌ๋ณด๋ค ์ค๋ฅธ์ชฝ ๊ฐ๋ค ์ค ํ์ฌ๊ฐ๋ณด๋ค ํฐ ๊ฐ๋ค์ LIS ์ค ๊ฐ์ฅ ํฐ
ex) nums = [10, 9, 2, 5, 3, 7, 101, 18]
1) 18 - ๋ค์ ์๋ฌด ์ซ์ ์์ผ๋ฏ๋ก LIS๋ 1์ ๋๋ค.
2) 101 - ๋ค์ 18์ด ์์ง๋ง 101๋ณด๋ค ์์ ์์ด๋ฏ๋ก Increasing์ด ์๋๋๋ค. ๋ฐ๋ผ์ LIS๋ 1์ ๋๋ค.
3) 7 - ๋ค์ 101๊ณผ 18 ๋ชจ๋ 7๋ณด๋ค ํฝ๋๋ค.
7์ LIS = max( 101์ LIS, 18์ LIS) +1= 2
[7, 101], [7, 18] ๋ชจ๋ 7์์ ์์ํ๋ longest increasing subsequence์ ๋๋ค.
4) 3 - ๋ค์ 7, 101, 18 ๋ชจ๋ 3๋ณด๋ค ํฝ๋๋ค.
3์ LIS = max( 7์ LIS, 101์ LIS, 18์ LIS) +1
= max( 2, 1, 1) +1 = 3
[3, 7, 101] ๋๋ [3, 7, 18]์ด 3์์ ์์ํ๋ longest increasing subsequence์ ๋๋ค.
4) 5 - ๋ค์ 7, 101, 18 ์ด 5๋ณด๋ค ํฝ๋๋ค.
5์ LIS = max( 7์ LIS, 101์ LIS, 18์ LIS ) +1
= max( 2, 1, 1 )+1 = 3
[5, 7, 101] ๋๋ [5, 7, 18]์ด 3์์ ์์ํ๋ longest increasing subsequence์ ๋๋ค.
4) 2 - ๋ค์ 5, 3, 7, 101, 18 ์ด 2๋ณด๋ค ํฝ๋๋ค.
5์ LIS = max( 5์ LIS, 3์ LIS, 7์ LIS, 101์ LIS, 18์ LIS) +1
= max( 3, 3, 2, 1, 1) = 4
[2, 5, 7, 101]
[2, 5, 7, 18]
[2, 3, 7, 101]
[2, 3, 7, 18]
์ด 2์์ ์์ํ๋ longest increasing subsequence์ ๋๋ค.
from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
print(nums)
cache = [1]*(len(nums))
maxValue = 0
for i in range(len(nums)-1, -1, -1):
for j in range(i+1, len(nums)):
if nums[j] > nums[i]: cache[i] = max(cache[i], cache[j]+1)
maxValue = max(cache[i], maxValue)
# print("finding LIS for ",nums[i], "... ", cache[i], cache)
return maxValue
Time Complexity
O(N^2)
๊ฐ ์์๋ง๋ค ๋ค์์๋ ๋ชจ๋ ์์๋ค์ ๊ฐ๋ค์ ํ์ธํด์ผ ํ๋ฏ๋ก ์ด์คํฌ๋ฃน ์ฆ O(N^2)์ด ๋ฉ๋๋ค.
2. O(NlogN) ํ์ด
๋ง๋ค์ด์ง๋ LIS๊ธธ์ด๊ฐ ๊ฐ๋ค๋ฉด ๋ ํฐ ๊ฐ์ ๊ธฐ์ค์ผ๋ก ํ๋๊ฒ ์ ๋ฆฌํ๋ค ๋ผ๋ ์ ์ ํ์ฉํ์ต๋๋ค.
LIS๊ธธ์ด์ ์์๊ฐ์ ์บ์ฑํด๊ฐ๋ฉฐ ์ฝ์ ์์น๋ฅผ logN๋ง์ ์ฐพ์๊ฐ๋ ๋ฐฉ์์ ๋๋ค.
bisect_left๋ ์ค๋ฆ์ฐจ์ ๋ฐฐ์ด์์ ์ฌ์ฉํ๋ ํจ์๋ผ์ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌํ๊ธฐ ์ํด target_num์ ์์๋ฅผ ์ทจํด ์ ์ฅํ์ต๋๋ค.
ex) nums = [10, 9, 2, 5, 3, 7, 101, 18]
1) 18
LIS(18) = 1 ์ด๋ฏ๋ก cache[0] = -18
2) 101
bisect_left ๋ฅผ ํตํด cache[0] ์๋ฆฌ์ -101์ ์ฝ์ ํด์ผ ํจ์ ์๊ณ ์์
๊ธฐ์กด์ ์ ์ฅ๋์ด์๋ 18๋ณด๋ค 101์ด ๋ ํฌ๋ฏ๋ก cache[0] = -101๋ก ์ ๋ฐ์ดํธ
* ์ดํ์ 18~101์ฌ์ด์ ๊ฐ์ด ๋ค์ด์ค๋ฉด 18๋ก๋ LIS๋ฅผ ๋ง๋ค ์ ์์ง๋ง 101๋ก๋ ๋ง๋ค ์ ์์
[20, 18] LIS์๋
[20, 101] LIS
์ฆ, 101๋ก ๋ง๋ค ์ ์๋ LIS๋ 18๋ก ๋ง๋ค ์ ์๋ LIS๋ฅผ ๋ชจ๋ ํฌํจํจ
3) 7
bisect_left ๋ฅผ ํตํด cache[1] ์๋ฆฌ์ -7์ ์ฝ์ ํด์ผ ํจ์ ์ ์ ์์.
๊ทธ ์๋ฆฌ๋ ๋น์์ผ๋ฏ๋ก ๋ฐ๋ก ์ฝ์ .
4) 3
bisect_left ๋ฅผ ํตํด cache[2] ์๋ฆฌ์ -3์ ์ฝ์ ํด์ผ ํจ์ ์ ์ ์์.
๊ทธ ์๋ฆฌ๋ ๋น์์ผ๋ฏ๋ก ๋ฐ๋ก ์ฝ์ .
4) 5
bisect_left ๋ฅผ ํตํด cache[2] ์๋ฆฌ์ -5์ ์ฝ์ ํด์ผ ํจ์ ์ ์ ์์.
๊ธฐ์กด์ ์ ์ฅ๋์ด์๋ 3๋ณด๋ค 5๊ฐ ๋ ํฌ๋ฏ๋ก cache[2] = -5๋ก ์ ๋ฐ์ดํธ
...
from bisect import bisect_left
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
cache = []
cacheLen = 0
for i in range(len(nums)-1, -1, -1):
target_num = -nums[i]
idx = bisect_left(cache, target_num)
if idx == cacheLen:
cache.append(target_num)
cacheLen += 1
else: cache[idx] = target_num
return cacheLen
'์๊ณ ๋ฆฌ์ฆ > LEETCODE' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
Remove Invalid Parentheses | LeetCode 301 | Python3 ๐ (0) | 2022.08.02 |
---|---|
Task Scheduler | LeetCode 826 | Python3 ๐ (0) | 2022.03.17 |
Majority Element | LeetCode 824 | Python3 ๐ (0) | 2022.03.16 |
Divide Two Integers | LeetCode 820 | Python3 ๐ (0) | 2022.03.15 |
Search a 2D Matrix II | LeetCode 806 | Python3 ๐ (0) | 2022.03.14 |