탐색 알고리즘 완벽 가이드

데이터에서 원하는 값을 찾는 것은 프로그래밍의 가장 기본적인 연산입니다. 이 글에서는 선형 탐색, 이진 탐색, DFS, BFS, 해시 탐색까지 개발자가 반드시 알아야 할 탐색 알고리즘을 정리합니다.

1. 탐색 알고리즘이란?

탐색 알고리즘(Search Algorithm)은 데이터 집합에서 특정 값이나 조건을 만족하는 요소를 찾는 알고리즘입니다. 어떤 자료구조를 사용하느냐에 따라 적합한 탐색 방법이 달라지며, 시간 복잡도도 크게 차이납니다.

2. 선형 탐색 (Linear Search)

배열의 처음부터 끝까지 순차적으로 요소를 하나씩 비교하는 가장 단순한 탐색 방법입니다.

• 시간 복잡도: O(n)
• 공간 복잡도: O(1)
• 전제 조건: 없음 (정렬 불필요)

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

const data = [5, 3, 8, 1, 9, 2];
console.log(linearSearch(data, 8)); // 2
console.log(linearSearch(data, 7)); // -1

단순하지만 정렬되지 않은 데이터에서는 사실상 유일한 선택지입니다. 데이터가 소규모일 때는 이진 탐색보다 오히려 빠를 수 있습니다(캐시 효율성).

3. 이진 탐색 (Binary Search)

정렬된 배열에서 중간값을 기준으로 탐색 범위를 절반씩 줄여나가는 알고리즘입니다.

• 시간 복잡도: O(log n)
• 공간 복잡도: O(1) (반복) / O(log n) (재귀)
• 전제 조건: 데이터가 반드시 정렬되어 있어야 함

반복 방식 구현

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;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

const sorted = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(sorted, 7));  // 3
console.log(binarySearch(sorted, 6));  // -1

재귀 방식 구현

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) return -1;

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

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

이진 탐색 과정 시각화

배열: [1, 3, 5, 7, 9, 11, 13, 15]
       0  1  2  3  4   5   6   7

target = 11

Step 1: left=0, right=7, mid=3
        [1, 3, 5, 7, 9, 11, 13, 15]
                  ^
        arr[3]=7 < 11 → 오른쪽으로 이동

Step 2: left=4, right=7, mid=5
        [_, _, _, _, 9, 11, 13, 15]
                         ^
        arr[5]=11 == 11 → 찾음! index=5

Lower Bound / Upper Bound

이진 탐색의 실전 변형으로, 범위 질의에 자주 사용됩니다.

// target 이상의 첫 번째 인덱스
function lowerBound(arr, target) {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
}

// target 초과의 첫 번째 인덱스
function upperBound(arr, target) {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] <= target) left = mid + 1;
    else right = mid;
  }
  return left;
}

💡 팁: upperBound(target) - lowerBound(target)로 특정 값의 개수를 O(log n)에 구할 수 있습니다.

4. 깊이 우선 탐색 (DFS)

그래프/트리에서 한 경로를 끝까지 탐색한 후 되돌아와 다른 경로를 탐색하는 방식입니다.

• 시간 복잡도: O(V + E) (V: 정점, E: 간선)
• 공간 복잡도: O(V)
• 구현 방식: 스택 또는 재귀
• 적합한 경우: 경로 탐색, 사이클 감지, 위상 정렬

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

function dfs(graph, start) {
  const visited = new Set();
  const stack = [start];
  const result = [];

  while (stack.length > 0) {
    const node = stack.pop();
    if (visited.has(node)) continue;

    visited.add(node);
    result.push(node);

    for (const neighbor of [...graph[node]].reverse()) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
      }
    }
  }
  return result;
}

console.log(dfs(graph, 'A'));
// ['A', 'B', 'D', 'E', 'F', 'C']

5. 너비 우선 탐색 (BFS)

그래프/트리에서 현재 노드와 가까운 노드부터 탐색하는 방식입니다.

• 시간 복잡도: O(V + E)
• 공간 복잡도: O(V)
• 구현 방식: 큐
• 적합한 경우: 최단 경로(가중치 없는 그래프), 레벨별 탐색

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

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return result;
}

console.log(bfs(graph, 'A'));
// ['A', 'B', 'C', 'D', 'E', 'F']

DFS vs BFS 시각화

        A
       / \
      B   C
     / \   \
    D   E - F

DFS (깊이 우선):  A → B → D → E → F → C
                  한 경로를 끝까지 파고든다

BFS (너비 우선):  A → B → C → D → E → F
                  가까운 노드부터 차례로 방문한다

6. 해시 탐색 (Hash Search)

해시 함수를 사용해 키를 인덱스로 변환하여 **O(1)**에 접근하는 방식입니다.

• 시간 복잡도: O(1) 평균 / O(n) 최악
• 공간 복잡도: O(n)
• 전제 조건: 해시 테이블 구축 필요

// JavaScript의 Map을 활용한 해시 탐색
const hashMap = new Map();
const items = [
  { id: 1, name: '사과' },
  { id: 2, name: '바나나' },
  { id: 3, name: '체리' }
];

// O(n)으로 해시 테이블 구축
items.forEach(item => hashMap.set(item.id, item));

// O(1)로 탐색
console.log(hashMap.get(2)); // { id: 2, name: '바나나' }
console.log(hashMap.has(5)); // false

7. 핵심 비교 표

8. 면접 단골 Q&A

Q1: 이진 탐색의 시간 복잡도가 O(log n)인 이유는?

매 단계마다 탐색 범위가 정확히 절반으로 줄어듭니다. n개의 요소에서 k번 비교하면 범위가 n/2^k이 되고, n/2^k = 1이 되는 시점인 k = log₂n번의 비교로 답을 찾습니다.

Q2: DFS와 BFS를 각각 언제 써야 하나요?

DFS는 경로 존재 여부 확인, 사이클 감지, 위상 정렬, 백트래킹에 적합합니다. BFS는 최단 경로(가중치 없는 그래프), 레벨 단위 처리, 최소 횟수 문제에 적합합니다.

Q3: mid 계산 시 오버플로우를 방지하는 방법은?

mid = (left + right) / 2 대신 mid = left + (right - left) / 2를 사용합니다. left + right가 정수 범위를 초과할 수 있지만, right - left는 항상 안전합니다.

Q4: 정렬 안 된 배열에서 O(n)보다 빠르게 탐색할 수 있나요?

단일 탐색이라면 O(n)이 최선입니다. 하지만 여러 번 탐색한다면 O(n log n)으로 정렬 후 이진 탐색을 반복하거나, O(n)으로 해시 테이블을 구축하여 O(1) 탐색이 가능합니다.

Q5: BFS가 최단 경로를 보장하는 조건은?

모든 간선의 가중치가 동일(보통 1)할 때입니다. 가중치가 다르면 다익스트라(Dijkstra), 음수 가중치가 있으면 벨만-포드(Bellman-Ford) 알고리즘을 사용합니다.

9. 핵심 키워드 정리