contents

🔎 코딩 테스트를 위한 탐색 알고리즘 가이드

코딩 테스트와 기술 면접에서 자주 등장하는 탐색 알고리즘을 자세히 정리했습니다. 각 알고리즘의 핵심 개념, 사용 사례, 시간 복잡도, Java 예제 코드를 포함합니다.

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)
🧩 사용 예: 정렬된 배열의 값 검색

int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

✅ 응용:

• 중복값 중 첫/마지막 위치 찾기
• lower_bound, upper_bound 구현 등

3. 📌 삼분 탐색 (Ternary Search)

🧠 개요:
데이터가 "늘었다 작아지는" (unimodal) 곡선(함수)일 때, 최대/최소값을 빠르게 찾기 위한 로그 급 탐색

⏱ 시간 복잡도: O(log n)
🧩 사용 예: 최대값 위치 찾기 (ex: 이진 탐색 대신 쓸 수 있음)

double ternarySearch(double left, double right, Function<Double, Double> f) {
    double eps = 1e-9;
    while (right - left > eps) {
        double m1 = left + (right - left) / 3;
        double m2 = right - (right - left) / 3;
        if (f.apply(m1) < f.apply(m2)) left = m1;
        else right = m2;
    }
    return (left + right) / 2;
}

4. 📌 점프 탐색 (Jump Search)

🧠 개요:
정렬된 배열에서 일정 간격(√n)만큼 건너뛰며 탐색. 범위 내에 들어간 뒤 선형 탐색을 수행.

⏱ 시간 복잡도: O(√n)
🧩 사용 예: 정렬된 중간 크기 리스트

int jumpSearch(int[] arr, int x) {
    int n = arr.length, step = (int)Math.floor(Math.sqrt(n));
    int prev = 0;
    while (arr[Math.min(step, n) - 1] < x) {
        prev = step;
        step += (int)Math.floor(Math.sqrt(n));
        if (prev >= n) return -1;
    }
    for (int i = prev; i < Math.min(step, n); i++)
        if (arr[i] == x) return i;
    return -1;
}

5. 📌 지수 탐색 (Exponential Search)

🧠 개요:
먼저 1, 2, 4, 8 식으로 범위를 넓히며 적절한 구간을 찾고, 그 안에서 이진 탐색 수행.

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

int exponentialSearch(int[] arr, int x) {
    int n = arr.length, bound = 1;
    while (bound < n && arr[bound] < x) bound *= 2;
    int left = bound / 2, right = Math.min(bound, n - 1);
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x) return mid;
        if (arr[mid] < x) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

6. 📌 보간 탐색 (Interpolation Search)

🧠 개요:
정렬된 값이 균등하게 분포되어 있음을 가정하고, 이진 탐색보다 더 정교하게 위치를 추측.

⏱ 시간 복잡도: 평균 O(log log n), 최악 O(n)
🧩 단점: 배열이 균일하지 않으면 비효율적

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

7. 📌 피보나치 탐색 (Fibonacci Search)

🧠 개요:
피보나치 수열을 기반으로 왼쪽/오른쪽 범위 분할. 이진 탐색의 대안

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

int fibonacciSearch(int arr[], int x) {
    int n = arr.length;
    int fibMm2 = 0, fibMm1 = 1, fibM = fibMm1 + fibMm2;
    while (fibM < n) {
        fibMm2 = fibMm1;
        fibMm1 = fibM;
        fibM = fibMm1 + fibMm2;
    }
    int offset = -1;
    while (fibM > 1) {
        int i = Math.min(offset + fibMm2, n - 1);
        if (arr[i] < x) {
            fibM = fibMm1;
            fibMm1 = fibMm2;
            fibMm2 = fibM - fibMm1;
            offset = i;
        } else if (arr[i] > x) {
            fibM = fibMm2;
            fibMm1 -= fibMm2;
            fibMm2 = fibM - fibMm1;
        } else return i;
    }
    if (fibMm1 == 1 && arr[offset + 1] == x) return offset + 1;
    return -1;
}

8. 📌 자료구조 기반 탐색

🔸 해시 탐색 (Hash Table)

• 평균: O(1)
• 사용 예: 존재 여부 확인, 중복 검사 등

HashSet<Integer> set = new HashSet<>();
set.add(10);
boolean found = set.contains(10); // true

🔸 이진 탐색 트리 (BST), 균형 이진 트리

• 평균: O(log n) (AVL, Red-Black trees 등 사용 시)
• 범위 검색, floor/ceiling 등 정렬 기반 연산에 유리

TreeSet<Integer> bst = new TreeSet<>();
bst.add(20); bst.add(5);
Integer next = bst.higher(10); // 20

9. 📌 그래프/트리 탐색 – DFS & BFS

🔹 DFS (깊이 우선 탐색)

• 가능한 깊이까지 먼저 탐색한 뒤, 백트래킹

void dfs(int node, boolean[] visited, List<Integer>[] adj) {
    visited[node] = true;
    for (int next : adj[node])
        if (!visited[next]) dfs(next, visited, adj);
}

🔹 BFS (너비 우선 탐색)

• 가까운 노드부터 레벨 순으로 순회

void bfs(int start, boolean[] visited, List<Integer>[] adj) {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    visited[start] = true;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int next : adj[node]) {
            if (!visited[next]) {
                queue.add(next);
                visited[next] = true;
            }
        }
    }
}

10. 💡 실무/테스트 팁

• 작은/비정렬 자료 → Linear Search
• 정렬된 자료 → Binary, Jump, Exponential
• 정수 탐색/중복 확인 → HashSet/Map
• 그래프/트리 탐색 → BFS/DFS
• 최솟값/최댓값 찾기 → Ternary Search

✅ 요약 표

references