탐색 알고리즘

• 특정한 경로, 값을 찾는 방법
• 주어진 데이터 집합에서 특정 항목을 찾는 방법을 제공.

종류

• 선형 탐색 Linear Search
• 이진 탐색 Binary 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;
}

이진 탐색

정렬된 배열에서 빠르게 원하는 항목을 찾는 방법.
중간값을 찾은 후, 찾을 항목과 비교해서 중간값이 작다면 왼쪽으로, 크다면 오른쪽으로 범위를 좁혀가며 찾는 방법.

• 시간 복잡도 : 최악의 경우 O(log n)
• 미리 정렬된 배열에서 사용하는 알고리즘
• 중앙값과 비교하며 범위를 반씩 줄여나가는 방식

int BinarySearch(int[] arr, int target)
{
    int left = 0;
    int 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;
}

그래프 Graph

개발하면서 다루는 자료형들이 항상 1차원 배열같이 선형적 구조일 수는 없음.

그래프

정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조

종류

방향 그래프 Directed Graph :

정점들 간에 방향을 가진 간선으로 구성.
이동할 수 있는 방향이 제한된 그래프.

무방향 그래프 Undirected Graph :

정점들 간 방향 구분이 없는 간선으로 구성.
이동 방향에 제한이 없는 그래프.

가중치 그래프 Weighted Graph :

간선에 가중치가 있음.
간선에 대해 비용이나 거리 개념을 적용할 때 사용.

탐색 방법

그래프 및 트리의 탐색 방법입니다.

• 깊이 우선 탐색 (DFS : Depth-First Search)
• 너비 우선 탐색 (BFS : Breadth-First Search)

DFS

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

• 단절점 찾기에 유용

BFS

루트에서 시작해서 가장 가까운 노드(동등하거나 이보다 바로 아래 레벨)부터 방문하고, 그 다음 레벨 노드를 방문하는 방식

• 간선의 비용이 동일할 때 최단거리 탐색에 유용

시간 복잡도

둘다 최악의 경우 O(V + E) (V: 노드, 정점의 수, E: 간선의 수)

예제

namespace CodePractice
{
    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>(); //이 버텍스와 연결된 점들이 들어올 곳
        }

        public void AddEdge(int v, int w) 
        {
            adj[v].Add(w);
        }

        public void DFS(int startVertex)
        {
            // 방문 여부 체크
            bool[] visited = new bool[V];
            DFSUtil(startVertex, ref visited);
        }
		// 재귀적 호출로 구현한 형태
        // 스택을 이용하는 방법도 있음
        void DFSUtil(int visitVertex, ref bool[] visited)
        {
            visited[visitVertex] = true;
            Console.Write($"{visitVertex} ");

            foreach (int v in adj[visitVertex])
            {
                if (!visited[v])
                    DFSUtil(v, ref visited);
            }
        }
		
        // 큐를 사용해서 만든 형태
        public void BFS(int startVerex)
        {
            bool[] visited = new bool[V];
            Queue<int> qu = new Queue<int>();

            visited[startVerex] = true;
            qu.Enqueue(startVerex);

            while(qu.Count > 0)
            {
                int v = qu.Dequeue();
                Console.Write($"{v} ");

                foreach (int next in adj[v])
                {
                    if (!visited[next])
                    {
                        visited[next] = true;
                        qu.Enqueue(next);
                    }
                }
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Graph g = new Graph(6);

            g.AddEdge(0, 1);
            g.AddEdge(0, 2);
            g.AddEdge(1, 3);
            g.AddEdge(2, 3);
            g.AddEdge(2, 4);
            g.AddEdge(3, 4);
            g.AddEdge(3, 5);
            g.AddEdge(4, 5);

            Console.WriteLine("DFS : ");
            g.DFS(0); // 0 1 3 4 5 2
            Console.WriteLine();

            Console.WriteLine("BFS : ");
            g.BFS(0); // 0 1 2 3 4 5
            Console.WriteLine();
        }
    }
}

최단 경로 알고리즘 Shortest Path Problem

종류

다익스트라 알고리즘 Dijikstra Algorithm

가중치가 있는 그래프에서
하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘.
음의 가중치가 없는 그래프에서 사용.

벨만-포드 알고리즘 Bellman-Ford Algorithm

가중치가 있는 그래프에서
음의 가중치를 갖는 간선이 있는 그래프에서도 사용가능한 최단 경로 알고리즘.
음수 사이클이 있는 경우에도 탐지 가능.

A* 알고리즘 A-start 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);
    }
}