0. 들어가며...
버킷은 처음 공부할 때 가장 애매했던 개념 중 하나였다.
세그먼트 트리의 경우 그래도 "이런 문제에서 쓰는구나" 하는 감이 비교적 빨리 오는데, 버킷은 설명을 들어도 막상 문제를 보면 어디에서 써야 하는지 잘 모르겠다는 느낌이 강했다.
이번 글에서는 내가 이해한 버킷의 본질과, 문제에서 어떤 식으로 버킷을 떠올려야 하는지 정리해보려고 한다.
1. 버킷이 필요한 이유
전체를 다 보면 느리다
문제를 풀다 보면 이런 상황을 자주 만난다.
- 배열 전체를 매번 다 보면
O(N)이 걸린다. - 점과 점을 매번 전부 비교하면
O(N^2)이 된다. - 값의 범위가 너무 커서 전체를 정직하게 관리하기 어렵다.
예를 들어 구간 합을 반복해서 구해야 하는데 매번 l부터 r까지 직접 더하면 느리다.
좌표 평면 위 점들 사이의 거리 판정을 해야 하는데 매번 모든 점을 다 비교하면 그것도 느리다.
묶어서 보면 빨라질 수 있다
여기서 버킷이라는 발상이 나온다.
예를 들어
- 배열이 있으면 인덱스를 몇 개씩 묶어서 블록으로 나눌 수 있다.
- 값의 범위가 크면 값대별로 구간을 나눌 수 있다.
- 2차원 좌표 공간이면 작은 칸(cell)들로 나눌 수 있다.
이렇게 나누고 나면, 매번 모든 원소를 처음부터 끝까지 보는 대신 지금 필요한 범위와 관련 있는 블록만 확인하면 된다.
어떤 경우에는 블록 하나를 통째로 처리할 수도 있고, 어떤 경우에는 마지막에 남는 부분만 직접 보면 되기도 한다.
즉 버킷은 전체를 줄이기 위한 바깥 틀이라고 볼 수 있다.
2. 버킷의 핵심 아이디어
버킷은 결국 "묶기"다
버킷의 핵심은 정말 단순하다.
비슷한 것끼리 묶어서 관리한다.
여기서 "비슷한 것"은 문제에 따라 달라진다.
- 배열 문제에서는 인덱스가 가까운 원소들
- 값 관련 문제에서는 값의 범위가 비슷한 원소들
- 좌표 문제에서는 공간적으로 가까운 점들
즉 버킷은 하나의 고정된 자료구조라기보다는, 무엇을 기준으로 묶을 것인가를 정하는 아이디어에 가깝다.
양 끝은 직접, 가운데는 한 번에
버킷에서 가장 자주 나오는 패턴은 이거다.
양 끝은 직접 처리하고, 가운데는 블록 단위로 처리한다.
예를 들어 배열을 블록으로 나눴다고 하자.
구간 [l..r]의 합을 구해야 한다면,
- 왼쪽에서 블록이 애매하게 걸치는 부분은 직접 보고
- 가운데 완전히 포함되는 블록들은 블록 합을 한 번에 더하고
- 오른쪽에서 남는 부분만 다시 직접 본다
이 흐름이 버킷의 가장 기본적인 감각이다.
즉 버킷은 대개 애매하게 걸친 부분은 직접 처리하고 깔끔하게 떨어지는 구간은 묶음 단위로 처리하는 방식으로 속도를 줄인다.
3. 버킷의 대표 유형
배열 블록 분할형
가장 기본적인 버킷 유형이다.
배열을 sqrt(N) 크기 정도의 블록으로 나누고, 블록마다 합이나 최솟값 같은 요약 정보를 따로 저장해 둔다.
예를 들어 N = 10이고 블록 크기를 4로 잡으면 배열은 이렇게 나뉜다.
- 0번 블록:
0 ~ 3 - 1번 블록:
4 ~ 7 - 2번 블록:
8 ~ 9
그리고 각 블록의 합을 blockSum[]에 저장해두면, 구간합 query에서 가운데 블록은 통째로 더할 수 있다.
이 유형의 핵심은 다음 수식들이다.
blockSize = ceil(sqrt(N))blockCount = ceil(N / blockSize)idx / blockSize= 몇 번 블록인지left % blockSize != 0이면 아직 블록 시작점이 아니므로 직접 처리left + blockSize - 1 <= right이면 현재 블록 전체를 통째로 쓸 수 있음
이건 버킷의 가장 정석적인 형태라고 보면 된다.
정렬 버킷형
배열 블록 분할형에서 한 단계 더 나아간 형태다.
이번에는 블록마다 단순한 합이 아니라, 정렬된 정보를 들고 있는다.
왜 이런 게 필요하냐면, 어떤 문제는 블록마다 합 하나만 저장해서는 해결이 안 되기 때문이다.
예를 들어 이런 질문이 들어온다고 하자.
구간
[l..r]에서k보다 큰 수의 개수는?
이건 구간 합처럼 숫자 하나로 표현하기 어렵다.
대신 블록 안 원소들을 정렬해 두면 완전한 블록은 upperBound(k)로 k보다 큰 수의 개수를 빠르게 셀 수 있고, 양 끝의 애매한 블록만 직접 보면 된다.
즉 정렬 버킷형은 버킷 + 이분탐색 구조라고 보면 된다.
이 유형에서는 블록마다 보통 정렬된 리스트를 하나 더 들고 가고, 업데이트가 들어오면 기존 값을 제거하거나 새 값을 삽입해서 정렬 상태를 유지한다.
값 범위 버킷형
이번에는 배열 인덱스를 나누는 게 아니라 값의 범위 자체를 나눈다.
예를 들어 값 범위가 1 ~ 1,000,000인데 실제 데이터는 몇 천 개밖에 없다고 해보자.
이럴 때 값을 그대로 다루기보다 범위를 이렇게 나눌 수 있다.
- 0번 버킷:
1 ~ 1000 - 1번 버킷:
1001 ~ 2000 - 2번 버킷:
2001 ~ 3000 - ...
그리고 각 버킷에 몇 개가 있는지, 혹은 그 버킷 안에 실제 어떤 값들이 있는지를 따로 관리한다.
이런 방식은 다음 같은 질의에서 유용하다.
- 현재 최솟값 / 최댓값 찾기
X이하 개수 구하기- 특정 값 이상/이하 중 가장 가까운 값 찾기
핵심은 정답이 어느 값대에 있는지 먼저 좁히고, 그 버킷 안만 자세히 본다는 점이다.
즉 값 범위 버킷형은 "답을 바로 찾는 구조"라기보다, 답이 있을 만한 구간을 빠르게 좁히는 구조라고 이해하는 게 편하다.
공간 버킷형
이건 2차원 좌표 문제에서 자주 나오는 형태다.
좌표 범위가 매우 클 때, 평면 전체를 2차원 배열로 만들면 메모리 초과가 날 수 있다.
예를 들어 1,000,000 x 1,000,000 같은 공간을 그대로 배열로 만들 수는 없다.
이럴 때 공간을 일정 크기의 칸(cell)으로 나누고, 점이나 객체를 자기 칸에 넣어둔다.
예를 들어 칸 크기를 B라고 하면
cellX = x / BcellY = y / B
로 어떤 칸에 속하는지 계산할 수 있다.
그리고 전체 평면을 배열로 들고 있는 게 아니라, Map<cell, points> 같은 구조로 실제로 점이 있는 칸만 저장한다.
이 방식은 다음 같은 문제에서 잘 맞는다.
- 반경
R이내 점 찾기 - 가까운 객체만 보면 되는 경우
- 충돌 판정
- 주변 장애물/적 탐색
즉 공간 버킷형은 희소한 2차원 공간을 효율적으로 관리하는 버킷이라고 보면 된다.
4. 버킷 안에는 무엇을 넣을까
버킷은 바깥 틀일 뿐이고, 실제 문제 해결은 버킷 내부에 어떤 자료구조를 넣느냐에 따라 달라진다.
정렬 리스트
버킷 내부에서 k보다 큰 수 개수, x 이하 개수처럼 개수 세기를 이분탐색으로 하고 싶을 때 쓴다.
이 경우 블록마다 정렬된 ArrayList 같은 걸 유지하고, 이분 탐색를 활용해서 답을 구한다.
즉 이 구조는 버킷 + 정렬 + 이분탐색이다.
정렬 리스트의 장점은 query가 강하다는 점이고,
단점은 update 때 값을 지우고 다시 삽입하면서 정렬 상태를 유지해야 하므로 조금 무거울 수 있다는 점이다.
TreeMap / TreeSet
이건 버킷 안에서 정렬된 순서 자체가 중요할 때 쓴다.
예를 들어 필요한 연산이 이런 식이라면 잘 맞는다.
- 현재 최소 / 최대
x이상인 가장 작은 값x이하인 가장 큰 값
TreeSet
- 중복이 중요하지 않을 때
- 정렬된 집합이면 충분할 때
TreeMap
- 같은 값이 여러 개 있을 수 있을 때
- 즉 중복까지 관리해야 할 때
예를 들어 값 범위 버킷형에서 먼저 어느 버킷에 답이 있는지 좁히고 그 버킷 안에서 firstKey(), lastKey(), ceilingKey(), floorKey() 같은 걸 쓰는 식으로 결합할 수 있다.
HashMap + 직접 탐색
정렬은 필요 없고, 빈도 정보만 관리하면 되는 경우도 많다.
예를 들어 어떤 값이 몇 개 있는지, 어떤 타입의 이벤트가 몇 번 들어왔는지 이런 건 굳이 정렬 구조까지 쓸 필요가 없다.
이때는 HashMap<Integer, Integer> 로 빈도만 관리하고 버킷 내부를 필요할 때 직접 훑는 방식으로도 충분할 수 있다.
이 구조는 특히 버킷 내부 크기가 작고 정렬 순서가 중요하지 않을 때 유용하다.
5. 문제에서 버킷을 의심해야 하는 신호
버킷은 세그트리처럼 "이 문제는 무조건 세그트리" 같은 느낌이 잘 안 온다.
대신 문제를 읽다가 이런 신호가 보이면 의심해볼 만하다.
전체를 다 보면 느리다
O(N)이 너무 크다O(N^2)전체 비교가 안 된다
범위는 큰데 실제 데이터는 적다
- 값 범위는 넓지만 실제 원소 수는 적음
- 좌표 범위는 큰데 점 개수는 적음
근처만 보면 된다
- 거리
R이내만 확인하면 된다 - 주변 칸/주변 구간만 보면 된다
6. 버킷의 한계
버킷이 강력하긴 하지만, 만능은 아니다.
세그트리처럼 항상 깔끔한 O(log N)은 아니다
버킷은 보통 O(sqrt(N)) 근처가 많이 나오고,
상황에 따라 더 느릴 수도 있다.
데이터가 한 버킷에 몰리면 효율이 떨어진다
예를 들어 공간 버킷에서 점들이 한 칸에 몰리면, 후보를 줄였다고 해도 그 칸 안 비교가 많아져서 이득이 줄어든다.
문제마다 모양이 다르다
배열을 나누기도 하고, 값을 나누기도 하고, 공간을 나누기도 한다.
즉 "버킷 템플릿 하나 외워서 끝" 같은 느낌은 아니다.
그래서 버킷은 정형 자료구조라기보다, 최적화 아이디어에 더 가깝다고 보는 편이 맞다.
7. 마무리
처음에는 버킷이 너무 추상적으로 느껴졌다.
정확히는, 버킷이 뭔지 설명을 들어도 막상 문제를 보면 언제 이걸 써야 하는지 감이 잘 안 왔다. 근데 정리해보니 결국 본질은 하나였다.
전체를 다 보지 말고, 묶어서 필요한 부분만 보자.
배열을 묶든, 값을 묶든, 공간을 묶든 핵심은 똑같다.
그래서 앞으로 문제를 볼 때도 "이걸 세그트리로 해야 하나?"만 생각하기보다, 전체를 다 보지 말고, 블록이나 칸 단위로 먼저 줄일 수는 없을까?를 한 번쯤 떠올려보는 게 중요하다고 느꼈다.
