Java를 이용한 검색 알고리즘

안녕하세요 dev-woo 입니다.
오늘은 java를 이용한 검색 알고리즘에 대해 공부해 보겠습니다.

 

컴퓨터 과학에서 검색 알고리즘은 데이터에서 특정 값을 찾는 방법을 의미합니다. 검색 알고리즘의 목적은 수많은 데이터에서 필요한 정보를 빠르고 효율적으로 찾는 것입니다. 이 글에서는 Java와 함께 사용할 수 있는 다양한 검색 알고리즘들에 대해 소개하겠습니다.

순차 검색 - Sequential Search

순차 검색은 가장 기본적인 검색 알고리즘 중 하나입니다. 순차 검색은 배열에서 원하는 값을 찾을 때 각 요소를 차례로 검사하여 일치하는 값을 찾게 됩니다.

public static boolean sequentialSearch(int[] arr, int x) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == x) return true;
    }
    return false;
}

시간 복잡도는 O(n)입니다. 이 알고리즘은 검색할 데이터가 적은 경우나 자주 업데이트되는 경우에 유용합니다.

이진 검색 - Binary Search

이진 검색 알고리즘은 배열이 정렬된 경우에 사용할 수 있습니다. 더 빠른 검색을 위해 데이터가 정렬되어 있어야 하지만, 데이터를 정렬하는 것이 추가적인 비용을 낮출 수 있습니다.

public static int binarySearch(int[] arr, int x) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == x) return mid;
        else if (arr[mid] < x) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

시간 복잡도는 O(log n)입니다. 이 알고리즘은 검색할 데이터가 많은 경우나 자주 검색되는 경우에 유용합니다.

해시 검색 - Hash Search

해시 검색은 해시 테이블이라는 데이터 구조를 사용하여 검색을 수행합니다. 해시 함수를 사용하여 각 데이터를 해시 테이블의 적절한 위치에 저장하고 검색이 필요한 데이터에 대해 해당 위치에서 검색을 수행합니다.

public static boolean hashSearch(int[] arr, int x) {
    Set<Integer> set = new HashSet<Integer>();
    for (int num : arr) {
        set.add(num);
    }
    return set.contains(x);
}

해시 검색은 상수 시간 O(1)의 시간 복잡도를 가지며 매우 빠릅니다. 하지만 해시 충돌이 발생할 경우 성능 저하가 발생할 수 있습니다.

보간 검색 - Interpolation Search

이 알고리즘은 이진 검색과 비슷하지만, 데이터가 일정한 간격으로 분포되어 있을 때 평균적인 경우 이진 검색보다 적은 회수로 검색을 수행할 수 있습니다.

public static int interpolationSearch(int[] arr, int x) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high && x >= arr[low] && x <= arr[high]) {
        if (low == high) {
            if (arr[low] == x) return low;
            else return -1;
        }
        int pos = low + ((x - arr[low]) * (high - low)) / (arr[high] - arr[low]);
        if (arr[pos] == x) return pos;
        else if (arr[pos] < x) low = pos + 1;
        else high = pos - 1;
    }
    return -1;
}

시간 복잡도는 O(log log n)입니다. 이 알고리즘은 검색할 데이터가 정렬된 경우거나, 데이터 양이 많지만 빈번한 검색이 필요한 경우에 유용합니다.

거품 정렬 - Bubble Sort

거품 정렬은 배열을 정렬하는 가장 기본적인 알고리즘 중 하나입니다. 인접한 두 원소를 비교하여 크기가 작은 원소를 왼쪽으로 이동시켜 정렬합니다.

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

시간 복잡도는 O(n^2)입니다. 이 알고리즘은 작은 규모의 데이터에 적합합니다.

퀵 정렬 - Quick Sort

퀵 정렬은 분할 정복 알고리즘을 사용하여 배열을 정렬합니다. 먼저 배열에서 pivot 값을 선택한 후, pivot 값을 기준으로 배열을 둘로 분할하고, 각 부분 배열을 재귀적으로 정렬합니다.

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot-1);
        quickSort(arr, pivot+1, high);
    }
}

public static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
    return i+1;
}

시간 복잡도는 O(n log n)입니다. 이 알고리즘은 대부분의 데이터에 적합하며, 빠른 속도와 메모리 사용량의 비교적 낮은 부하를 가집니다.

병합 정렬 - Merge Sort

병합 정렬은 분할 정복 알고리즘을 사용하여 배열을 정렬합니다. 먼저 배열을 두 부분으로 분할한 다음, 각 부분을 정렬한 후, 두 부분을 병합하여 정렬된 배열을 생성합니다.

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
}

public static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] < arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    for (int index = 0; index < temp.length; index++) {
        arr[left+index] = temp[index];
    }
}

시간 복잡도는 O(n log n)입니다. 이 알고리즘은 대부분의 데이터에 적합하며 안정적인 성능을 보입니다.

결론

Java를 이용한 검색 알고리즘과 정렬 알고리즘에 대해 알아보았습니다. 이 글에서는 각 알고리즘의 코드 예시와 시간 복잡도 등의 개념을 소개하였습니다. 개발자는 이러한 일반적인 알고리즘을 이해하고 적용하는 것이 중요합니다. 그렇게 함으로써 더 나은 성능과 더 좋은 코드를 만들 수 있습니다.