스파르타 코딩 3주차 WIL

15장 힙

힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)이다

최대 힙

항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조입니다.
다시 말하면 부모 노드의 값이 자식 노드의 값보다 항상 커야 합니다.
그러면 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 가겠죠!
따라서 최대의 값들을 빠르게 구할 수 있게 되는 것입니다.

최소 힙

최대 힙의 정 반대이다
항상 작은 값이 상위 레벨에 있고 큰 값이 하위 레벨에 있도록 하는 자료구조
그러면 가장 작은 값은 모든 자식보다 작아야 하기 때문에, 가장 위의 값이 최솟값이 된다

특징

• BST(이진탐색트리)와 다르다. 좌, 우 자식의 위치가 대소관계를 반영하지 않음.
• 계산 편의를 위해 인덱스는 1부터 사용한다. (parent: x, left: 2x, right: 2x+1)

최대 힙 - 삽입 알고리즘

원소를 추가하거나 삭제할 때도 힙의 규칙을 성립 해야한다

1. 원소를 맨 마지막에 넣습니다
2. 그리고 부모 노드와 비교합니다. 만약 더 크다면 자리를 바꿉니다
3. 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2의 과정을 반복합니다

최대 힙 - 추출 알고리즘

루트 노드만 추출/삭제 가능
스택과 같이 맨 위에 있는 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할 수는 없습니다!

1. 루트 노드와 맨 끝에 있는 원소를 교체한다.
2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다.
3. 변경된 노드와 자식 노드들을 비교합니다. 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꿉니다.
4. 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지, 3의 과정을 반복합니다.
5. 2에서 제거한 원래 루트 노드를 반환합니다.

시간 복잡도

삽입은 원소를 맨 밑에 넣어서 꼭대기까지 비교하면서 올리고,
추출은 작은 값으로 교체된 루트 노드와 가장 큰 자식을 바꿔가며 내립니다.
완전 이진트리의 최대 높이는 O(log_2(N)) 이기에, 반복하는 최대 횟수도 O(log_2(N)) 입니다.
맥스 힙의 원소 추가는 O(log_2(N)) 만큼의 시간 복잡도를 가진다고 분석할 수 있습니다.

heapq

파이썬의 내장함수이고
0부터 시작하는 인덱스를 사용한다

heapq.nlargest(n, iterable, key=None)
"""
iterable에 정의된 데이터 집합에서 n개의 가장 큰 요소로 구성된 리스트를 반환합니다

18장 이진 탐색

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

내장함수 bisect

bisect.bisect_left(nums :list , target: int)
##원하는 target 값의 index 하나를 반환한다

예외상황

1. 원하는 target 값이 여러개 - target과 값이 같은 index중 가장 작은 index 반환
2. 원하는 target 값이 리스트에 없을 때 - target값보다 큰 첫번째 값의 index 반환
3. 원하는 target 값이 리스트의 모든 값보다 클 때 - 배열의 길이 len(nums) 반환 (배열내에 없음)
4. 원하는 target 값이 리스트의 모든 값보다 작을 때 - (-1) 반환 (배열내에 없음)

import bisect
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

## 예외1. 만약 [-1,1,3,3,5]배열에서 3를 찾는다면 첫 번째 3의 index 2 반환
## 예외2. 만약 [-1,1,3,3,5]배열에서 2를 찾는다면 1,3사이까지 찾은 후 3의 index 2 반환
## 예외3. 만약 [-1,1,3,3,5]배열에서 2를 찾는다면 1,3사이까지 찾은 후 3의 index 2 반환
## 예외4. 만약 [-1,1,3,3,5]배열에서 9를 찾는다면 5반환
## 예외5. 만약 [-1,1,3,3,5]배열에서 -2를 찾는다면 -1반환