99클럽 코테 스터디 29일차 TIL + 이분탐색

오늘의 문제 - 이분탐색

LeetCode - 300. Longest Increasing Subsequence

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

 

---

풀이 및 접근 방식

브루트 포스 + DP

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n

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

        return max(dp)

풀이

1. dp 배열은 각 위치에서 끝나는 가장 긴 증가 부분 수열의 길이를 저장한다.
2. 각 원소 nums[i]에 대해 그 이전의 모든 원소 nums[j]를 확인하며, 만약 nums[i] > nums[j]인 경우 dp[i]를 갱신한다.
3. 마지막으로 dp 배열에서 가장 큰 값을 반환한다.

시간 복잡도

이중 for 문을 사용하기 때문에 시간 복잡도는 O(n^2)이다.

 

이분탐색 풀이

import bisect

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        lis = []
    
        for num in nums:
            pos = bisect.bisect_left(lis, num)
            if pos < len(lis):
                lis[pos] = num
            else:
                lis.append(num)
    
        return len(lis)

풀이

1. lis 리스트는 현재까지 찾은 증가하는 부분 수열을 저장한다.
2. 각 원소 num에 대해 lis 리스트에서 해당 원소가 삽입될 위치를 이분 탐색(bisect_left)을 통해 찾는다.
3. 만약 num이 이미 lis에 있는 값보다 크다면, 그 위치에 num을 대체한다. 그렇지 않으면 lis의 끝에 num을 추가한다.
4. 최종적으로 lis의 길이가 가장 긴 증가하는 부분 수열의 길이가 된다.

시간 복잡도

bisect_left 함수가 이분 탐색을 수행하므로, 각 원소에 대해 O(log n)의 시간이 걸리며, 전체 배열에 대해 O(n log n)의 시간이 소요된다.

 

bisect 라이브러리를 이용하지 않은 풀이는 아래와 같다.

def binary_search(lis, num):
    left, right = 0, len(lis) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if lis[mid] < num:
            left = mid + 1
        else:
            right = mid - 1
    
    return left

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

        for num in nums:
            pos = binary_search(lis, num)
            if pos < len(lis):
                lis[pos] = num
            else:
                lis.append(num)

        return len(lis)

---

회고

bisect 라는 라이브러리가 있는 줄 처음 알았다.

bisect

이진탐색 알고리즘을 사용하여 정렬된 리스트에서 효율적으로 원소를 삽입할 위치를 찾거나, 해당 위치에 원소를 삽입하는 기능 제공

• bisect.bisect_left(a, x, lo=0, hi=len(a)):
  • 이 함수는 리스트 a에서 x가 삽입될 수 있는 가장 왼쪽(최소 인덱스)의 위치를 반환한다.
  • lo와 hi 매개변수를 통해 탐색 범위를 제한할 수 있다.
• bisect.bisect_right(a, x, lo=0, hi=len(a)):
  • bisect_left와 유사하지만, x가 삽입될 수 있는 가장 오른쪽(최대 인덱스)의 위치를 반환한다. 동일한 값이 여러 개 있는 경우 마지막 값의 바로 뒤를 가리키게 된다.
  • bisect라는 이름으로도 호출할 수 있다. (bisect.bisect(a, x, lo=0, hi=len(a))는 bisect_right와 동일한 기능을 한다).
• bisect.insort_left(a, x, lo=0, hi=len(a)):
  • 이 함수는 bisect_left가 반환하는 위치에 x를 삽입한다. 리스트가 이미 정렬된 상태를 유지할 수 있게 한다.
  • a.insert(pos, x)와 같은 효과를 가지지만, 이분 탐색을 통해 위치를 찾기 때문에 성능이 더 우수하다.
• bisect.insort_right(a, x, lo=0, hi=len(a)):
  • insort_left와 비슷하지만, bisect_right가 반환하는 위치에 x를 삽입한다.