24년 8월 26일 알고리즘 4일차

탐색 알고리즘

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

가장 일반적인 탐색 알고리즘으로 선형 탐색과 이진 탐색이 있다.

 

선형 탐색

가장 단순한 탐색 알고리즘이다. 배열의 각 요소를 하나씩 차례대로 검사하여 원하는 항목을 찾는 것이다.

시간복잡도 : 최악의 경우 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;
}

중간으로 나누고 타겟을 찾고, 타겟을 못 찾을 경우에 left와 right 값을 변경을 하여서 찾는 범위를 줄여나가는 방식이다. 

 

 

 

그래프 

정점과 간선으로 이루어진 자료 구조다. 

간선이 방향을 가지고 있느냐 없느냐로 방향 그래프와 무방향 그래프로 나뉘어진다. 

경로를 이용 할 때 소모비용이 있다면 가중치 그래프라고도 할 수 있다. 

 

그래프 탐색 방법

DFS(깊이우선탐색)    시간복잡도 : 최악의 경우 O(V+E) V는 노드의 수, E는 간선의 수다.

DFS는 트리나 그래프를 탐색 하는 알고리즘 중 하나로 루트에서 시작 하여 가능한 한 깊이 들어가서 노드를 탐색 하고 더 이상 방문 할 노드가 없으면 이전 노드로 돌아가는 방식이다. 한 길을 쭉 들어갔다가 다른 걸 찾는 방식.

 

BFS(너비우선탐색)    시간복잡도 : 최악의 경우 O(V+E) 

BFS도 트리나 그래프를 탐색 하는 알고리즘 중에 하나로 루트에서 시작 하여 가까운 노드부터 방문 하고, 그 다음 레벨의 노드를 방문 하는 방식이다. 0번째가 가까운 노드를 전부 방문 하고 그 다음 1번째가 방문을 하는 방식으로 데이터를 찾는 방법이다. 

 

예제

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) // DFS를 이용한 탐색 방식.
    {
        bool[] visited = new bool[V]; //생성자 때 사용 된 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();
    }
}

 

 

최단 경로 알고리즘

다익스트라 알고리즘 

하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 음의 가중치를 갖는 간선이 없는 경우에 사용 된다. 

 

벨만 - 포드 알고리즘 

 

A* 알고리즘 

특정 목적지까지의 최단 경로를 찾는 알고리즘이다. 

휴리스틱 함수를 사용 하여 각 정점까지의 예상 비용을 계산하고 가장 낮은 예상 비용을 가진 정점을 선택하여 탐색한다. 

 

동적 프로그래밍

 

그리디 알고리즘

 

분할 정복

 

 

흠 ㅎ.. 

역시 난 문제에 강한가. 

 

공부부터 하려니 이해가 오래 걸리는 걸지도, 내일부터 바로 문제풀이부터 들어간다. 

덤벼라 백준

 

이론은 나중에 부숴주마.

 

바킹독 강의를 보면 좋다고 한다. 

 

 

내일 : 백준회원가입 하고 문제 풀어보기. 그리고 강의 보기.

문제 풀고 강의 보는 식으로 간다.

 

그래도 3달 전에는 진짜 1도 모르던 소리들이 집중해서 듣기만 하면 뭔소린지 다 알아들으니까 기분은 좋다. 근데 뭔가 마음이 진정이 안 되어서 집중이 안 됨.

 

골드는 찍을 수 있을까나..?