기록

개인적으로 공부하다가 그 심플함과 발상에 충격먹은 알고리즘 1순위 (2023/07 기준)

Binary Search의 구현에 관한 정리. 주제 자체는 solved.ac 기준 실버 티어 정도일 수도 있겠지만, 제대로 쓰기까지 상당한 시간이 걸리는 주제이기도 하다. 또, 각종 알고리즘에서 뜬금없이 튀어나오는 1순위. O(n)을 O(log n)으로 줄여주는 강력한 무기.

Bit count는 말 그대로 int 나 long long 등에 저장된 숫자가 2진법으로 1이 몇개가 켜져있는지를 세는 것을 말한다. 흔히 __builtin_popcount로 사용하지만, 직접 구현할 경우를 살펴본다.