728x90
반응형
1. 탐색 알고리즘의 정의
탐색 알고리즘은 데이터 구조(배열, 리스트, 트리 등)에서 특정 값 또는 조건을 만족하는 데이터를 찾는 과정을 말합니다.
- 목적: 값이 데이터 안에 존재하는지 확인하거나, 위치를 반환.
- 필수 요소:
- 데이터 구조(정렬 여부, 크기, 형태)
- 탐색 키(찾고자 하는 값)
2. 탐색 알고리즘의 활용
탐색 알고리즘은 다음과 같은 분야에서 광범위하게 사용됩니다:
- 데이터 검색: 데이터베이스, 파일 시스템, 캐시.
- 웹 검색 엔진: 키워드 기반 검색.
- 네트워크 라우팅: 최단 경로 탐색.
- 게임 개발: 경로 탐색, 상태 공간 탐색.
- AI 및 머신러닝: 상태 공간에서 최적의 값 찾기.
3. 탐색 알고리즘의 종류
1) 선형 탐색 (Linear Search)
정의:
- 데이터를 처음부터 끝까지 순차적으로 확인하며 목표 값을 찾는 방식.
- 정렬되지 않은 데이터에서도 사용 가능.
특징:
- 단순하고 구현이 쉬움.
- 데이터 크기가 클수록 비효율적.
시간 복잡도:
- 최악: O(n)O(n)
- 최선: O(1)O(1) (첫 번째 요소가 목표값일 때)
2) 이진 탐색 (Binary Search)
정의:
- 데이터를 정렬된 상태에서 탐색 범위를 절반씩 줄여나가며 목표 값을 찾는 알고리즘.
특징:
- 정렬된 데이터에서만 동작.
- 효율적이며 데이터 크기가 커질수록 강력.
시간 복잡도:
- 최악: O(logn)O(\log n)
- 최선: O(1)O(1) (중간값이 목표값일 때)
3) 이진 탐색 트리 탐색 (Binary Search Tree Search)
정의:
- **이진 탐색 트리(Binary Search Tree, BST)**에서 값을 찾는 알고리즘.
- 트리 구조에서 왼쪽은 작은 값, 오른쪽은 큰 값으로 저장.
특징:
- 동적 데이터 삽입/삭제가 필요한 경우 적합.
- 탐색 과정은 이진 탐색과 유사.
시간 복잡도:
- 최악: O(n)O(n) (트리가 한쪽으로 치우칠 때)
- 평균: O(logn)O(\log n)
탐색 시
트리가 한쪽으로 치우칠경우
4) 해시 탐색 (Hash Search)
정의:
- 데이터를 해시 함수를 통해 탐색.
- 데이터 키(key)를 해시 함수에 입력하여 저장 위치를 계산.
특징:
- 매우 빠르며 데이터 크기와 상관없이 일정 시간 소요.
- 해시 충돌 발생 가능.
시간 복잡도:
- 최악: O(n)O(n) (충돌 발생 시)
- 평균: O(1)O(1)
5) 깊이 우선 탐색 (Depth-First Search, DFS)
정의:
- 그래프나 트리에서 한 노드를 시작으로 깊게 탐색한 후, 다음 분기로 이동.
- 스택(재귀적 호출) 기반으로 동작.
시간 복잡도:
- O(V+E)O(V + E): VV는 정점, EE는 간선.
6) 너비 우선 탐색 (Breadth-First Search, BFS)
정의:
- 그래프나 트리에서 한 노드를 시작으로 넓게 탐색.
- 큐(queue) 기반으로 동작.
시간 복잡도:
- O(V+E)O(V + E): VV는 정점, EE는 간선.
CF) BFS, DFS 비교
4. 탐색 알고리즘 비교
알고리즘정렬 필요시간 복잡도특징
| 선형 탐색 | X | O(n)O(n) | 단순하지만 비효율적 |
| 이진 탐색 | O | O(logn)O(\log n) | 정렬된 배열에서만 사용 가능 |
| 이진 탐색 트리 | O | O(logn)O(\log n) | 트리 구조에서 삽입, 삭제도 가능 |
| 해시 탐색 | X | O(1)O(1) | 매우 빠르지만 충돌 가능 |
| DFS | X | O(V+E)O(V + E) | 트리/그래프의 깊이 탐색 |
| BFS | X | O(V+E)O(V + E) | 트리/그래프의 너비 탐색 |
728x90
반응형
'Computer Science > 자료구조 & 알고리즘' 카테고리의 다른 글
| [자료구조 & 알고리즘] 그래프 + DFS (4) | 2024.12.20 |
|---|---|
| [자료구조 & 알고리즘] 정렬 알고리즘 총 정리 (0) | 2024.12.18 |
| [자료구조 & 알고리즘] 자료구조 개념 총정리 (향후 내용추가) (1) | 2024.12.16 |
| [알고리즘] 공부 목표 & 학습자료 (0) | 2024.12.01 |
| [알고리즘 C] 정렬 알고리즘 기본 코드 (1) | 2024.12.01 |
