탐색 알고리즘 (Searching Algorithms)

탐색 알고리즘은 주어진 데이터 내에서 특정한 값을 찾는 방법을 정의합니다. 탐색 알고리즘은 주로 정렬된 또는 정렬되지 않은 배열, 트리, 그래프 등 다양한 자료구조에서 사용됩니다. 이 페이지에서는 대표적인 탐색 알고리즘인 선형 탐색, 이진 탐색, 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)을 설명합니다.

1. 선형 탐색 (Linear Search)

선형 탐색은 데이터셋의 처음부터 끝까지 순차적으로 값을 비교하면서 탐색하는 방법입니다. 정렬되지 않은 배열에서도 사용할 수 있으며, 간단하고 직관적이지만 비효율적인 탐색 방법입니다.


// 선형 탐색 예제 코드 (JavaScript)
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;  // 타겟 값이 있으면 해당 인덱스 반환
        }
    }
    return -1;  // 타겟 값이 없으면 -1 반환
}

let arr = [34, 22, 10, 19, 17];
console.log(linearSearch(arr, 19));  // 3 출력
console.log(linearSearch(arr, 50));  // -1 출력

선형 탐색의 시간 복잡도는 O(n)으로, 데이터가 많을수록 탐색 시간이 길어집니다. 그러나 작은 데이터셋에서는 효율적일 수 있습니다.

2. 이진 탐색 (Binary Search)

이진 탐색은 정렬된 배열에서 중간 값을 기준으로 탐색 범위를 반으로 줄여나가는 방법입니다. 중간 값과 타겟 값을 비교하여, 타겟이 중간 값보다 크면 오른쪽 절반을, 작으면 왼쪽 절반을 탐색합니다. 이진 탐색은 매우 효율적인 탐색 방법이지만, 데이터가 미리 정렬되어 있어야만 사용할 수 있습니다.


// 이진 탐색 예제 코드 (JavaScript)
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;  // 타겟 값이 없으면 -1 반환
}

let sortedArr = [10, 17, 19, 22, 34];
console.log(binarySearch(sortedArr, 19));  // 2 출력
console.log(binarySearch(sortedArr, 50));  // -1 출력

이진 탐색의 시간 복잡도는 O(log n)으로 매우 효율적입니다. 그러나 반드시 데이터가 정렬되어 있어야만 사용할 수 있습니다.

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

깊이 우선 탐색(DFS)은 트리 또는 그래프에서 탐색을 수행할 때, 한 노드의 자식을 깊게 탐색한 후 더 이상 깊이 탐색할 수 없을 때 다음 노드를 탐색하는 방법입니다. DFS는 스택을 사용하여 구현하거나 재귀적으로 구현할 수 있습니다.


// 깊이 우선 탐색(DFS) 예제 코드 (JavaScript)
function dfs(graph, start, visited = new Set()) {
    console.log(start);
    visited.add(start);

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

const graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6],
    4: [],
    5: [],
    6: []
};

dfs(graph, 1);  // 출력: 1 2 4 5 3 6

DFS의 시간 복잡도는 O(V + E)로, 여기서 V는 노드의 수, E는 간선의 수를 의미합니다. DFS는 그래프의 모든 노드를 방문하기 위해 사용됩니다.

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

너비 우선 탐색(BFS)은 그래프 또는 트리에서 탐색을 수행할 때, 현재 노드의 모든 인접한 노드를 탐색한 후 다음 레벨로 이동하여 탐색하는 방법입니다. BFS는 주로 큐를 사용하여 구현됩니다.


// 너비 우선 탐색(BFS) 예제 코드 (JavaScript)
function bfs(graph, start) {
    let queue = [start];
    let visited = new Set();

    visited.add(start);

    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],
    2: [4, 5],
    3: [6],
    4: [],
    5: [],
    6: []
};

bfs(graph, 1);  // 출력: 1 2 3 4 5 6

BFS의 시간 복잡도는 DFS와 마찬가지로 O(V + E)입니다. BFS는 최단 경로를 찾는 데 유용합니다.

5. DFS와 BFS의 차이점

DFS와 BFS는 그래프 탐색 알고리즘으로, 서로 다른 방식으로 그래프를 탐색합니다.

DFS (깊이 우선 탐색): 먼저 깊게 탐색하고, 더 이상 갈 곳이 없을 때 돌아옵니다. 스택 또는 재귀를 사용합니다.
BFS (너비 우선 탐색): 먼저 가까운 노드를 탐색한 후 점차 멀리 있는 노드를 탐색합니다. 큐를 사용하여 구현됩니다.

DFS는 경로 탐색 문제에서 사용되며, BFS는 최단 경로 문제에서 유용합니다. 또한, DFS는 모든 경로를 탐색하는데 적합하고, BFS는 최단 경로 탐색에 최적화되어 있습니다.

결론

탐색 알고리즘은 다양한 자료구조에서 데이터를 찾는 데 사용됩니다. 선형 탐색과 이진 탐색은 배열에서 데이터를 찾는 데 주로 사용되며, DFS와 BFS는 그래프나 트리 구조에서 경로를 찾는 데 자주 사용됩니다. 각 알고리즘은 상황에 맞게 선택해야 하며, 데이터의 구조와 크기에 따라 시간 복잡도와 효율성을 고려하여 적절한 알고리즘을 선택하는 것이 중요합니다.

DAILY IS COMING

탐색 알고리즘 (Searching Algorithms) 요약