개요

검색(검색 알고리즘)과 탐색(탐색 알고리즘)은 자료구조나 상태공간에서 목표값이나 조건을 만족하는 항목(또는 경로)을 찾는 방법들을 말한다. 적용 대상과 목적에 따라 완전탐색(브루트포스), 그래프/트리 탐색, 정렬된 자료에서의 이진검색, 휴리스틱 기반 최적 경로 탐색 등으로 나뉜다.

주요 분류와 핵심 알고리즘

선형 검색 (Linear Search)

• 방법: 배열이나 리스트를 처음부터 끝까지 한 원소씩 검사해서 목표를 찾음.
• 장단점: 구현이 단순하고 정렬 불필요하지만 최악 시간복잡도 O(n)로 큰 데이터에 비효율적이다.

이진 검색 (Binary Search)

• 방법: 정렬된 배열에서 중앙값과 비교하여 탐색 범위를 반씩 좁혀 나감.
• 전제: 입력이 정렬되어 있어야 함. 시간복잡도 O(log n)로 대용량에서 효율적이다.

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

• 방법: 가능한 한 깊게 내려가며 상태공간/그래프를 탐색하고 더 이상 갈 곳이 없으면 되돌아감.
• 용도: 경로 존재 확인, 위상정렬, 백트래킹 문제(해밀턴, 퍼즐) 등에 자주 사용된다.

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

• 방법: 시작 노드에서 동일한 깊이(거리)에 있는 노드들을 먼저 모두 탐색한 뒤 다음 깊이로 이동.

• 특성: 최단거리(가중치 없는 그래프) 보장, 메모리 사용량은 높을 수 있음.

  

이진 탐색 트리(BST) 검색

• 방법: 트리 노드의 키 비교로 좌/우 자식으로 내려가며 탐색.
• 특성: 균형이 유지되면 평균 O(log n), 최악(편향) O(n). 균형 BST(AVL, Red-Black)는 성능 보장에 사용된다.