아무 말

INTRODUCTION Segment tree를 이용해서 수열에서의 구간 합을 구하는 방법은 매우 잘 알려져 있다. 본문에서는 수열의 값이 0 또는 1밖에 없을때 이를 더 빠르게 처리하는 방법에 대해서 다루고자 한다. IDEA 컴퓨터에서 bit의 수를 세는 것은 \(O(1)\)에 수행할 수 있다. 또한, 이 bit를 셀 때 세고싶은 구간만 나눌 수 있다. 간단히 원하는 구간만 1로 채워져 있는 bitset과 bitwise AND 연산을 이용하면 된다. 그렇다면 이것으로 구간 쿼리를 처리하는 방법에 대해 감이 어느정도 왔을 것이다. Segmet tree의 맨 아래쪽 리프를 모두 bitset으로 만든다. 그리고 나머지는 원래대로 처리하면서 리프의 bitset에서 값이 1인 bit의 수를 세서 위쪽 리프로 올..

들어가기에 앞서.. 단순히 빠른 정렬 방법이 아니라, 특정 상황에서 좋은 정렬법에 대해 설명하고자 한다. BOJ의 '수 정렬하기(시리즈)'의 문제들을 통해 여러 정렬의 방법들을 알아보고자 한다. 본론 2750번: 수 정렬하기는 다루지 않도록 하겠다. 먼저, 10989번: 수 정렬하기 3을 보자. 딱 봐도 Counting Sort의 냄새가 난다. 시간 복잡도는 수의 범위의 크기가 T일 때, O(T+N)이다. Counting Sort는 정렬하고자 하는 수를 배열의 index로 생각하고 배열에서 Count 한 뒤 Count 한 횟수만큼 출력하는 것으로 이루어진다. Counting Sort를 모르는 사람은 많지 않을 것으로 생각한다. 이 Counting Sort의 단점은 수의 범위가 클 때 처리하기 어렵다는 것..