๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์•Œ๊ณ ๋ฆฌ์ฆ˜/LEETCODE

Longest Increasing Subsequence | LeetCode 810 | Python3 ๐Ÿ

๋ฐ˜์‘ํ˜•

 

๐Ÿ“„ ๋ชฉ์ฐจ

     

     

    ๐Ÿค” ๋ฌธ์ œ : Longest Increasing Subsequence | LeetCode 810

    ๋ฌธ์ œ: https://leetcode.com/explore/interview/card/top-interview-questions-medium/111/dynamic-programming/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

     

    ๋ฐ˜์‘ํ˜•