탐색 알고리즘 ( Search Algorithms )

탐색 알고리즘 ( Search Algorithms )

C# 에서 탐색 알고리즘은 데이터 안에서 원하는 값을 찾는 방법이다.

탐색은 정렬 여부 / 탐색 범위 / 구조 형태 ( 리스트 , 트리 , 그래프 등 ) 에 따라 여러 가지로 나뉜다.

 

 

1. 기본 탐색 알고리즘 ( 배열 , 리스트 )

데이터가 정렬되어 있는지 여부에 따라 달라진다.

 

1-1. 선형 탐색 ( Linear Search )

• 하나씩 순서대로 비교하는 가장 단순한 방법
• 정렬되어 있지 않아도 사용 가능
• BigO : O(n)

int LinearSearch(int[] arr, int target)
{
    for (int i = 0; i < arr.Length; i++)
        if (arr[i] == target) return i;
    return -1;
}

 

 

1-2. 이진 탐색 ( Binary Search )

• 정렬된 배열에서 중간값을 기준으로 탐색
• 중간값보다 작으면 왼쪽 , 크면 오른쪽 절반만 탐색
• BigO : O(log n)

int BinarySearch(int[] arr, int target)
{
    int left = 0, right = arr.Length - 1;

    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

C# 에서는 Array.BinarySearch( ) 메서드가 이미 구현되어 있다.

 

 

2. 트리 탐색 ( Tree Search )

트리 구조에서 노드를 탐색할 때 사용한다.

 

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

• 루트에서 시작해서 끝까지 탐색 후 되돌아온다
• 스택 ( Stack ) 또는 재귀 ( Recursion ) 로 구현한다
• BigO : O(V + E) (정점 + 간선)

void DFS(Node node)
{
    if (node == null) return;
    Console.WriteLine(node.value);
    foreach (var child in node.children)
        DFS(child);
}

 

 

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

• 가까운 노드부터 차례대로 탐색한다
• 큐 ( Queue ) 사용한다
• BigO : O(V + E)

void BFS(Node start)
{
    Queue<Node> q = new Queue<Node>();
    q.Enqueue(start);

    while (q.Count > 0)
    {
        Node node = q.Dequeue();
        Console.WriteLine(node.value);
        foreach (var child in node.children)
            q.Enqueue(child);
    }
}

 

 

3. 그래프 탐색 ( Graph Search )

그래프는 트리보다 일반화된 구조로 DFS / BFS 가 그대로 사용된다.

• DFS : 백트래킹 , 미로 탐색 등에 자주 사용
• BFS : 최단 거리 탐색에 자주 사용 ( A* 의 기본 원리 )