탐색 알고리즘(search algorithm)은 데이터 집합이나 구조 내에서 특정 목표값(키, 요소 등)을 찾기 위해 사용되는 절차적 방법을 의미한다. 일반적으로 입력으로는 탐색 대상이 되는 데이터 집합(배열, 리스트, 트리, 그래프 등)과 탐색하고자 하는 목표값이 주어지며, 출력으로는 목표값이 존재한다면 그 위치(인덱스, 노드 등)를, 존재하지 않으면 실패 신호를 반환한다.
주요 분류
| 분류 | 대표적인 알고리즘 | 적용 대상 | 특징 |
|---|---|---|---|
| 선형 탐색 | 순차 탐색(Linear Search) | 정렬 여부와 무관한 1차원 배열, 리스트 | 데이터 순차적으로 검사. 최악의 경우 O(n) 시간 복잡도. |
| 이진 탐색 | Binary Search | 정렬된 1차원 배열 | 중간값과 비교하여 탐색 범위를 절반씩 축소. 평균·최악 O(log n) 시간 복잡도. |
| 그래프 탐색 | 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) | 무방향·유향 그래프, 트리 | DFS: 스택(재귀) 기반, 경로 깊이 우선 탐색. BFS: 큐 기반, 레벨 순서 탐색. |
| 휴리스틱 탐색 | A* 알고리즘, Dijkstra 알고리즘 | 가중치 그래프(주로 경로 찾기) | 비용 함수(휴리스틱) 사용으로 최적 경로 탐색 효율성 향상. |
| 해시 기반 탐색 | 해시 테이블 조회 | 키-값 매핑 구조 | 평균 O(1) 시간 복잡도(충돌 최소 시). |
일반적인 동작 원리
- 입력 검증 – 데이터 구조와 목표값이 유효한지 확인한다.
- 탐색 전략 선택 – 데이터가 정렬돼 있는지, 구조의 특성(트리, 그래프 등)에 따라 적절한 알고리즘을 선택한다.
- 반복/재귀 수행 – 선택한 알고리즘에 따라 반복문이나 재귀 호출을 통해 목표값을 비교·검사한다.
- 결과 반환 – 목표값을 찾으면 해당 위치를, 찾지 못하면 실패 신호(예: –1, null)를 반환한다.
시간·공간 복잡도
- 선형 탐색: 시간 O(n), 공간 O(1)
- 이진 탐색: 시간 O(log n), 공간 O(1) (반복형) 또는 O(log n) (재귀형)
- DFS: 시간 O(V+E), 공간 O(V) (재귀 스택 포함)
- BFS: 시간 O(V+E), 공간 O(V) (큐 사용)
- A*: 시간 O(E) (휴리스틱 품질에 따라 변동), 공간 O(V)
활용 예시
- 데이터베이스 인덱스 검색
- 파일 시스템 경로 탐색
- 인공지능 게임에서 최단 경로 찾기
- 네트워크 라우팅 프로토콜
- 문자열 검색(예: KMP, Rabin‑Karp 등은 문자열 내 패턴 탐색 알고리즘에 해당)
참고 사항
- 탐색 효율은 데이터의 사전 정렬 여부, 구조 특성, 메모리 제약 등에 크게 좌우된다.
- 휴리스틱 기반 알고리즘은 목표에 최적화된 비용 함수를 설계하는 것이 성능에 핵심이다.
- 해시 충돌이나 그래프 사이클 등 특수 상황을 고려한 예외 처리가 필요하다.
