[C#] 탐색 알고리즘(선형탐색, 이진탐색)

01. 탐색 알고리즘 ( Search Algorithm )

1) 탐색 알고리즘 이란?

탐색 알고리즘은 주어진 데이터 집합에서 특정 항목을 찾는 방법을 제공합니다.

여기서는 가장 일반적인 탐색 알고리즘 몇 가지를 살펴보겠습니다.

 

2) 선형 탐색 ( Linear Search )

선형 탐색은 가장 단순한 탐색 알고리즘으로, 배열의 처음부터 끝까지 하나씩 비교하면서 원하는 값을 찾습니다.

• 배열이 정렬되어 있지 않을 경우 사용
• 시간 복잡도: 최악의 경우 O(n)

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

    return -1;
}

 

 

3) 이진 탐색 ( Binary Search )

정렬된 배열에서 빠르게 원하는 항목을 찾는 방법입니다.

중앙값과 찾고자 하는 항목을 비교하여 대상이 중앙값보다 작으면 왼쪽을, 크면 오른쪽을 탐색합니다.

• 배열이 정렬되어 있어야 함
• 시간 복잡도: 최악의 경우 O(log n)

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

        while (left <= right)
        {
            int middle = (left + right) / 2;

            if (arr[middle] == target) // 중간값이 찾고 있는 값이라면
            {
                return middle;
            }
            else if (arr[middle] < target)
            {
                left = middle + 1;
            }
            else
            {
                right = middle - 1;
            }
        }
        return -1;
    }

 

02. 그래프 ( Graph )

1) 그래프 개념과 종류

• 정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조
• 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나뉨
• 가중치 그래프(Weighted Graph)는 간선에 가중치가 있음
• https://visualgo.net/en/dfsbfs

2) 그래프 탐색 방법

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

시작 노드에서 시작하여 가능한 한 깊이 들어가서 노드를 탐색하고, 더 이상 방문할 노드가 없으면 이전 노드로 돌아가는 방식

• 시간 복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 

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

시작 노드에서 시작하여 가까운 노드부터 방문하고, 그 다음 레벨의 노드를 방문하는 방식입니다.

• 시간 복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)

using System;
using System.Collections.Generic;

public class Graph
{
    private int V; // 그래프의 정점 개수
    private List<int>[] adj; // 각 정점의 인접 리스트 배열

    public Graph(int v)
    {
        V = v;
        adj = new List<int>[V]; // 정점 개수만큼 리스트 생성
        for (int i = 0; i < V; i++)
        {
            adj[i] = new List<int>(); // 각 정점의 연결 리스트 초기화
        }
    }

    // 간선 추가 (v → w 방향으로 연결)
    public void AddEdge(int v, int w)
    {
        adj[v].Add(w);
    }

    // 깊이 우선 탐색 (DFS)
    public void DFS(int v)
    {
        bool[] visited = new bool[V]; // 방문 여부 기록
        DFSUtil(v, visited);
    }

    // DFS 재귀적으로 탐색
    private void DFSUtil(int v, bool[] visited)
    {
        visited[v] = true; // 현재 정점 방문 처리
        Console.Write($"{v} "); // 방문한 정점 출력

        // 현재 정점과 연결된 모든 정점 확인
        foreach (int n in adj[v])
        {
            if (!visited[n]) // 아직 방문하지 않은 정점이면 재귀 호출
            {
                DFSUtil(n, visited);
            }
        }
    }

    // 너비 우선 탐색 (BFS)
    public void BFS(int v)
    {
        bool[] visited = new bool[V]; // 방문 여부 기록
        Queue<int> queue = new Queue<int>(); // 탐색할 정점을 저장할 큐

        visited[v] = true; // 시작 정점 방문 처리
        queue.Enqueue(v);  // 큐에 삽입

        while (queue.Count > 0) // 큐가 빌 때까지 반복
        {
            int n = queue.Dequeue(); // 큐에서 꺼내기
            Console.Write($"{n} ");  // 방문한 정점 출력

            // 현재 정점과 연결된 모든 정점 확인
            foreach (int m in adj[n])
            {
                if (!visited[m]) // 아직 방문하지 않았다면
                {
                    visited[m] = true; // 방문 처리
                    queue.Enqueue(m);  // 큐에 삽입 (나중에 탐색)
                }
            }
        }
    }
}

public class Program
{
    public static void Main()
    {
        Graph graph = new Graph(6); // 정점 6개짜리 그래프 생성

        // 간선 추가
        graph.AddEdge(0, 1);
        graph.AddEdge(0, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(2, 3);
        graph.AddEdge(2, 4);
        graph.AddEdge(3, 4);
        graph.AddEdge(3, 5);
        graph.AddEdge(4, 5);

        Console.WriteLine("DFS traversal:");
        graph.DFS(0); // DFS 시작
        Console.WriteLine();

        Console.WriteLine("BFS traversal:");
        graph.BFS(0); // BFS 시작
        Console.WriteLine();
    }
}

 

03. 최단 경로 알고리즘 ( Shortest path problem )

1) 최단 경로 알고리즘 개념과 종류

• 다익스트라 알고리즘(Dijkstra Algorithm) 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 음의 가중치를 갖는 간선이 없는 경우에 사용됩니다.
• 벨만-포드 알고리즘(Bellman-Ford Algorithm) 음의 가중치를 갖는 간선이 있는 그래프에서도 사용할 수 있는 최단 경로 알고리즘입니다. 음수 사이클이 있는 경우에도 탐지할 수 있습니다.
• A 알고리즘 (A-star Algorithm)* 특정 목적지까지의 최단 경로를 찾는 알고리즘입니다. 휴리스틱 함수를 사용하여 각 정점까지의 예상 비용을 계산하고, 가장 낮은 예상 비용을 가진 정점을 선택하여 탐색합니다.

다익스타라 알고리즘 예제

using System;

class DijkstraExample
{
    static int V = 6; // 정점의 수

    // 주어진 그래프의 최단 경로를 찾는 다익스트라 알고리즘
    static void Dijkstra(int[,] graph, int start)
    {
        int[] distance = new int[V]; // 시작 정점으로부터의 거리 배열
        bool[] visited = new bool[V]; // 방문 여부 배열

        // 거리 배열 초기화
        for (int i = 0; i < V; i++)
        {
            distance[i] = int.MaxValue;
        }

        distance[start] = 0; // 시작 정점의 거리는 0

        // 모든 정점을 방문할 때까지 반복
        for (int count = 0; count < V - 1; count++)
        {
            // 현재 방문하지 않은 정점들 중에서 최소 거리를 가진 정점을 찾음
            int minDistance = int.MaxValue;
            int minIndex = -1;

            for (int v = 0; v < V; v++)
            {
                if (!visited[v] && distance[v] <= minDistance)
                {
                    minDistance = distance[v];
                    minIndex = v;
                }
            }

            // 최소 거리를 가진 정점을 방문 처리
            visited[minIndex] = true;

            // 최소 거리를 가진 정점과 인접한 정점들의 거리 업데이트
            for (int v = 0; v < V; v++)
            {
                if (!visited[v] && graph[minIndex, v] != 0 && distance[minIndex] != int.MaxValue && distance[minIndex] + graph[minIndex, v] < distance[v])
                {
                    distance[v] = distance[minIndex] + graph[minIndex, v];
                }
            }
        }

        // 최단 경로 출력
        Console.WriteLine("정점\t거리");
        for (int i = 0; i < V; i++)
        {
            Console.WriteLine($"{i}\t{distance[i]}");
        }
    }

    static void Main(string[] args)
    {
        int[,] graph = {
            { 0, 4, 0, 0, 0, 0 },
            { 4, 0, 8, 0, 0, 0 },
            { 0, 8, 0, 7, 0, 4 },
            { 0, 0, 7, 0, 9, 14 },
            { 0, 0, 0, 9, 0, 10 },
            { 0, 0, 4, 14, 10, 0 }
        };

        int start = 0; // 시작 정점

        Dijkstra(graph, start);
    }
}