300. Longest Increasing Subsequence ★

300. Longest Increasing Subsequence

 

https://youtu.be/cjWnW0hdF1Y?si=DCsJr16gb5K6nTle

 

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        """
        n = len(nums)
        dp = [0] * n, nums 개수만큼        
        우선, 초기값으로 
            dp[n-1] = 1 왜냐, 마지막은.. 자기자신..
        dp[m] = max(1, 1 + dp[m+1] if nums[m] < nums[m+1].. nums[n-1] else 1) 
            이후꺼들보다, 내가 작으면 거기에 내가 더해지는 거니, 1 + dp[n+1],... 
            아니면, 나 자신밖에 안될테니. 1이고.
        """
        # LIS 배열 초기화: 각 위치에서 시작하는 LIS 길이를 저장
        LIS = [1] * len(nums)

        # nums 배열을 거꾸로 순회하면서 LIS 계산
        for i in range(len(nums) - 1, -1, -1):  # 뒤에서부터 순회
            for j in range(i + 1, len(nums)):  # i 이후의 요소 탐색
                if nums[i] < nums[j]:  # 현재 값이 이후 값보다 작다면
                    # LIS[i]를 업데이트: 기존 LIS[i]와 1 + LIS[j] 중 큰 값 선택
                    """
                    # nums[i]를 포함하는 LIS[i] 
                    # nums[i] 부터 시작하는 LIS, 즉, 1+LIS[j] 중 큰 값
                    """
                    LIS[i] = max(LIS[i], 1 + LIS[j])
        
        # LIS 배열 중 가장 큰 값 반환: 전체 배열의 최장 증가 부분 수열 길이
        return max(LIS)

 

이 문제는 "Longest Increasing Subsequence (LIS)", 즉 최장 증가 부분 수열 문제입니다. 아래에서 문제를 상세히 설명하겠습니다.

---

문제 정의

입력: 정수 배열 nums
출력: 배열 nums에서 증가하는 부분 수열 중 가장 긴 길이

---

조건

1. 증가 부분 수열:
   • 배열에서 임의의 원소를 선택하되, 선택한 원소들은 오름차순이어야 합니다.
   • 반드시 연속할 필요는 없습니다. 예를 들어, [10, 9, 2, 5, 3, 7, 101, 18]에서 [2, 3, 7, 101]이 증가 부분 수열이 될 수 있습니다.
2. 길이만 반환:
   • 실제로 증가 부분 수열을 반환할 필요는 없으며, 그 길이만 구하면 됩니다.

 

풀이 방법

1. 브루트포스 (모든 경우 탐색)

• 모든 가능한 증가 부분 수열을 찾고 그중 가장 긴 것을 선택.
• 비효율적: 시간 복잡도가 O(2n)O(2^n)O(2n).

2. 동적 프로그래밍 (DP) (위 코드)

• 배열 nums의 각 위치에서 끝나는 증가 부분 수열의 최대 길이를 저장하는 dp 배열 사용.
• 점화식:
  • dp[i] = max(dp[i], dp[j] + 1) (단, nums[j] < nums[i]이고 j<ij < ij<i)
  • 즉, i번째 원소 이전에 증가 부분 수열이 있으면 그 길이를 현재 값과 합쳐 갱신.
• 시간 복잡도: O(n2)O(n^2)O(n2).

3. 이진 탐색을 이용한 최적화

• DP + 이진 탐색을 사용하여 LIS를 계산.
• 시간 복잡도: O(nlog⁡n)

 

이 문제를 이진 탐색으로 최적화하여 풀 수 있습니다. 이 방법은 시간 복잡도를 O(nlog⁡n)로 줄일 수 있는 효율적인 접근 방식입니다.

---

이진 탐색을 이용한 풀이 방법

아이디어

1. 증가 부분 수열을 저장할 배열 sub를 유지합니다.
   • 이 배열은 LIS의 길이를 간접적으로 나타냅니다.
   • 반드시 최종 LIS를 나타내지는 않지만, 길이는 정확히 유지됩니다.
2. 배열 nums의 각 원소를 순회하면서:
   • sub 배열에서 현재 원소가 삽입될 위치를 이진 탐색으로 찾습니다.
   • 삽입 위치:
     • 기존 원소를 교체하면 LIS의 후보를 최소화할 수 있음.
     • 새로운 위치에 삽입하면 LIS 길이가 늘어납니다.
3. 최종적으로 sub의 길이가 LIS의 길이입니다.

핵심 논리

• 이진 탐색을 통해 적절한 위치를 빠르게 찾습니다:
  • 만약 nums[i]가 sub의 마지막 원소보다 크면, nums[i]를 추가.
  • 그렇지 않으면, nums[i]와 같거나 더 큰 값이 있는 위치를 찾아 교체.

from bisect import bisect_left
from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        sub = []  # 증가 부분 수열 후보를 저장
        
        for num in nums:
            # sub 배열에서 num이 들어갈 위치를 이진 탐색으로 찾기
            pos = bisect_left(sub, num)
            
            if pos == len(sub):
                # num이 sub 배열의 마지막 원소보다 크다면, 새로 추가
                sub.append(num)
            else:
                # num이 들어갈 위치의 값을 num으로 교체
                sub[pos] = num
        
        # sub 배열의 길이가 LIS의 길이
        return len(sub)

 

주의

• sub 배열은 LIS의 실제 값을 포함하지 않을 수 있습니다.
  • 예: nums = [3, 5, 7, 2, 8] → sub = [2, 5, 7, 8].
• 하지만 sub의 길이는 항상 LIS의 길이와 같습니다.

이 방법은 최적화된 풀이로, 대규모 입력에서도 효율적으로 동작합니다! 😊

 

이진 탐색을 배열로 구현한 LIS 풀이

 

from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        def binary_search(sub, target):
            """
            이진 탐색으로 target이 삽입될 위치를 찾음.
            sub 배열에서 target보다 크거나 같은 첫 번째 위치 반환.
            """
            left, right = 0, len(sub) - 1
            while left <= right:
                mid = (left + right) // 2
                if sub[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return left
        
        sub = []  # LIS를 저장할 배열
        
        for num in nums:
            pos = binary_search(sub, num)  # 이진 탐색으로 삽입 위치 찾기
            if pos == len(sub):
                sub.append(num)  # 새로운 LIS 후보 추가
            else:
                sub[pos] = num  # 기존 값을 num으로 대체
        
        return len(sub)  # sub 배열의 길이가 LIS의 길이