[자료구조&알고리즘] 탐색(Search)

탐색(검색) 알고리즘: 저장된 데이터 중 원하는 값을 찾는 방법

---

1. 선형 탐색 (Linear Search, 순차 탐색)

• 방법: 데이터의 처음부터 끝까지 하나씩 차례대로 비교하며 원하는 값을 찾는 방식
• 특징: 정렬 여부와 상관없이 사용 가능, 구현이 단순하지만 데이터가 많을수록 비효율적
• 시간 복잡도: O(n)
• 적용: 정렬되지 않은 배열, 리스트 등
• 예시

[3][8][2][7][5]
 ↑  ↑  ↑  ↑  ↑
(순서대로 비교)

---

2. 이진 탐색 (Binary Search)

• 방법: 정렬된 데이터에서 중간값과 비교하여 더 작으면 왼쪽, 더 크면 오른쪽으로 인덱스를 이용해 절반씩 범위를 줄여가며 찾는 방식
• 특징: 정렬된 배열이나 리스트에서만 사용 가능, 매우 빠름
• 시간 복잡도: O(log n)
• 적용: 정렬된 배열, 리스트
• 예시:

배열: [1, 3, 5, 7, 9]
찾는 값: 5

1. 중간값 5와 비교 → 찾음!

---

3. 해시 탐색 (Hash Search)

• 방법: 해시 함수를 이용해 데이터의 저장 위치를 계산하여 바로 접근
• 특징: 평균적으로 매우 빠름, 충돌 처리 필요
• 시간 복잡도: 평균 O(1), 최악 O(n)
• 적용: 해시 테이블, 해시 맵 등
• 예시: 해시함수(key) → index

import java.util.HashMap;

public class HashSearchExample {
    public static void main(String[] args) {
        // HashMap 객체 생성 (키: String, 값: Integer)
        HashMap<String, Integer> hashMap = new HashMap<>();

        // 데이터 추가
        hashMap.put("Alice", 25);
        hashMap.put("Bob", 30);
        hashMap.put("Cathy", 35);
        hashMap.put("David", 40);

        // 키로 값 탐색
        String searchKey = "Cathy";
        if (hashMap.containsKey(searchKey)) {
            int value = hashMap.get(searchKey);
            System.out.println("The value for the key '" + searchKey + "' is: " + value);
        } else {
            System.out.println("The key '" + searchKey + "' is not in the HashMap.");
        }
    }
}

# 해시 테이블 생성
hashTable = [None] * 10

# 데이터 삽입
L = [34, 16, 2, 93, 80, 77, 51]
for num in L:
    hashTable[num % 10] = num

# 93을 찾고 싶을 때
key = 93
index = key % 10
if hashTable[index] == key:
    print(f"Number {key} found at index {index}")
else:
    print(f"Number {key} not found")

---

4. 이진 탐색 트리 탐색 (Binary Search Tree Search)

• 방법: 트리 구조에서 각 노드의 값을 기준으로 왼쪽/오른쪽 자식으로 이동하며 탐색
• 특징: 동적 데이터 삽입/삭제에 적합, 트리 균형에 따라 성능 차이
• 시간 복잡도: 평균 O(log n), 최악 O(n)
• 적용: 이진 탐색 트리(BST)
• 예시:

    5
   / \
  2   8
 / \   \
1   3   9

찾는 값: 3
5(루트) → 2(왼쪽) → 3(오른쪽)

---

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

• 방법: 트리나 그래프에서 한 분기를 끝까지 탐색한 뒤, 다음 분기로 이동
• 특징: 스택(혹은 재귀) 사용, 모든 경로를 탐색할 때 유용
• 적용: 트리, 그래프
• 예시:

    0
   / \
  1   2
 /     \
3-------4
탐색 순서 (0에서 시작, 가능한 한 왼쪽부터):
0 → 1 → 3 → 4 → 2

동작 과정:

0을 방문, 1로 이동

1을 방문, 3으로 이동

3을 방문, 4로 이동

4를 방문, 더 이상 갈 곳 없으니 백트래킹

2로 이동하여 방문.

---

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

• 방법: 트리나 그래프에서 가까운 노드부터 차례대로 탐색
• 특징: 큐 사용, 최단 경로 탐색에 유용
• 적용: 트리, 그래프
• 예시:

    0
   / \
  1   2
 /     \
3-------4
탐색 순서 (0에서 시작):
0 → 1 → 2 → 3 → 4

동작 과정:

0을 방문하고 큐에 0을 넣음

0의 이웃 1, 2를 큐에 추가

1을 방문, 1의 이웃 3을 큐에 추가

2를 방문, 2의 이웃 4를 큐에 추가

3, 4를 차례로 방문.

---

요약 표

탐색 종류	특징/적용 구조	시간 복잡도	비고
선형 탐색	정렬 불필요, 단순 배열	O(n)	구현 쉬움
이진 탐색	정렬 필요, 배열	O(log n)	정렬 필수
해시 탐색	해시 테이블	O(1) ~ O(n)	충돌 관리 필요
BST 탐색	이진 탐색 트리	O(log n) ~ O(n)	트리 균형 중요
깊이 우선 탐색	트리, 그래프	O(V+E)	스택/재귀
너비 우선 탐색	트리, 그래프	O(V+E)	큐