sort 썸네일형 리스트형 max-heap, min-heap - 이진트리의 활용 heap - 이진트리의 활용 실제로 상당히 유용하게 쓰이는 heap에 대해서 알아보도록 하자. heap이란 이진트리를 활용한 상당히 재밌는 구조이다. 주로 max-heap, min-heap으로 가장 큰값 또는 가장 작은 값을 빠르게 찾기 위해서 사용이된다.min, max 뿐만 아니라 원하는 조건대로 compare을 하면 가장 원하는 값을 빠른시간에 뽑아낼 수 있다. 아직 설명하기 전이지만 , sort를 한 후에 골라내는게 더 빠르지 않냐 라는 생각을 할 수 도있다.이 heap의 장점이라면, 삽입, 삭제를 했을 때 추가적인 sort가 필요없다는 것이다.이 정도로 서론을 끝내고 직접 적으로 heap에 대해서 알아보자. 1. heap?heap이란 최대값 또는 최소값을 빠르게 찾기위해서 고안된 트리모양의 자료구.. 더보기 이진탐색(Binary Search)와 Parametric Search 이진탐색(Binary Search)와 Parametric Search 1. 이진탐색1.1 기본 아이디어우리가 원하는 값을 찾고 싶을 때에는 정말 간단하게 생각하면, 모든 값들을 하나씩 보면서 맞는지 아닌지 확인는 방법이 직관적인 방법이라고 할 수 있다. 하지만 이렇게 찾는 것은 가장 마지막에 원하는 값이 있을 경우, 모든 값 들을 한번 씩 살펴보아야 하기 때문에, O(N)으로 볼 수 있다. 그렇다면 좀더 효율적인 방법은 없을까? 에서 시작한 것이 바로 이진탐색(Binary search)이다. 이진탐색(Binary search)의 경우는 결과적으로 보면 O(logN) 만에 원하는 값을 찾을 수 있는데, 그 이유는 정렬이 되있다는 가정이 있기 때문이다. 아래의 그림을 보면서, 왜 그러한지 직관적으로 이해를 .. 더보기 이전 1 다음
