99클럽 TIL (240819)

> [Middler] Longest Increasing Subsequence

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

 

🔥 다시 풀기 🔥

 

 

문제 풀이 과정

nums 배열이 주어 질 때, 부분 수열을 구하는데 가장 길이가 긴 증가수열 (최장 증가 부분 수열, LIS)을 구하라는 문제이다. 문제 의도는 파악했으나 구현이 어려운 문제였다. 적절한 문제 풀이 방법이 떠오르지 않아 다른 사람의 풀이를 참고했다. 

 

이 문제는 이진탐색, dp를 활용해 풀수 있는데 두 풀이 모두에 대해 기록해두자..!

 

1. Binary Search

1. 주어지는 nums 요소마다 dp 배열에 들어갈 자리를 찾는다. (binary search 이용)
2. dp 배열의 길이와 인덱스가 같다면, 해당 요소가 제일 크다는 의미이므로 수열 증가할 수 있다. 그러므로 dp에 추가한다.
3. dp 배열의 길이와 인덱스가 같지 않다면, 찾은 인덱스가 dp에 존재한는 경우, dp[인덱스]를 num 요소로 바꿔준다.

i	0	1	2	3	4	5	6	7
nums[i]	10	9	2	5	3	7	101	18
dp	[10]	[9]	[2]	[2,5]	[2,3]	[2,3,7]	[2,3,7,101]	[2,3,7,18]

 

2. Dynamic Programming

dp[i] = nums[i]를 마지막 수로 가지는 최장 증가 부분 수열의 개수로 점화식을 작성하면 이렇게 작성할 수 있다. nums[i] 보다 작은 값을 마지막수로 가지는 증가 부분 수열의 개수 + 1 이다.

• nums 배열길이만큼 돌면서 dp[0] ~ dp[i-1] 범위까지 확인해야 한다.
• nums[i] 보다 nums[j]가 작다면 dp[i] = max(dp[i], dp[j]+1) 로 dp테이블을 갱신한다.

 

문제 풀이

python ( binary search )

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:

        # 해당 원소가 위치해야하는 인덱스 리턴
        def binary_search(arr, target, start, end) :
            while start <= end :
                mid = (start+end) // 2
                if arr[mid] == target :
                    return mid
                elif arr[mid] > target :
                    end = mid - 1
                else :
                    start = mid + 1
            return start

        d = []
        for i in range(len(nums)) :
            idx = binary_search(d, nums[i], 0, len(d)-1)
            if idx == len(d) :
                d.append(nums[i])
            else : 
                d[idx] = nums[i]
            
        return len(d)

 

python ( DP )

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:

        dp = [1] * len(nums)
 
        for i in range(len(nums)):
            for j in range(i-1, -1, -1):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

 

시간복잡도

1. binary search : O(NlogN)

2. dp : O(N^2)

 

회고 및 느낀점

이 문제가 주어진다면 내가 풀 수 있을까.. 

 

---

> [Beginner] Missing Number

https://leetcode.com/problems/missing-number/description/

 

 

문제 풀이 과정

우선 주어지는 nums 배열 만큼 개별된 숫자 요소들이 주어질 때, 0 ~ n 까지의 숫자중에 nums에 없는 요소를 리턴하는 문제이다. 로직 동작은 이렇다.

 

1. n만큼 개수를 세기 위해 0으로 배열(d)을 초기화한다.

2. nums 를 for loop 하면서 해당 원소가 있다면 +1한다.

3. 배열 d 에서 세어지지 않은(=0인) 요소의 인덱스를 리턴한다.

 

문제 풀이

python

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        d = [0] * (len(nums)+1)

        for num in nums :
            d[num] = 1
        
        for i,v in enumerate(d) :
            if v == 0 :
                ans = i
        return ans

 

시간복잡도 : O(N)

 

오늘의 회고 및 느낀점

...

 

---

> [Challenger] Maximum Profit in Job Scheduling

https://leetcode.com/problems/maximum-profit-in-job-scheduling/

 

🔥 다시 풀기 🔥