Profile

Searching

1. 선형 탐색 (Linear Search)

  • 시간 복잡도: O(n)

선형 탐색은 배열의 첫 번째 요소부터 마지막 요소까지 차례대로 탐색하는 방식입니다.

int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;  // 찾는 값의 인덱스 반환
        }
    }
    return -1;  // 찾는 값이 없는 경우
}

2. 이진 탐색 (Binary Search)

  • 시간 복잡도: O(log n)

이진 탐색은 배열이 정렬되어 있는 경우에 사용할 수 있으며, 중간 값을 기준으로 탐색 범위를 절반으로 줄여 나가는 방식입니다.

2-1. 반복문을 사용한 이진 탐색

int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) {
            return mid;  // 값을 찾았을 때
        } else if (arr[mid] < target) {
            low = mid + 1;  // 오른쪽 부분 탐색
        } else {
            high = mid - 1;  // 왼쪽 부분 탐색
        }
    }
    return -1;  // 찾는 값이 없는 경우
}

2-2. 재귀를 사용한 이진 탐색

int binarySearchRecursive(int[] arr, int target, int low, int high) {
    if (low > high) return -1;  // 탐색 범위를 벗어난 경우
    
    int mid = (low + high) / 2;
    if (arr[mid] == target) {
        return mid;  // 값을 찾았을 때
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, high);  // 오른쪽 부분 탐색
    } else {
        return binarySearchRecursive(arr, target, low, mid - 1);  // 왼쪽 부분 탐색
    }
}

3. 제곱근 탐색 (Jump Search)

  • 시간 복잡도: O(√n)

제곱근 탐색은 일정한 범위로 건너뛰며 탐색하는 방식입니다. 배열이 정렬되어 있을 때 유효합니다.

int jumpSearch(int[] arr, int target) {
    int n = arr.length;
    int step = (int) Math.floor(Math.sqrt(n));
    int prev = 0;

    while (arr[Math.min(step, n) - 1] < target) {
        prev = step;
        step += (int) Math.floor(Math.sqrt(n));
        if (prev >= n) return -1;
    }

    // 선형 탐색 수행
    while (arr[prev] < target) {
        prev++;
        if (prev == Math.min(step, n)) return -1;
    }

    if (arr[prev] == target) return prev;
    return -1;
}

4. 보간 탐색 (Interpolation Search)

  • 시간 복잡도: O(log log n)

보간 탐색은 이진 탐색과 비슷하나, 탐색할 값을 추정하여 접근하는 방식으로, 값이 균등하게 분포된 배열에서 사용됩니다.

int interpolationSearch(int[] arr, int target) {
    int low = 0, 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;
        } else if (arr[pos] < target) {
            low = pos + 1;
        } else {
            high = pos - 1;
        }
    }
    return -1;
}

5. 이진 검색 트리 (Binary Search Tree, BST)

  • 시간 복잡도: 평균 O(log n), 최악 O(n)

BST는 트리 자료 구조에서 탐색을 수행하는 방식입니다.

5-1. 이진 검색 트리 삽입

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int x) {
        val = x;
        left = right = null;
    }
}

TreeNode insert(TreeNode root, int key) {
    if (root == null) {
        return new TreeNode(key);
    }
    
    if (key < root.val) {
        root.left = insert(root.left, key);
    } else if (key > root.val) {
        root.right = insert(root.right, key);
    }
    
    return root;
}

5-2. 이진 검색 트리 탐색

TreeNode search(TreeNode root, int key) {
    if (root == null || root.val == key) {
        return root;  // 찾은 경우
    }
    
    if (key < root.val) {
        return search(root.left, key);  // 왼쪽 서브트리 탐색
    } else {
        return search(root.right, key);  // 오른쪽 서브트리 탐색
    }
}

6. 삼진 탐색 (Ternary Search)

  • 시간 복잡도: O(log3 n)

삼진 탐색은 이진 탐색과 유사하나, 배열을 세 부분으로 나누어 탐색하는 방식입니다.

int ternarySearch(int[] arr, int low, int high, int target) {
    if (high >= low) {
        int mid1 = low + (high - low) / 3;
        int mid2 = high - (high - low) / 3;

        if (arr[mid1] == target) {
            return mid1;
        } else if (arr[mid2] == target) {
            return mid2;
        }

        if (target < arr[mid1]) {
            return ternarySearch(arr, low, mid1 - 1, target);  // 왼쪽 부분 탐색
        } else if (target > arr[mid2]) {
            return ternarySearch(arr, mid2 + 1, high, target);  // 오른쪽 부분 탐색
        } else {
            return ternarySearch(arr, mid1 + 1, mid2 - 1, target);  // 중간 부분 탐색
        }
    }
    return -1;
}

7. 해시 탐색 (Hash Search)

  • 시간 복잡도: O(1)

해시 탐색은 배열이 아닌 HashMap을 사용하여 탐색하는 방법입니다.

Map<Integer, String> map = new HashMap<>();

// 값 삽입
map.put(1, "One");
map.put(2, "Two");

// 값 탐색
String result = map.getOrDefault(2, "Not Found");
System.out.println(result);  // "Two"

8. 너비 우선 탐색 (BFS, Breadth-First Search)

  • 시간 복잡도: O(V + E) (V는 노드 수, E는 간선 수)

BFS는 그래프에서 주로 사용되며, 큐를 사용하여 최단 경로 탐색에 유리합니다.

void bfs(int start, List<List<Integer>> graph) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[graph.size()];
    
    queue.add(start);
    visited[start] = true;
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");
        
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.add(neighbor);
            }
        }
    }
}

9. 깊이 우선 탐색 (DFS, Depth-First Search)

  • 시간 복잡도: O(V + E)

DFS는 그래프에서 깊이 우선으로 탐색하며, 재귀적으로 구현되거나 스택을 사용합니다.

void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
    visited[node] = true;
    System.out.print(node + " ");
    
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, graph);
        }
    }
}
PreviousSortingNextGreedy

Last updated