TIL-231005(자료구조 & 알고리즘 3주차)

📝오늘 공부한 것

• 프로그래머스 문제풀기
• 스파르타코딩클럽 자료구조 & 알고리즘 3주차 강의 듣기
• 항해 커리어톤 참여
• 이력서 수정하기

 

알게 된 점❗

[ 이진 탐색 트리 ]

• 부모 기준 왼쪽에는 작은 값, 오른쪽에는 큰 값을 가지는 이진 트리
• 평균적으로 탐색의 시간복잡도는 O(logN). 치우친(skewed) 경우 O(n). 따라서 균형이 중요
• 자가균형 이진탐색 트리는 AVL, 레드블랙 트리 등이 있다.
• 자바의 해시맵이 체이닝 시 연결리스트와 함께 레드블랙 트리를 병행해 저장한다.

 

[ 이진탐색의 효율성 ]

이진탐색

배열이 정렬되어있을 경우, 절반식 줄여나가면서 탐색하는 기법

이진탐색의 효율성

• 1억개 목록을 선형탐색할 때, 1억 번을 연산해야 한다. 이진탐색으로 찾는다면, 27번안에 찾을 수 있다.
• 이진탐색을 위해서는 정렬되어 있어야 한다.

[ 이진 검색 ]

이진검색

//구현
def binary_search(nums, target):
    def bs(start, end):
        if start > end:
            return -1

        mid = (start + end) // 2

        if nums[mid] < target:
            return bs(mid + 1, end)
        elif nums[mid] > target:
            return bs(start, mid - 1)
        else:
            return mid

    return bs(0, len(nums) - 1)


assert binary_search(nums=[-1, 0, 3, 5, 9, 12], target=9) == 4
assert binary_search(nums=[-1, 0, 3, 5, 9, 12], target=2) == -1

//내장
def binary_search_builtin(nums, target):
    idx = bisect.bisect_left(nums, target)
		# idx == len(nums) 가능하기 때문.
		"""Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """
    if idx < len(nums) and nums[idx] == target:
        return idx
    else:
        return -1