세그먼트 트리에 대해 알아보자: 해결하는 문제와 데이터 구조, 작동 방식, 사용 사례, 자바 코드
개요세그먼트 트리는 효율적인 데이터 관리와 빠른 쿼리를 가능하게 해주는 데이터 구조이다. 특히, 누적 합 계산이나 특정 구간의 최대값, 최소값을 빠르게 처리해야 하는 경우 유용하게 쓰인다. 💡 이 글에서는 세그먼트 트리가 해결하는 문제와 그 이유, 작동 원리와 활용 사례에 대해서 살펴본다.문제 상황 🧐다음과 같은 배열 {1, 3, 5, 7, 9}를 생각해보자. 이에 대해서 다음과 같은 연산을 해야 하는 상황이다.구간 합 구하기예를 들어, 배열의 2번째부터 4번째 숫자의 합을 계산하려면 3 + 5 + 7 = 15이다.값 업데이트배열의 특정 값을 바꿔야 한다면 어떻게 될까요? 예를 들어, 5를 6으로 변경한다면 배열은 {1, 3, 6, 7, 9}로 변한다.이 배열에 대해, 직관적으로 구간 합을 구하거나 ..
2024. 12. 21.
충돌 없는 완벽한 해싱이 존재한다고 ? (퍼펙트 해싱 개념 및 사례, 최적화 방법에 대해서)
이 글의 탄생 배경, 이 글에 대해서코딩 스터디 중 해싱 챕터에서 시간 복잡도를 주제로 이야기할 때였다. 해싱하면 연상되는 이미지는 당연히 "빠르다"였고 나는 당연스럽게 O(1)이지! 라고 생각하며 대화를 이어나갔는데, 한 멤버가 질문했다."어... 해싱도 최악의 경우는 O(n) 아니에요?"어라, 순간 멈칫했다. 사실 해싱에서 최악의 경우는 O(n)이라는 걸 깜빡하고 있었다! 자바에서 해싱을 사용할 때는 충돌 문제를 자동으로 처리해주고, 또 key-value 스토어로서 레디스와 같은 저장소를 사용할 때, 단순히 "빠르다"는 이미지에만 노출되어 있다 보니 당연히 해싱은 O(1)이라고 생각했던 것이다. 문득 기억을 환기시키며 깨달았다. 앗,,, 해싱은 충돌이 없다면 O(1)이지만, 충돌이 발생하면 O(n)이..
2024. 11. 2.
