버킷(Bucket) 알고리즘 - 코딩테스트에서 시간을 단축하는 비법(시간복잡도, C언어,Java,Python 예시코드)

버킷(Bucket) 알고리즘

 

코딩테스트 문제를 풀 때, 효율적인 자료구조와 알고리즘을 선택하는 것은 매우 중요합니다. 오늘은 버킷 알고리즘에 대해 알아보고, 이를 활용하여 문제를 빠르게 해결하는 방법을 공유드리겠습니다. 버킷 알고리즘의 개념, 동작 원리, 시간 복잡도, 장단점, 그리고 대표적인 문제와 코드 예제를 살펴보겠습니다.

---

1. 버킷 알고리즘이란?

버킷 알고리즘(Bucket Algorithm)은 데이터를 일정한 범위로 나누어 처리하는 방식입니다. 데이터를 미리 분할하여 필요한 범위 내에서만 계산하거나 검색하도록 최적화된 방법으로, 흔히 범위 쿼리 문제나 데이터 그룹화 문제에서 사용됩니다.

---

 

반응형

2. 동작 원리

버킷의 원리

 

1. 버킷 생성: 데이터를 일정한 크기의 범위로 나눕니다. 이 범위를 버킷이라고 합니다.
2. 데이터 분배: 각 데이터를 해당하는 버킷에 삽입합니다.
3. 처리 수행: 특정 범위의 데이터를 처리할 때, 해당 범위에 포함된 버킷만 검사합니다.

예를 들어, 숫자 데이터를 정렬하는 대신 버킷에 나눠 넣고 필요한 범위만 탐색하면 전체 데이터를 탐색하지 않아도 됩니다.

---

 

3. 시간 복잡도

• 버킷 생성 및 데이터 분배: O(n)
• 버킷 내 처리: 데이터 분포와 문제 유형에 따라 다르지만 보통 O(k + m), 여기서 k는 탐색할 버킷 수, m은 버킷 내 데이터 수입니다.

버킷 알고리즘은 데이터가 고르게 분포되어 있을 때 가장 효율적입니다.

---

 

4. 장단점

장점:

• 특정 범위의 데이터를 빠르게 검색 가능
• 큰 데이터를 처리할 때 효율적
• 다양한 문제에 적용 가능 (예: 정렬, 최솟값/최댓값 찾기, 중복 검사)

단점:

• 데이터가 불균등하게 분포되면 비효율적
• 메모리 사용량이 증가할 수 있음

---

 

5. 대표적인 코딩테스트 문제

1. 범위 내 최대/최소값 찾기
2. 주어진 범위의 데이터 합 계산
3. 중복 데이터 탐색
4. 값 정렬 또는 그룹화 문제

---

 

6. 코드 예시

C 언어 예제

#include <stdio.h>
#include <stdlib.h>

#define BUCKET_SIZE 10

void bucketSort(int arr[], int n) {
    int buckets[BUCKET_SIZE][n];
    int bucketCount[BUCKET_SIZE] = {0};

    // 데이터 분배
    for (int i = 0; i < n; i++) {
        int bucketIndex = arr[i] / BUCKET_SIZE;
        buckets[bucketIndex][bucketCount[bucketIndex]++] = arr[i];
    }

    // 각 버킷 정렬
    for (int i = 0; i < BUCKET_SIZE; i++) {
        for (int j = 0; j < bucketCount[i] - 1; j++) {
            for (int k = j + 1; k < bucketCount[i]; k++) {
                if (buckets[i][j] > buckets[i][k]) {
                    int temp = buckets[i][j];
                    buckets[i][j] = buckets[i][k];
                    buckets[i][k] = temp;
                }
            }
        }
    }

    // 결과 병합
    int index = 0;
    for (int i = 0; i < BUCKET_SIZE; i++) {
        for (int j = 0; j < bucketCount[i]; j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

int main() {
    int arr[] = {29, 25, 3, 49, 9, 37, 21, 43};
    int n = sizeof(arr) / sizeof(arr[0]);

    bucketSort(arr, n);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

 

Java 예제

import java.util.*;

public class BucketSort {
    public static void bucketSort(int[] arr) {
        int n = arr.length;
        List<Integer>[] buckets = new List[10];

        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 데이터 분배
        for (int num : arr) {
            int bucketIndex = num / 10;
            buckets[bucketIndex].add(num);
        }

        // 각 버킷 정렬
        for (List<Integer> bucket : buckets) {
            Collections.sort(bucket);
        }

        // 결과 병합
        int index = 0;
        for (List<Integer> bucket : buckets) {
            for (int num : bucket) {
                arr[index++] = num;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {29, 25, 3, 49, 9, 37, 21, 43};
        bucketSort(arr);

        System.out.println(Arrays.toString(arr));
    }
}

 

Python 예제

def bucket_sort(arr):
    buckets = [[] for _ in range(10)]

    # 데이터 분배
    for num in arr:
        bucket_index = num // 10
        buckets[bucket_index].append(num)

    # 각 버킷 정렬
    for bucket in buckets:
        bucket.sort()

    # 결과 병합
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr

arr = [29, 25, 3, 49, 9, 37, 21, 43]
print(bucket_sort(arr))

---

 

버킷 알고리즘은 데이터를 범위별로 나눠 효율적으로 처리하는 강력한 도구입니다. 특히 코딩테스트에서 큰 데이터를 다루거나 특정 범위 내 값을 찾는 문제에 자주 활용됩니다.