데이터에서 원허는 값을 빠르고 효율적으로 찾는 방법이자 알고리즘의 필수 분야로,
탐색 알고리즘에 대해서 알아보자.
탐색에 앞서 자료구조의 형태 또한 중요하다.
배열, 리스트, 트리 등등 각 자료구조의 탐색 알고리즘은 각각 다르고
성능 차이가 있기에
탐색 알고리즘만 이해하기 보다,
트리 자료구조와 엮어서 이해해야 한다.
여기서 탐색이란 데이터 집합에서 특정 값을 찾는 작업이다.
예를 들어,
리스트에서 어느 숫자가 있는지 확인하고 있다면 그 위치를 반환한다.
앞서 살펴본 정렬 여부, 자료 구조에 따라 탐색 알고리즘의 효율이 달라진다.
| 분류 | 알고리즘 | 특징 |
|---|---|---|
| 선형 탐색 | 순차 탐색 (Linear Search) | 정렬 여부 관계없음, 단순한 구조 |
| 이진 탐색 | Binary Search | 정렬된 배열에만 적용 가능, 매우 빠름 |
| 해시 기반 | 해시 탐색 (Hash Table) | 키를 통해 즉시 접근, 매우 빠름 |
| 트리 탐색 | 이진 탐색 트리(BST), AVL 트리 | 정렬 + 구조화된 탐색 |
| 그래프 탐색 | BFS / DFS | 노드 간 관계 탐색에 활용 |