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

[오늘의 학습 키워드 및 문제]
- 리트코드의 "Longest Increasing Sequence" 문제를 풀었다.
- 오늘 주제는 이분 탐색인데, DP로도 풀 수 있는 듯 보였다.
- 아 배고파서 기운 없다.

[나의 코드]

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        
        def binary_search(result, num):
            left, right = 0, len(result) - 1
            while left <= right:
                mid = (left + right) // 2
                if result[mid] < num:
                    left = mid + 1
                else:
                    right = mid - 1
            return left

        result = []

        for num in nums:
            x = binary_search(result, num)
            
            if x == len(result):
                result.append(num)
            else:
                result[x] = num
        
        return len(result)

설명하기 귀찮은데. To. 멍청한 미래의 나에게

일단 빈 배열을 하나 만들어 준다.
nums 배열에 있는 걸 하나씩 돌릴 거다.

result 배열에서 num을 찾는다. 
만약 그 인덱스가 배열과 길이가 같다면 넣어준다. 즉, 마지막 배열의 수보다 크다라면 뜻이다.
아니라면 마지막 원소를 바꿔준다.

다 돌면 result 배열의 길이를 반환한다.

그러면 여기서 질문이 나온다. 왜 인덱스와 배열의 길이와 일치할 때 넣느냐?
가장 긴 증가하는 부분 수열을 확장하기 위해서다.
예를 들어, result가 [2, 3, 7]이고, 새로운 숫자 10이 들어오면, 10을 추가하여 [2, 3, 7, 10]으로 확장하는 것이 가능하다.
그냥 print로 값을 찍어 보면서 보는 게 이해가 가장 빠르다.

이분 탐색을 머리로 돌려보면 왜 저러는지는 안다. 아는데 설명이 어렵다.

난 이런 까다로운 문제 싫어하는데, 기라면 기어야 하는 나의 현실이 안타깝다.

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

        for num in nums[1:]:
            if num > result[-1]:
                result.append(num)
            else:
                x = bisect.bisect_left(result, num)
                result[x] = num
        
        return len(result)

이거는 이분 탐색 라이브러리를 써서 푼 코드다. 그냥 참고용.
그리고 코드 저렇게 안 써도 된다. 근데 이해하기는 얘가 더 편하다. 그냥 이거 보는 게 나을지도?

[오늘의 회고]
- 음.. 문제가 평이했다.
- 밥을 먹으러 가야겠다. 끝!