충돌 없는 완벽한 해싱이 존재한다고 ? (퍼펙트 해싱 개념 및 사례, 최적화 방법에 대해서)
이 글의 탄생 배경, 이 글에 대해서코딩 스터디 중 해싱 챕터에서 시간 복잡도를 주제로 이야기할 때였다. 해싱하면 연상되는 이미지는 당연히 "빠르다"였고 나는 당연스럽게 O(1)이지! 라고 생각하며 대화를 이어나갔는데, 한 멤버가 질문했다."어... 해싱도 최악의 경우는 O(n) 아니에요?"어라, 순간 멈칫했다. 사실 해싱에서 최악의 경우는 O(n)이라는 걸 깜빡하고 있었다! 자바에서 해싱을 사용할 때는 충돌 문제를 자동으로 처리해주고, 또 key-value 스토어로서 레디스와 같은 저장소를 사용할 때, 단순히 "빠르다"는 이미지에만 노출되어 있다 보니 당연히 해싱은 O(1)이라고 생각했던 것이다. 문득 기억을 환기시키며 깨달았다. 앗,,, 해싱은 충돌이 없다면 O(1)이지만, 충돌이 발생하면 O(n)이..
2024. 11. 2.
요세푸스 문제의 마지막 남은 사람을 수학적 귀납법으로 도출한 점화식으로 찾아보자
이 글의 작성 배경요세푸스 문제를 다양한 방법으로 풀어보면서 배열, 큐, 링크드 리스트, 세그먼트 트리 등 여러 알고리즘적 접근을 시도해 보았다. 각 방법에서 최적화를 시도했지만, 시간 복잡도는 여전히 \( O(n^2) \) 정도였고, 세그먼트 트리를 사용해도 \( O(n \log n) \) 이 최대였다. 조금 더 최적화할 방법이 뭔가 있을 것 같은데... 고민하다가 문제를 가상의 순환 구조로 해석하면 어떤 규칙이나 패턴이 존재하지 않을까 하는 의문이 생겼다. 그러던 중, 점화식 풀이법을 알게 되며 이 방식에 주목하게 되었다. 점화식을 활용한 풀이법은 흥미로웠지만, 문제는... 어려웠다. 😭 특히, 이 점화식을 어떻게 유도할 수 있는지, 그 논리적 근거와 직관이 어떻게 도출되는지, 그리고 실제로 이 ..
2024. 10. 13.
