퀵 정렬은 평균적으로 가장 빠르고, 이해하기도 쉬운 정렬 알고리즘이다. 이 알고리즘의 핵심 알고리즘은 partition 이다. 흔히 pivot 이라고 부르는 메소드다. partition algorithm 은 Lumuto, hoare 두개의 방법이 존재한다. 최악의 경우에서 hoare 가 더 좋은 성능을 가진다. 하지만, hoare 는 구현하기 굉장히 까다...
heap 의 사전적 의미는 더미 라는 뜻이다. 대충 쌓아 올린다는 뜻이다. 그런데 꺼내는건 쉽지 않다. heap push 와 pop 을 간단하게 구현했다. 인터넷에 거창한 구현들이 많다. 다들 너무 거창하고 주석도 너무 자세하다. min heap 의 간단한 구현체다. 이 구현은 0번 인덱스 까지 사용한다. 그래서 parent 를 계산하는 식이 조금 다를 수...
바이너리 서치는 매우 효율 적이고, 이해하기도 쉽기 때문에 많은 자료구조, 알고리즘 서적의 처음에 등장한다. 구현은 매우 간단하다. 하지만 종종 실수한다. 바이너리 서치와 비슷한 bisect 구현도 추가한다. 구현을 찾아보다 보면 mid 구하는 식에 가 쓰이기도 하고, 이 쓰이기도 한다. 무슨 차이가 있나 싶은데. 차이가 없다. 그런데, 어떤 문제 풀이...