시간이 빠르다 벌써 항해가 3주차가 지나갔다.
나에게 알고리즘은 여전히 어렵고 난해하다
하지만 난 여전히 오늘도 게더를 들어간다.
이번주 WIL 을 작성하고 다시 공부를 더 하기 위해서...
1. 힙 자료구조
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
- 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
- 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다.
- 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
- 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
- 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
힙자료구조 를 구현해서 썼을때는 좀복잡해서 어려웠지만 파이썬에 heapq 라이브러리를 사용했을 경우 쉽게 사용할 수 있어서 좋았습니다.
2.이진탐색
이진 탐색 알고리즘(二進探索algorithm, Binary Search Algorithm)은 컴퓨터과학, 수학 등에서 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다.
