[CS] 검색 알고리즘 (선형 검색, 이진 검색, 트리 검색, 해시 검색, 보간 검색)

검색 알고리즘은 데이터 집합에서 특정 값을 찾는 데 사용되는 중요한 알고리즘입니다. 다섯 가지 주요 검색 알고리즘인 선형 검색, 이진 검색, 트리 검색, 해시 검색, 보간 검색에 대하여 자세히 알아보겠습니다.

목차

선형 검색 (Linear Search)

이진 검색 (Binary Search)

트리 검색 (Tree Search)

해시 검색 (Hash Search)

보간 검색 (Interpolation Search)

---

선형 검색 (Linear Search)

선형 검색은 데이터 집합에서 특정 값을 찾기 위해 처음부터 끝까지 순차적으로 탐색하는 간단한 검색 알고리즘입니다. 시간복잡도는 O(n)입니다.

작동 방식

1. 데이터 집합의 첫 번째 요소부터 마지막 요소까지 순차적으로 탐색하면서 대상 값을 찾습니다.

2. 대상 값이 존재하면 해당 값을 반환하고, 데이터 집합을 모두 탐색한 후에도 대상 값이 없으면 -1을 반환합니다.

예시 코드

public class LinearSearch {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 12, 1, 9};
        int target = 8;

        int index = linearSearch(arr, target);
        if (index != -1) {
            System.out.println("Element found at index " + index);
        } else {
            System.out.println("Element not found");
        }
    }
}

---

이진 검색 (Binary Search)

이진 검색은 정렬된 배열에서 특정 값을 찾는 알고리즘입니다. 배열의 중간 요소와 대상 값을 비교하여 검색 범위를 반으로 나누어 탐색을 수행합니다. 검색 내용을 반으로 줄여가기 때문에 시간 복잡도는 O(log n)입니다.

작동 방식

1. 검색 범위의 가운데 요소와 대상 값을 비교합니다.

2. 가운데 요소가 대상 값보다 작으면 오른쪽 절반을, 크면 왼쪽 절반을 새로운 검색 범위로 설정합니다.

3. 검색 범위를 반으로 줄이며 반복하여 대상 값을 찾을 때까지 탐색을 진행합니다.

예시 코드

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (arr[mid] == target) {
                return mid;
            }

            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int target = 5;

        int index = binarySearch(arr, target);
        if (index != -1) {
            System.out.println("Element found at index " + index);
        } else {
            System.out.println("Element not found");
        }
    }
}

---

트리 검색 (Tree Search)

트리 검색은 트리 구조를 사용하여 특정 값을 검색하는 알고리즘입니다. 트리의 구조를 활용하여 데이터를 효율적으로 탐색할 수 있습니다. 일반적으로 시간 복잡도는 O(log n)이지만 편향된 트리의 경우 O(n)입니다. 트리의 구조에 따라 다를 수 있습니다.

작동 방식

1. 트리 구조에서 특정 값을 검색하기 위해 노드들을 순회하며 값을 찾습니다.

2. 대부분의 트리 검색 알고리즘은 균형 잡힌 트리를 유지하도록 설계되어 있어 탐색 시간을 최소화합니다.

예시 코드

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class TreeSearch {
    public static TreeNode search(TreeNode root, int target) {
        if (root == null || root.val == target) {
            return root;
        }

        if (target < root.val) {
            return search(root.left, target);
        } else {
            return search(root.right, target);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(8);

        int target = 4;
        TreeNode result = search(root, target);

        if (result != null) {
            System.out.println("Value " + target + " found in the tree.");
        } else {
            System.out.println("Value " + target + " not found in the tree.");
        }
    }
}

---

해시 검색 (Hash Search)

해시 검색은 해시 함수를 사용하여 키와 값을 짝지어 저장하고, 키를 통해 값을 검색하는 알고리즘입니다. 빠른 검색 속도를 제공하며, 일반적으로 시간 복잡도는 O(1)입니다.

작동 방식

1. 해시 함수를 사용하여 키와 값을 해시 테이블에 저장합니다.

2. 검색할 때는 동일한 해시 함수를 사용하여 키를 해시 테이블에 적용하여 값을 찾습니다.

예시 코드

import java.util.HashMap;

public class HashSearch {
    public static void main(String[] args) {
        // 해시 테이블 생성
        HashMap<String, Integer> hashMap = new HashMap<>();

        // 값 추가
        hashMap.put("apple", 100);
        hashMap.put("banana", 200);
        hashMap.put("cherry", 300);

        // 값 검색
        int value = hashMap.get("banana");
        System.out.println("Value: " + value);
    }
}

---

보간 검색 (Interpolation Search)

보간 검색은 정렬된 데이터 집합에서 특정 값을 찾는 알고리즘으로, 이진 검색의 발전된 형태입니다. 데이터가 균일하게 분포되어 있는 경우에 더 빠르게 동작할 수 있습니다. 시간 복잡도는 균등 분포된 데이터의 경우 O(log log n), 균등하지 않은 데이터에서 O(n)입니다.

작동 방식

1. 이진 검색과 달리 데이터를 반씩 분할하여 탐색하지 않고 대상 값과 비교하여 대상 값이 존재할 범위를 예측합니다.

2. 예측된 위치로 이동하여 비교를 수행하고, 대상 값이 예측 값보다 작으면 예측 범위를 왼쪽으로, 크면 오른쪽으로 좁히는 방식으로 탐색을 진행합니다.

예시 코드

public class InterpolationSearch {
    public static int interpolationSearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high && target >= arr[low] && target <= arr[high]) {
            if (low == high) {
                if (arr[low] == target)
                    return low;
                return -1;
            }

            int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);

            if (arr[pos] == target)
                return pos;

            if (arr[pos] < target)
                low = pos + 1;
            else
                high = pos - 1;
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int target = 6;

        int index = interpolationSearch(arr, target);
        if (index != -1) {
            System.out.println("Element found at index " + index);
        } else {
            System.out.println("Element not found");
        }
    }
}