[알고리즘] 탐색

# 탐색

: 주어진 데이터에서 특정 값을 찾는 방법

 

알고리즘	언제 사용하면 좋을까?	시간복잡도
순차 탐색 (Linear Search)	정렬되지 않은 데이터에서 특정 값을 찾을 때	O(N)
이진 탐색 (Binary Search)	정렬된 데이터에서 빠르게 찾을 때	O(log N)
해시 탐색 (Hash Search)	특정 키에 대한 값을 빠르게 찾을 때	O(1)
DFS (깊이 우선 탐색)	그래프에서 경로를 찾거나 미로를 탐색할 때	O(V + E)
BFS (너비 우선 탐색)	최단 거리를 찾을 때	O(V + E)

 

1. 선형 탐색 (linear search)

: 앞에서부터 하나하나 찾는다

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

// 예제 실행
let numbers = [10, 20, 30, 40, 50];
console.log(linearSearch(numbers, 30)); // 2
console.log(linearSearch(numbers, 100)); // -1 (없음)

 

- find() , findIndex() 메서드

const result = dictionary.find(el=>el.word ==='a');
return result;

const result = dictionary.findIndex(el=>el.word ==='a');
return result;

 

그외

- findLast()

- findLastIndex()

- includes()

- some()

- filter()

 

2. 이진 탐색 ( binary search)

: 찾고자 하는 데이터를 중간을 잘라서 찾기

 

 

[ 방식 ]

중요 ** 이미 정렬된 상태여야 이진 탐색을 할 수 있다.

1. 전체 배열의 중간 인덱스의 원소와 검색값을 비교한다.

2. 검색값이 배열의 좌우 한 곳에 포함되면 다시 1단계를 반복한다.

 

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

    while (left <= right) {
        let 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; // 찾지 못함
}

// 예제 실행
let sortedArr = [10, 20, 30, 40, 50, 60, 70];
console.log(binarySearch(sortedArr, 30)); // 🔹 2
console.log(binarySearch(sortedArr, 100)); // 🔹 -1 (없음)

 

 

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

: 스택구조 탐색 방법 중 하나

최대한 깊게 탐색해보자

그래프나 트리에서 한 경로를 끝까지 탐색한 후, 다시 돌아와 다른 경로를 탐색하는 방식

일단 마지막 depth까지 제일 깊게 쭉 찾아보고 그다음 옆동네로 간다

 

스택구조 : 후입선출 (LIFO)

 

[ 코드 흐름 ]

=> 상하좌우 direction + 해당 4가지 방향으로 움직이는 for 문 작성

=> 접근 가능한 경로일 때(조건부) 재귀적으로 dfs 를 실행

 

 

예시 전체 코드 )

function dfs(maze, position = [0, 0], path = []) { // position: 출발점, path: 경로배열
    const [x, y] = position; // 좌표값선언
    
    if(maze[x][y] === "E") return [...path, position]; // 목적지 도착시 경로 반환
   
    // 이동 방향 (상, 하, 좌, 우)
    let directions = [
        [-1, 0], [1, 0], [0, -1], [0, 1]
    ];
    
       // 경로 탐색 (DFS)
    for (let [dx, dy] of directions) {
     let newX = x + dx,
         newY = y + dy;   // 이전 좌표에서 방향 1씩 이동
         
     if( newX >= 0 &&
         newX < maze.length &&
         newY >= 0 &&
         newY < maze[0].length &&   // 미로 밖으로 나가는 것 방지
         (maze[newX][newY] === 0 || maze[newX][newY] === "E") // 열린길 or 도착지 일 때만 이동
       ) { 
         maze[x][y] = 1; // 방문한 곳을 표시 + 벽처럼 처리
         let result = dfs(maze, [newX, newY], [...path, position]); // 재귀적으로 실행
         if (result) return result;
         }
     }
     return null;
   }


// 🔥 테스트 실행
const maze = [
    ["S", 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, "E"]
];

console.log(dfs(maze));

function findPath(maze, position = [0, 0], path = []) { // position: 출발점, path: 경로배열
    const [x, y] = position; // 좌표값선언
    const rows = maze.length;
    const cols = maze[0].length;

    // 이동 방향 (상, 하, 좌, 우)
    const directions = [
        [-1, 0], [1, 0], [0, -1], [0, 1]
    ];

    // 목적지 (출구는 오른쪽 아래)
    const exit = [rows - 1, cols - 1];

    // 범위 밖이거나, 벽(1)이거나, 이미 방문한 곳이면 중단
    if (x < 0 || x >= rows || y < 0 || y >= cols || maze[x][y] === 1) {
        return null;
    }

    // 이미 방문한 경로 방지
    if (path.some(([px, py]) => px === x && py === y)) {
        return null;
    }

    // 경로 추가
    path.push([x, y]);

    // 목적지 도착 시 경로 반환
    if (x === exit[0] && y === exit[1]) {
        return path;
    }

    // 다음 경로 탐색 (DFS)
    for (const [dx, dy] of directions) {
        const nextPath = findPath(maze, [x + dx, y + dy], [...path]);
        if (nextPath) {
            return nextPath;
        }
    }

    return null; // 출구에 도달할 수 없는 경우
}

// 🔥 테스트 실행
const maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
];

console.log(findPath(maze));

 

 

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

: 시작 노드에서 가까운 노드부터 탐색하는 알고리즘

 

- Queue(큐) 를 사용하여 방문할 노드를 순서대로 탐색

 

[ 사용 유형 ]

최단거리탐색

 

 

[ 코드 흐름 ]

=> 인접 리스트 형식으로 변환 (인접한 지점들만 배열 값으로 보여주는 객체 형태)

const list = {}
tickets.forEach(([u,v])=>{
  if(!list[u]) list[u]= [];
  list[u].push(v);
});

 

function bfs(graph, startNode,targetNode) {
    let visited = {}; // 방문한 노드 저장
    let queue = []; // 탐색할 정점을 저장할 큐
    const distances = {}; // 시작 정점으로부터의 거리를 저장할 객체
    
    visited[startNode] = true; // 시작 정점을 방문 처리
    queue.push(startNode); // 시작 정점을 큐에 추가
    distances[startNode] = 0; // 시작 정점까지의 거리는 0

    while (queue.length > 0) {
        let node = queue.shift(); // 큐에서 노드를 하나씩 꺼내기
        
      if(node === targetNode) {
        return distances[node];
        
      }
        
        const adjacentNodes = graph[node];
        for (let i = 0 ; i < adjacentNodes.length; i++) {
        const adjacentNode = adjacentNodes[i];
            if (!visited[adjacentNode]) { // 방문하지 않은 노드라면
                visited[adjacentNode] = true; // 방문 처리
                queue.push(adjacentNode); // 큐에 삽입
                distances[adjacentNode] = distances[node] + 1; // 🔥 거리 업데이트
            }
        }
    }
  return -1;
}

// 🔥 테스트 실행 (그래프 예제)
const graph = {
    1: [2, 3, 4],
    2: [5, 6],
    3: [4],
    4: [3,6],
    5: [1,2],
    6: [7],
    7: [5,6]
};

console.log(bfs(graph, 1,7));

 

function bfs(graph, startNode) {
    let queue = [startNode]; // 큐(Queue) 초기화
    let visited = new Set(); // 방문한 노드 저장
    visited.add(startNode); 

    while (queue.length > 0) {
        let node = queue.shift(); // 큐에서 노드 꺼내기
        console.log(node); // 방문한 노드 출력

        for (let neighbor of graph[node]) {
            if (!visited.has(neighbor)) { // 방문하지 않은 노드라면
                visited.add(neighbor); // 방문 처리
                queue.push(neighbor); // 큐에 삽입
            }
        }
    }
}

// 🔥 테스트 실행 (그래프 예제)
const graph = {
    1: [2, 3, 4],
    2: [5, 6],
    3: [7],
    4: [],
    5: [],
    6: [],
    7: []
};

bfs(graph, 1);

 

 

✅ DFS (깊이 우선 탐색)

• 재귀 방식
  → 함수 안에서 자기 자신을 계속 호출.
• 스택 방식
  → 직접 stack 배열을 만들어 while 루프로 돌림.

→ 두 가지 방식

 

✅ BFS (너비 우선 탐색)

• 큐(queue) 방식
  → 큐 자료구조를 사용해 탐색 순서를 관리.

→ 사실상 큐 방식 한 가지