24.01.18 TIL - [C#] 기초 (14) | 알고리즘 下 | 탐색 알고리즘 + 고급 알고리즘

JJwoo·2024년 1월 18일

C 내일배움캠프

C#

목록 보기

19/20

탐색 알고리즘 ( Search Algorithm )

탐색 알고리즘은 주어진 데이터 집합에서 특정 항목을 찾는 방법을 제공합니다. 여기서는 가장 일반적인 탐색 알고리즘 몇 가지를 살펴보겠습니다.

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 mid = (left + right) / 2;

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

    return -1;
}

🧫 그래프

1) 그래프 개념과 종류

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

방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나뉨

가중치 그래프(Weighted Graph)는 간선에 가중치가 있음

https://visualgo.net/en/dfsbfs

2) 그래프 탐색 방법

깊이 우선 탐색 (Depth-First Search, DFS)
- DFS는 트리나 그래프를 탐색하는 알고리즘 중 하나로, 루트에서 시작하여 가능한 한 깊이 들어가서 노드를 탐색하고, 더 이상 방문할 노드가 없으면 이전 노드로 돌아가는 방식입니다.
- 시간 복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)
너비 우선 탐색 (Breadth-First Search, BFS)
- 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>();
        }
    }

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

    public void DFS(int v)
    {
        bool[] visited = new bool[V];
        DFSUtil(v, visited);
    }

    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);
            }
        }
    }

    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);

        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);
        Console.WriteLine();

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


이 코드는 C#을 사용하여 그래프를 구현하고, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 알고리즘을 적용하는 예제입니다. 그래프는 정점과 이들을 연결하는 간선으로 구성되며, 여기서는 인접 리스트를 사용하여 각 정점의 이웃을 저장합니다.


Graph 클래스

V: 그래프의 정점 개수를 나타냅니다.
adj: 각 정점에 인접한 정점들의 리스트를 저장하는 배열입니다.
AddEdge: 두 정점을 연결하는 간선을 그래프에 추가합니다.
DFS와 BFS: 각각 깊이 우선 탐색과 너비 우선 탐색을 수행합니다.



DFS (깊이 우선 탐색)

DFSUtil 재귀 함수를 사용하여, 아직 방문하지 않은 인접 정점으로 깊이 들어가면서 탐색합니다.
방문한 정점을 기록하는 visited 배열을 사용합니다.



BFS (너비 우선 탐색)

Queue를 사용하여 각 레벨의 정점을 순차적으로 탐색합니다.
방문하지 않은 인접 정점을 큐에 추가하고, 큐에서 제거된 정점을 탐색합니다.

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;

        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);
    }
}

이 코드는 C#으로 구현된 다익스트라 알고리즘의 예시입니다. 다익스트라 알고리즘은 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 코드는 특히 가중치가 있는 무방향 그래프에 적용됩니다.

코드 해석

변수 선언
V: 그래프의 정점 수 (6)

graph: 그래프의 인접 행렬 표현. 각 셀 graph[i, j]는 정점 i에서 j로 가는 간선의 가중치를 나타냅니다. 간선이 없으면 0입니다.

distance: 시작 정점에서 다른 모든 정점까지의 현재까지 알려진 최단 거리를 저장합니다.

visited: 각 정점이 최단 경로 트리에 포함되었는지 여부를 나타냅니다.

다익스트라 알고리즘
모든 정점의 distance 값을 무한대로 초기화합니다.
시작 정점의 distance를 0으로 설정합니다.
모든 정점에 대해 최단 경로를 찾습니다.
방문하지 않은 정점 중 distance가 가장 작은 정점을 찾습니다.
해당 정점을 방문 처리합니다 (visited[minIndex] = true).
해당 정점에 인접한 모든 정점의 distance 값을 업데이트합니다.

결과 출력
각 정점까지의 최단 거리를 출력합니다.

01. 동적 프로그래밍 ( Dynamic Programming )

✔️ 작은 문제 단위로 쪼개서 반복하여 푸는 방식

1) 동적 프로그래밍 이란?
- 동적 프로그래밍은 큰 문제를 작은 하위 문제로 분할하여 푸는 접근 방식입니다.
- 작은 하위 문제의 해결 방법을 계산하여 저장하고, 이를 이용하여 큰 문제의 해결 방법을 도출합니다. 이러한 저장 과정을 "메모이제이션(Memoization)"이라고 합니다.
- 동적 프로그래밍은 중복되는 하위 문제들을 효율적으로 해결하기 위해 사용됩니다.
- 일반적으로 재귀적인 구조를 가지며, 하향식(Top-down)과 상향식(Bottom-up) 두 가지 방법으로 구현할 수 있습니다.
- 동적 프로그래밍은 최적 부분 구조와 중복 부분 문제의 특징을 가진 문제들을 효과적으로 해결할 수 있습니다.

- 2) 동적 프로그래밍 실습 예제

    // 문제: 피보나치 수열의 n번째 항을 구하는 함수를 작성하세요.
    public int Fibonacci(int n)
    {
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
    
        for(int i = 2; i <= n; i++)
        {
            dp[i] = dp[i-1] + dp[i-2];
        }
    
        return dp[n];
    }

해설

위 코드는 피보나치 수열의 n번째 항을 구하는 문제를 해결하는 C# 코드입니다.
이 문제를 해결하는 데는 동적 프로그래밍 방법을 사용하였으며, 시간 복잡도는 O(n)이고 공간 복잡도는 O(n)입니다.

02. 그리디 알고리즘 ( Greedy Algorithm )

✔️ 현재에 집중하는 알고리즘

1) 그리디 알고리즘 이란?
- 그리디 알고리즘은 각 단계에서 가장 최적인 선택을 하는 알고리즘입니다.
- 각 단계에서 가장 이익이 큰 선택을 하여 결과적으로 최적해에 도달하려는 전략을 따릅니다.
- 그리디 알고리즘은 지역적인 최적해를 찾는데 초점을 맞추기 때문에 항상 전역적인 최적해를 보장하지는 않습니다.
- 그리디 알고리즘은 간단하고 직관적인 설계가 가능하며, 실행 시간이 매우 빠른 편입니다.
- 그리디 알고리즘은 최적해를 찾는 문제에 사용되는 경우가 많지만, 일부 문제에서는 최적해를 보장하지 않을 수 있습니다.

2) 그리디 알고리즘 실습 예제

// 문제: 주어진 동전들로 특정 금액을 만드는데 필요한 최소 동전 수를 구하는 함수를 작성하세요.
public int MinCoins(int[] coins, int amount)
{
    Array.Sort(coins);
    int count = 0;

    for(int i = coins.Length - 1; i >= 0; i--)
    {
        while(amount >= coins[i])
        {
            amount -= coins[i];
            count++;
        }
    }

    if(amount > 0) return -1; 

    return count;
}

해설

위 코드는 주어진 동전들로 특정 금액을 만드는데 필요한 최소 동전 수를 구하는 문제를 해결하는 C# 코드입니다.
이 문제를 해결하는 데는 그리디 알고리즘을 사용하였으며, 시간 복잡도는 동전의 개수에 비례하는 O(n)이고, 공간 복잡도는 O(1)입니다.

03. 분할 정복 ( Divide and Conquer )

✔️ 작은 부분부터 착실히 해결해 나가자

1) 분할 정복 이란?
- 큰 문제를 작은 부분 문제로 분할하므로 문제의 크기에 따른 성능 향상이 가능합니다.
- 재귀적인 구조를 가지므로 문제 해결 방법의 설계가 단순하고 직관적입니다.
- 분할된 부분 문제들은 독립적으로 해결되므로 병렬 처리에 유리합니다.
- 하지만 문제를 분할할 때 발생하는 부분 문제들 간의 중복 계산이 발생할 수 있습니다. 이런 경우에는 중복 계산을 피하기 위한 메모이제이션 등의 기법을 활용하여 성능을 향상시킬 수 있습니다.

2) 분할 정복 실습 예제

// 문제: 주어진 배열을 정렬하는 함수를 작성하세요. (퀵 정렬 사용)
public void QuickSort(int[] arr, int low, int high)
{
    if(low < high)
    {
        int pi = Partition(arr, low, high);

        QuickSort(arr, low, pi - 1);  // Before pi
        QuickSort(arr, pi + 1, high); // After pi
    }
}

int Partition(int[] arr, int low, int high)
{
    int pivot = arr[high];
    int i = (low - 1);

    for(int j = low; j <= high - 1; j++)
    {
        if(arr[j] < pivot)
        {
            i++;
            Swap(arr, i, j);
        }
    }
    Swap(arr, i + 1, high);
    return (i + 1);
}

void Swap(int[] arr, int a, int b)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

해설

위 코드는 주어진 배열을 정렬하는 문제를 해결하는 C# 코드입니다. 여기서는 퀵 정렬 알고리즘을 사용하였습니다.
이 문제를 해결하는 데는 분할 정복 방법을 사용하였으며, 시간 복잡도는 평균적으로 O(n log n)이고, 최악의 경우(이미 정렬된 배열 등)에는 O(n^2)가 됩니다. 공간 복잡도는 O(log n)입니다. (재귀 호출 스택의 크기를 고려)

🎞 동적 프로그래밍, 그리디 알고리즘, 분할 정복 차이

알고리즘	정의	특징	시간 복잡도	공간 복잡도
동적 프로그래밍	큰 문제를 작은 하위 문제로 분할하여 푸는 접근 방식	- 작은 하위 문제의 해결 방법을 계산하여 저장 - "메모이제이션" 사용 - 재귀적 구조, 하향식 또는 상향식	문제에 따라 다름, 일반적으로 O(n) 또는 O(n^2)	O(n)
그리디 알고리즘	각 단계에서 가장 최적인 선택을 하는 알고리즘	- 지역적 최적해에 집중 - 전역적 최적해를 보장하지 않음 - 간단하고 직관적인 설계	문제에 따라 다름, 일반적으로 O(n)	O(1)
분할 정복	큰 문제를 작은 부분 문제로 분할하여 해결하는 방식	- 재귀적 구조 - 부분 문제들은 독립적으로 해결 - 병렬 처리에 유리 - 중복 계산을 피하기 위한 기법 필요	일반적으로 O(n log n), 최악 O(n^2)	O(log n)

JJwoo

개발 모코코

이전 포스트

24.01.18 TIL - [C#] 기초 (14) | 알고리즘 上 | 정렬 알고리즘

다음 포스트

24.01.18 TIL - [C#] 기초 (14) | 알고리즘 下 | 탐색 알고리즘 + 고급 알고리즘

C#

탐색 알고리즘 ( Search Algorithm )

구현 예제

🧫 그래프

활용예제

03. 최단 경로 알고리즘 (Shortest Path Problem)

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

코드 해석

01. 동적 프로그래밍 ( Dynamic Programming )

- 2) 동적 프로그래밍 실습 예제

02. 그리디 알고리즘 ( Greedy Algorithm )

03. 분할 정복 ( Divide and Conquer )

2) 분할 정복 실습 예제

🎞 동적 프로그래밍, 그리디 알고리즘, 분할 정복 차이

24.01.18 TIL - [C#] 기초 (14) | 알고리즘 上 | 정렬 알고리즘

24.02.02 TIL - 알고리즘 : x만큼 간격이 있는 n개의 숫자 | 자연수 뒤집어 배열로 만들기

0개의 댓글

24.01.18 TIL - [C#] 기초 (14) | 알고리즘 下 | 탐색 알고리즘 + 고급 알고리즘

C#

탐색 알고리즘 ( Search Algorithm )

구현 예제

🧫 그래프

활용예제

03. 최단 경로 알고리즘 (Shortest Path Problem)

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

코드 해석

01. 동적 프로그래밍 ( Dynamic Programming )

- 2) 동적 프로그래밍 실습 예제

02. **그리디 알고리즘 ( Greedy Algorithm )**

03. 분할 정복 ( Divide and Conquer )

2) 분할 정복 실습 예제

🎞 동적 프로그래밍, 그리디 알고리즘, 분할 정복 차이

24.01.18 TIL - [C#] 기초 (14) | 알고리즘 上 | 정렬 알고리즘

24.02.02 TIL - 알고리즘 : x만큼 간격이 있는 n개의 숫자 | 자연수 뒤집어 배열로 만들기

0개의 댓글

02. 그리디 알고리즘 ( Greedy Algorithm )