검색, 탐색 알고리즘

검색(탐색, Search) 알고리즘이란?

데이터 집합 안에서 특정 값을 찾는 방법을 말해.
“어디에 있는지 찾아내는” 과정이 핵심

대표적인 탐색 알고리즘은 아래와 같다

알고리즘특징시간 복잡도

선형 탐색 (Linear Search)	단순하지만 느림. 정렬 불필요	O(n)
이진 탐색 (Binary Search)	정렬된 배열에서만 가능, 빠름	O(log n)
해시 탐색 (Hash Search)	매우 빠름 (평균 O(1))	O(1)
깊이 우선 탐색 (DFS)	그래프/트리에서 깊이 우선	O(V + E)
너비 우선 탐색 (BFS)	그래프/트리에서 레벨 단위 탐색	O(V + E)

---

선형 탐색 (Linear Search)

데이터를 처음부터 끝까지 차례로 탐색하는 가장 기본적인 방법.

예제

function linearSearch(arr, target) { 
	for (let i = 0; i < arr.length; i++) { 
    	if (arr[i] === target) return i; // 찾았으면 인덱스 반환 
    } 
     return -1; // 못 찾았으면 -1 반환 
} 

console.log(linearSearch([3, 5, 2, 9, 7], 9)); //  3

설명:
모든 원소를 하나씩 비교하니까 단순하지만, 데이터가 많아질수록 느려짐.

---

이진 탐색 (Binary Search)

정렬된 배열에서만 사용 가능!
중간값을 기준으로 범위를 반으로 줄여가며 탐색.

예제

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

console.log(binarySearch([1, 3, 5, 7, 9, 11], 7)); // 👉 3

 

설명:
정렬된 배열에서 한 번 탐색할 때마다 탐색 범위가 절반으로 줄어듦!
→ 대용량 데이터 탐색에 유리.

---

해시 탐색 (Hash Search)

데이터를 Key-Value 쌍으로 저장해 바로 찾는 방식!
객체(Object)나 Map이 대표적인 구조야.

예제

 

const phoneBook = {
  '서인': '010-1234-5678',
  '영재': '010-9876-5432'
};

console.log(phoneBook['서인']); // 👉 "010-1234-5678"

 

설명:
원하는 키(Key)를 바로 접근하니까 평균적으로 탐색 속도는 O(1)!
(단, 해시 충돌이 많으면 느려질 수도 있어)

---

깊이 우선 탐색 (DFS)

그래프나 트리에서 깊게 들어갔다가 돌아오는 탐색 방식!
재귀(Recursion)나 스택(Stack)으로 구현 가능.

예제

 

const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: ['F'],
  F: []
};

function dfs(node, visited = new Set()) {
  console.log(node);
  visited.add(node);

  for (let neighbor of graph[node]) {
    if (!visited.has(neighbor)) dfs(neighbor, visited);
  }
}

dfs('A');
// 👉 A → B → D → E → F → C

 

설명:
한 갈래를 끝까지 따라가다가 더 이상 갈 수 없을 때 되돌아와 다른 길로 가는 방식.

---

너비 우선 탐색 (BFS)

가까운 노드부터 차례로 탐색하는 방식!
큐(Queue)를 이용해 구현해.

예제

 

function bfs(start) {
  const visited = new Set();
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift();
    if (!visited.has(node)) {
      console.log(node);
      visited.add(node);
      queue.push(...graph[node]);
    }
  }
}

bfs('A');
// 👉 A → B → C → D → E → F

 

설명:
DFS보다 “한 단계씩 넓게” 탐색하는 구조야.
최단 거리 탐색(예: 미로찾기)에 자주 사용돼.

---

요약 비교

알고리즘사용 대상장점단점

순차 탐색	정렬 X, 단순 배열	구현 쉬움	느림
이진 탐색	정렬된 배열	빠름	정렬 필수
해시 탐색	Key-Value 구조	매우 빠름	충돌 가능성
DFS	그래프/트리	경로 탐색에 유리	깊은 재귀 시 스택오버플로우 가능
BFS	그래프/트리	최단 거리 탐색	큐 메모리 소모 큼

---

 그래프 탐색 (Graph Traversal)

그래프 탐색이란, 그래프에 있는 모든 노드를 빠짐없이 한 번씩 방문하는 방법이야.

대표적으로 두 가지 방식이 있어 👇
 깊이 우선 탐색 (DFS: Depth-First Search)
 너비 우선 탐색 (BFS: Breadth-First Search)

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

개념

가까운 노드부터 차례대로 탐색하는 방식!

즉, “넓게 퍼져나가는 탐색”이라고 보면 돼.

---

 동작 순서

1. 시작 노드를 큐에 넣고 방문 처리
2. 큐에서 노드를 하나 꺼내서,
   아직 방문하지 않은 인접 노드를 큐에 차례로 추가
3. 큐가 빌 때까지 반복

---

예시 그래프 (같은 구조)

const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: ['F'],
  F: []
};

---

큐(Queue) 방식 구현

 

function bfs(start) {
  const visited = new Set();
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift(); // 큐의 맨 앞에서 꺼냄

    if (!visited.has(node)) {
      console.log(node);
      visited.add(node);
      queue.push(...graph[node]); // 인접 노드 큐에 추가
    }
  }
}

bfs('A');
// 👉 A → B → C → D → E → F

---

BFS의 특징

항목설명

자료구조	Queue
장점	최단 거리 탐색에 유리
단점	큐 메모리 사용량이 큼
활용 예시	미로의 최단 거리, SNS 친구 추천, 네트워크 탐색

---

 DFS vs BFS 비교 요약

비교 항목DFSBFS

탐색 방향	깊이 우선 (끝까지 들어감)	너비 우선 (가까운 노드부터)
사용 자료구조	스택 / 재귀	큐
구현 난이도	재귀로 간단	반복문으로 직관적
장점	경로 탐색, 백트래킹 문제에 강함	최단 거리 탐색에 강함
단점	깊은 그래프에서는 스택 오버플로우 가능	큐 메모리 부담
예시 문제	미로의 모든 경로 찾기, 백트래킹	미로의 최단 거리 찾기

---

 시각적 이해 (탐색 순서 예시)

 

그래프 구조:
A
├─ B
│  ├─ D
│  └─ E
│      └─ F
└─ C
    └─ F

DFS 순서: A → B → D → E → F → C  
BFS 순서: A → B → C → D → E → F

 

 

--

 

 탐색(Search)의 본질

탐색이란?

“데이터 집합 내에서 원하는 데이터를 찾는 행위”
즉, 어디에 있는지 위치를 찾거나 존재 여부를 판단하는 게 목적이야.

---

탐색의 분류

 (1) 자료 구조에 따른 분류

탐색 알고리즘은 데이터의 저장 방식에 따라 달라져.

자료 구조사용되는 탐색 방식예시

배열(Array)	순차 탐색, 이진 탐색	[1, 2, 3, 4, 5]
연결 리스트(Linked List)	순차 탐색	Node → Node → Node
트리(Tree)	이진 탐색 트리 탐색(BST Search), DFS, BFS	이진트리, 트라이
그래프(Graph)	DFS, BFS	SNS, 지도
해시(Hash Table)	해시 탐색	Key → Value

 즉, “탐색”은 데이터 구조에 맞춰 설계해야 해.
예를 들어 해시 테이블에 DFS를 쓰진 않지!

---

 탐색의 형태

형태설명예시

선형 탐색 (Linear Search)	순서대로 탐색	배열, 리스트
비선형 탐색 (Non-Linear Search)	계층적 구조나 연결 구조에서 탐색	트리, 그래프

배열 같은 단순 구조는 선형 탐색,
트리/그래프처럼 “가지(branch)”가 있는 구조는 비선형 탐색을 사용해.

---

탐색의 평가 기준 — 시간 복잡도

탐색 알고리즘은 결국 “얼마나 빨리 찾느냐”가 핵심이야.

알고리즘평균 시간 복잡도설명

순차 탐색	O(n)	전체 순회
이진 탐색	O(log n)	정렬 필요, 반씩 줄여감
해시 탐색	O(1)	거의 즉시 찾음
DFS / BFS	O(V + E)	그래프의 정점 수(V), 간선 수(E)에 비례

시간 복잡도(Time Complexity) = 데이터 개수(n)가 커질 때 알고리즘의 속도가 어떻게 변하는가.
즉, “탐색 효율성”을 수학적으로 보는 척도야.

---

탐색의 구현 방식

구현 방식설명예시

반복형(Iterative)	while, for문 사용	순차 탐색, BFS
재귀형(Recursive)	함수가 자기 자신 호출	DFS, 트리 순회

DFS처럼 “깊게 들어가야 하는 구조”는 재귀형,
BFS처럼 “넓게 순회해야 하는 구조”는 반복형으로 구현하는 경우가 많아.

---

🧭 6️⃣ 탐색과 정렬의 관계

탐색은 정렬된 상태일 때 더 빨라질 수 있어.

• 정렬이 안 된 배열 → 순차 탐색만 가능
• 정렬이 된 배열 → 이진 탐색 가능

그래서 실제 시스템에서는

“먼저 정렬 → 나중에 탐색”
이렇게 병행하는 경우가 많아 (예: DB 인덱스, 바이너리 서치 트리).

---

실전에서의 탐색 응용

분야사용 예시사용 탐색 알고리즘

데이터베이스(DB)	WHERE, INDEX 조회	이진 탐색, 해시 탐색
지도, 길찾기	최단 경로 탐색	BFS, 다익스트라
AI, 게임	상태 탐색, 의사결정 트리	DFS, BFS
보안, 해시 매칭	암호화 키 탐색	해시 탐색
검색엔진	문서 키워드 검색	트라이(Trie), 해시

---

탐색 알고리즘 선택 기준

조건추천 알고리즘

데이터가 정렬되어 있지 않다	순차 탐색
데이터가 정렬되어 있다	이진 탐색
빠른 탐색을 위해 Key-Value 구조 사용	해시 탐색
모든 경로 탐색, 백트래킹 문제	DFS
최단 거리 탐색, 레벨 기반 문제	BFS

---

정리 포인트

개념핵심 요약

탐색(Search)	데이터 집합에서 원하는 값 찾기
자료 구조	탐색의 효율성을 결정
시간 복잡도	탐색 성능의 수학적 표현
DFS/BFS	비선형 탐색의 대표주자
해시 탐색	가장 빠른 탐색 (평균 O(1))
정렬과 탐색의 관계	정렬되면 탐색이 빨라진다