[자료구조] 탐색(검색) 알고리즘 (Search Algorithm)

thinktank911 2025. 11. 4. 00:03

탐색 알고리즘이란?

탐색은 주어진 데이터 중에서 원하는 값을 찾는 과정을 말한다.

즉, 탐색 알고리즘은 "데이터 구조(배열, 트리, 그래프 등) 안에서 특정한 값이나 노드를 찾기 위한 규칙적인 절차 또는 방법"이라고 정의할 수 있다.

탐색 알고리즘의 분류

자료구조	대표 탐색 알고리즘	예시
배열	선형 탐색, 이진 탐색	리스트에서 값 찾기
트리	이진 탐색 트리 탐색, DFS, BFS	폴더 구조, 계층형 데이터
그래프	BFS, DFS	길찾기, 소셜 네트워크, 네비게이션

선형 탐색 (Linear Search / 순차 탐색)

배열의 맨앞에서 하나씩 목표 값(target)과 비교해 나가서 찾으면 멈춘다.

책장에 정리 안 된 책 더미가 있고, 원하는 책을 찾을 때 맨앞부터 하나씩 확인하는 방식과 같다.

언제 쓰나?

데이터가 정렬되어 있지 않을 때
데이터 크기가 작을 때
구현이 간단해야 할 때

시간/공간 복잡도

시간 : 최악 O(n), 평균 O(n)
공간 : O(1) (추가 메모리 거의 없음)

장단점

장점 : 구현 쉬움, 정렬 필요 없음.
단점 : 속도 느림(대규모 데이터에는 비효율)

해당 메서드

indexOf
includes
find
findIndex

구현 예시

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

이진 탐색 (Binary Search)

정렬된 배열에서 중간값과 비교해 탐색 범위를 반씩 줄여가며 찾는 방법

전화번호부에서 가운데 쪽을 보고 찾는 이름이 어느 쪽(앞/뒤)에 있는지 판단해 절반만 뒤져나가는 방식이다.

전제조건

반드시 정렬된 자료구조(오름/내림차순)여야 함

시간/공간 복잡도

시간 : O(log n) - 매우 빠름
공간 : O(1) (반복문 사용 시) / O(log n) (재귀 사용 시 스택)

장단점

장점 : 큰 데이터에서도 매우 빠름
단점 : 데이터가 정렬되어 있어야 함. 삽입/삭제가 잦으면 정렬 유지 비용이 큼

구현 예시

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

// test cases
console.log(binarySearch([1, 2, 3, 4, 5], 2)); // 1
console.log(binarySearch([1, 2, 3, 4, 5], 6)); // -1

해시 탐색 (Hash Table / 해시 맵)

키(key)를 해시 함수로 숫자(인덱스)로 바꿔서 바로 접근하는 방식. 보통 해시맵/ 객체로 구현

사물함 번호(해시값)를 통해 문을 바로 열어 물건(값)에 접근하는 것과 같다.

시간/공간 복잡도

평균 시간 : O(1) (탐색, 삽입, 삭제)
최악 시간 : O(n) (충돌이 매우 심한 경우 - 해시 설계/체이닝/리사이징으로 보완)
공간 : O(n)

언제 쓰나?

키로 값을 바로 찾고 싶을 때(예: 사용자 id ➡️ 사용자 정보)
빈번한 삽입/삭제가 있을 때

장단점

장점 : 매우 빠름(평균), 키-값 저장에 적합
단점 : 순서 유지 안됨(일부 구현은 순서 보장), 메모리 오버헤드, 해시 충돌 처리 필요

구현 예시

const map = new Map();
map.set('alice', {age:25});
console.log(map.get('alice')); // {age:25}

이진 탐색 트리 탐색 (BST Search)

이진 트리의 성질을 이용해 탐색한다. 왼쪽 서브트리는 루트보다 작은 값이고, 오른쪽 서브트리는 큰 값이다.

루트 노드를 기준으로 시작해 원하는 값보다 노드 값이 작으면 오른쪽 서브트리로 이동한다.

원하는 값보다 노드 값이 크면 왼쪽 서브트리로 이동한다.

이 과정을 반복해 원하는 값과 노드 값이 같으면 종료한다.

시간/공간 복잡도

평균 시간 : O(log n) (균형 트리일 때)
최악 시간 : O(n) (한쪽으로 치우친 경우)
공간 : O(height) (재귀스택)

장단점

장점 : 정렬된 데이터를 유지하며 데이터를 추가하거나 삭제 가능, 삽입/삭제/탐색 통합
단점 : 균형이 안 맞으면 성능 저하 ➡️AVL, 레드-블랙 트리 같은 균형 트리 사용

언제 쓰나?

범위 쿼리(예: 특정 범위의 값 전부 조회)나 정렬된 상태 유지하면서 삽입/삭제를 자주 해야 할 때

구현 예시

// 노드 정의
class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// 이진 탐색 트리 클래스
class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  // 노드 삽입
  insert(value) {
    const newNode = new Node(value);

    if (this.root === null) {
      this.root = newNode;
      return;
    }

    let current = this.root;

    while (true) {
      if (value === current.value) return; // 중복 방지

      if (value < current.value) {
        if (current.left === null) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else {
        if (current.right === null) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  // 탐색
  search(value) {
    let current = this.root;

    while (current !== null) {
      if (value === current.value) return true;
      if (value < current.value) current = current.left;
      else current = current.right;
    }

    return false; // 찾지 못한 경우
  }
}

// 테스트
const bst = new BinarySearchTree();
bst.insert(8);
bst.insert(3);
bst.insert(10);
bst.insert(1);
bst.insert(6);
bst.insert(14);

console.log(bst.search(6));  // true
console.log(bst.search(15)); // false

그래프 탐색 알고리즘 - BFS(너비 우선 탐색) & DFS(깊이 우선 탐색)

그래프란?

그래프(Graph)는 노드(Node)와 간선(Edge)으로 이루어진 자료구조. 즉, 여러 점(노드)이 서로 연결(간선)되어 있는 형태

A ─ B ─ C
│   │
D   E

➡️ A, B, C, D, E는 노드(node)
➡️ 선으로 연결된 관계(A-B, B-C, A-D, B-E)는 간선(edge)

인접 리스트 표현

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

graph = 그래프 전체 데이터
graph['A'] = ['B', 'D'] → A는 B, D와 연결되어 있다
각 노드는 key, 연결된 노드 배열은 value

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

시작 노드에서 가까운 노드부터 차례로 탐색한다. 즉, 넓게 퍼지면서 탐색

큐 자료구조를 사용해 구현한다.

시간/공간 복잡도

시간 : O(V + E) (V는 노드 수, E는 간선 수)
공간 : O(V)

동작순서

시작 노드에서 출발하여, 해당 노드와 인접한 모든 노드를 우선 탐색한다.
탐색 중 방문한 노드는 큐(Queue)에 저장
큐에서 하나의 노드를 꺼내어 해당 노드와 인접한 노드를 탐색
모든 인접 노드를 탐색한 후, 큐에서 다음 노드를 꺼내어 반복
큐가 비거나 모든 노드를 방문할 때까지 반복

장단점

장점 : 답이 되는 경로가 여러 개인 경우에도 최단 경로 보장
단점 : DFS에 비해 구현이 다소 복잡
노드의 수가 많을수록 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간(메모리)를 필요로 하게 됨.

언제 쓰나?

최단 거리 문제 (예 : 미로, 지도)
레벨별 탐색

구현 예시

function bfs(graph, start) {
  const visited = new Set();  // 방문한 노드 기록
  const queue = [start];      // 탐색 대기열
  visited.add(start);

  while (queue.length) {
    const node = queue.shift();  // 현재 탐색 노드
    console.log(node);           // 방문 순서 출력

    for (const neigh of graph[node] || []) {  // 인접 노드 순회
      if (!visited.has(neigh)) {              // 아직 방문 안 했다면
        visited.add(neigh);
        queue.push(neigh);                    // 큐에 추가
      }
    }
  }
}

➡️ 변수 설명

변수	의미	예시
graph	그래프 전체 구조 (인접 리스트)	{ A:['B','D'], ... }
start	탐색 시작 노드	'A'
visited	방문한 노드를 저장 (중복 방지)	Set { 'A', 'B' }
queue	탐색 순서를 관리 (FIFO 구조)	[ 'B', 'D' ]
node	현재 방문 중인 노드	'A', 'B'
neigh	현재 노드의 인접 노드	'B', 'D', 'C'

※ 예시 실행 (bfs(graph, 'A'))

1) A 방문 → queue = ['B', 'D']
2) B 방문 → queue = ['D', 'C', 'E']
3) D 방문 → queue = ['C', 'E']
4) C, E 방문

출력 순서:
➡️ A → B → D → C → E

깊이 우선 탐색 (depth-First Search)

한 노드를 시작으로, 갈 수 잇는 곳까지 깊게 들어가며 탐색하고, 막히면 이전 노드로 돌아가는(backtracking) 알고리즘

스택 또는 재귀를 사용한다.

시간/공간 복잡도

시간 : O(V + E) (V는 노드 수, E는 간선 수)
공간 : O(V)

동작순서

시작 노드에서 출발하여, 해당 노드의 자식 노드를 순차적으로 탐색한다.
탐색 중 방문한 노드는 스택(Stack)에 저장하거나 재귀 호출을 통해 처리한다.
현재 노드에서 더 이상 자식 노드를 탐색할 수 없을 때, 되돌아와서 이전 노드의 다른 자식 노드를 탐색
스택이 비거나 모든 노드를 방문할 때까지 반복

장단점

장점 : 간단하고 직관적인 구조로 구현이 쉬움
재귀 함수를 활용하면 코드가 간결해짐
현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용
단점 : 모든 경로를 탐색하기 때문에 그래프가 순환 구조일 경우 무한 루프에 빠질 수 있음
목표에 이르는 경로가 다수인 경우, DFS는 값에 도착하면 탐색을 종료하므로 얻어진 값이 최단 경로라는 보장 없음

언제 쓰나?

경로 탐색, 사이클 탐지
백트래킹 문제 (예: 미로 탈출, 조합 탐색)

구현 예시

function dfs(graph, node, visited = new Set()) {
  if (visited.has(node)) return;   // 이미 방문했으면 중복 방지
  visited.add(node);               // 방문 처리
  console.log(node);               // 현재 노드 출력

  for (const neigh of graph[node] || []) {
    dfs(graph, neigh, visited);    // 재귀적으로 깊게 탐색
  }
}

➡️ 변수 설명

변수	의미
graph	그래프 전체 구조
node	현재 탐색 중인 노드
visited	방문한 노드 기록
neigh	현재 노드의 인접 노드들

※ 예시 실행 (dfs(graph, 'A'))

1) A 방문
➡️ 이웃: ['B', 'D'], 먼저 B로 이동
2) B 방문
➡️ 이웃: ['A', 'C', 'E'], A는 이미 방문 → C로 이동
3) C 방문 ➡️ 이웃: ['B'], 모두 방문 → 돌아감
4) B의 다음 이웃 E 방문
5) E 방문 ➡️ ['B'], 이미 방문 ➡️ 돌아감
6) B 탐색 끝 ➡️ A로 돌아가서 D 방문

출력 순서:
👉 A → B → C → E → D

BFS vs DFS 비교 요약

구분	BFS	DFS
탐색 방식	넓게(레벨 순)	깊게(하나의 경로 끝까지)
자료구조	큐(Queue)	스택(Stack) or 재귀
주 용도	최단 거리, 레벨 탐색	경로 탐색, 백트래킹
대표 특징	가까운 노드부터 방문	한 경로를 끝까지 탐색