[TIL]C# 알고리즘

알고리즘

문제를 해결하기 위한 단계적인 방법

개념
알고리즘은 문제를 해결하기 위한 명확한 절차나 방법
알고리즘은 주어진 입력에 대해 정확하고 일관된 결과를 제공해야 함
프로그래밍뿐만 아니라 다양한 분야에서 사용

중요성
효율적인 알고리즘은 프로그래밍에서 매우 중요
같은 문제를 해결하는 알고리즘이 있다면 효율적인 알고리즘은 더 적은 컴퓨팅 자원(시간, 메모리 등)을 사용한다.
따라서 가능한 효율적인 알고리즘을 사용

Big O 표기법

알고리즘의 효율성을 나타내는 표기법

입력의 크기에 따라 얼마나 많은 시간이나 공간을 필요하는지 설명
알고리즘의 최악의 경우 성능을 나타내므로 효율성을 과장하지 않는다.

O(1): 상수 시간, 입력의 크기에 상관없이 항상 일정한 시간이 걸림
O(n): 선형 시간, 입력의 크기에 비례하여 시간이 걸림
O(n^2): 이차 시간, 입력의 크기의 제곱에 비례하여 시간이 걸림.
O(log n): 로그 시간, 입력의 크기의 로그에 비례하여 시간이 걸림

계산 방법
1. 상수 버리기
2. 최고 차수 항목만 남기기
3. 다항식의 경우 최고 차수 항목만 고려
4. 연산자 상수 무시

시간복잡도(Time Complexity)
알고리즘이 문제를 해결하는데 걸리는 시간을 나타내는 척도
실제 시간으로 측정하는게 아닌 입력크기에 대한 연산횟수를 측정

공간 복잡도(Space Complexity)
입력 크기에 따라 필요한 저장 공간의 약을 측정
실제 메모리 크기로 측정하는게 아님

정렬 알고리즘

주어진 데이터 세트를 특정순서로 배열하는 방법을 제공

1. 선택정렬(SelectionSort)

배열에서 최소값(or 최대값)을 찾아 맨 앞(or 맨뒤)와 교환하는 방법

시간복잡도 : 최악과 평균 모두 O(n^2)

공간복잡도 : O(1)

int[] arr = new int[] {5, 2, 4, 6, 1, 3};

for(int i=0; i< arr.Length; i++)
{
    int minInex =i; //배열의 첫번째 값을 할당

    for(int j= i+1; j <arr.Length; j++)
    {
        if(arr[j] <arr[minIndex])//배열에 첫번째 값보다 작은 값을 찾는다면 minIndex에 j할당
        {
            minIndex =j;  
        }

        //가장 작았던 값의 위치와 arr[i]랑 바꾼다.
        int temp = arr[i];
        arr[i]= arr[minIndex];
        arr[minIndex]= temp;
    }
}
foreach(int num in arr) //결과 확인용
{
    Consloe.WriteLine(num);
}

1. 배열에서 시작하는의 위치를 minIndex에 저장

2. minIndex보다 낮은 값을 발견하면 서로 자리 바꿈

3. 배열의 크기만큼 위에 순서 반복

2. 삽입정렬(Insertion Sort)

정렬되지 않은 부분에서 요소를 가져와 정렬된 부분에 적절한 위치를 삽입하는 방법

시간 복잡도: 최악의 경우 O(n^2), 정렬되어 있는 경우 O(n)

공간 복잡도: O(1)

int[] arr = new int[] {5,2,4,6,1,3};

for(int i=1; i< arr.Length; i++)
{
    int j = i-1;
    int key = arr[i];
    
    while(j>=0 && arr[j]> key)// j가 0보다 크거나 같고, arr[j]가 key보다 클 때 돌아라
    {
    	arr[j+1]= arr[j];
        j--;
    }
    
    arr[j+1]=key; 
}

1. 시작하는 숫자(j)보다 1칸뒤의 숫자를 key(arr[i])에 저장한다.

2. 맨 앞에있는 숫자보다 뒤에 있는 숫자가 작으면(or 크면)  arr[j+1]에 arr[j]값을 복사한다. (한번 돌 때 마다 j-- , j=0이 될 때 까지 반복)

3. 저장해 놨던 key 값을  arr[j+1] 에 넣는다. (배열의 맨 앞에 넣는다.)

결론: 뒤로 가면서 맨 앞보다 작은(or 큰수)를 발견하면 맨 앞에 넣고 나머지 숫자를 한칸씩 뒤로 민다

3. 퀵 정렬 (Quick Sort)

피벗을 기준으로 작은 요소들은 왼쪽, 큰 요소들은 오른쪽으로 분할하고 이를 재귀적으로 정렬하는 방법

시간 복잡도: 최악의 경우 O(n^2), 평균적으로는 O(n log n)

공간 복잡도: 평균적으로 O(log n), 최악의 경우 O(n) 

static void Swap(int[] arr, int i, int j)
{
    int temp= arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

static int Partition(int[]arr, int left,int right)
{
    int pivot = arr[right];
    int i= left -1;
    
    for(int j=left ; j<right ; j++)
    {
    	if(arr[j]< pivot)
        {
        	i++;
            Swap(arr, i, j)
        }
    }
    Swap(arr, i+1 ,right);
    return i+1;
}

static void QuickSort(int[] arr, int left, int right)
{
	int(left<right)
    {
    	int pivot =Partition(arr,left,right);
        
        QuickSort(arr,left,pivot-1);
        QucikSort(arr,pivot+1.right);
    }
}

static void Main(string[] args)
{
	int[] arr= new int[]{5,2,4,6,1,3};
    
    QucikSort(arr,0,arr.Length-1);
}

1. QucikSort에 배열, 0, 길이-1 을 전달

2. Partition에 pivot에 배열의 마지막 값 할당

3. i 부터 시작해 pivot 값보다 작으면 i와 j 자리를 바꿈

4. pivot 기준으로  왼쪽은 pivot 보다 작고 오른쪽은 pivot 보다 큰 숫자로 배열

5. pivot 다시 설정후 QuickSort 실행

 

결론: pivot 을 기존으로 왼쪽은 pivot 보다 작게 오른쪽은 pivot보다 크게 정렬, 후에 다시 pivot을 설정하고 정렬, 왼쪽 값이 오른쪽 값보다 커지면 끝? (어렵다.)

4. 병합 정렬( Merge Sort)

배열을 반으로 나누고 각 부분을 재귀적으로 정렬한 후 병합
시간 복잡도: O(n log n)

공간 복잡도: O(n)

 

탐색알고리즘(Search Algorithm)

주어진 데이터 집합에서 특정 항목을 찾는 방법을 제공

1. 선형 탐색(Linear Search)

가장 단순한 탐색 알고리즘 

배열의 각 요소를 하나씩 검사하여 원하는 항목을 찾는다.

시간 복잡도: 최악의 경우 O(n)

int SequentialSearch(int[] arr, int target)
{
    for(int i=0; i<arr.Length; i++)
    {
 	 if(arr[i]==target)//찾고자 하는 값이 맞다면
         {
             return i; //i를 return
         }
    }
    return -1; //찾지 못했다면 -1 return
}

처음부터 끝까지 하나씩 비교하여 검색

배열이 정렬되어 있지 않을 경우 사용

2. 이진 탐색(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;
}

검색하는 값을 반씩 줄여나간다.

그래프(Graph)

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

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

가중치 그래프(Weighted Graph)는 간선에 가중치 존재

그래프 탐색 방법

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

트리나 그래프를 탐색하는 알고리즘 중 하나

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

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

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

트리나 그래프를 탐색하는 알고리즘 중 하나

루트에서 시작하여 가까운 노드부터 방문, 그 다음 레벨의 노드를 방문

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

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[] visitied = new bool[V]; //방문을 했나 안했나 검사하는 용도
        DFSUtil(v,visited);
    }
    void DFSUtil(int v, bool[] visited)
    {
        visitied[v]= true; 
        Console.Write($"{v} ");
        
        foreach(int n in adj[v]) //연결된 Edge 찾기
        {
            if(!visted[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); //연결된 Edge를 큐에 넣는다
        
        while(queue.Count>0)
        {
            int n= queue.Dequeue();
            Console.Write($"{n} "};
            
            foreach(int m in adj[n])
            {
                if(!visted[m])
                {
                    visited[m]=true;
                    queue.Enqueue(m);
                }
            }
        }
    }
    
}

internal class Program
{
    static void Main(string[] args)
    {
        Graph graph = new Graph(6);
        
        graph.AddEdge(0,1); // 0번에 1, 2 저장
        graph.AddEdge(0,2);
        graph.AddEdge(1,3); // 1번에 3 저장
        graph.AddEdge(2,3); // 2번에 3, 4 저장
        graph.AddEdge(2,4);
        graph.AddEdge(3,4); // 3번에 4, 5 저장
        graph.AddEdge(3,5);
        graph.AddEdge(4,5); // 4번에 5 저장
        graph.AddEdge(1,2);
        
        //결과 확인용
        Console.WriteLine("DFS Travle: ")
        graph.DFS(0); // 0 1 3 4 5 2
        
        Console.WriteLine("BFS Travle: ")
        graph.BFS(0); //0 1 2 3 4 5
  
    }
}

 

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

1. 다익스트라 알고리즘(Dijkstra Algorithm)

하나의 시작 점에서 다른 모든 점까지 최단 경로를 찾는 알고리즘

음의 가중치를 갖는 간선이 없는경우에 사용

2. 벨만-포드 알고리즘(Bellman-Ford Algorithm)

음의 가중치를 갖는 간선에서도 사용할 수 있는 알고리즘

음수 사이클이 있는 경우에도 탐지 가능

3. A* 알고리즘(A-star Algorithm)

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

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

 

 

동적 프로그래밍 (Dunamic Programming)

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

 

그리드 알고리즘(GreedyAlgorithm)

현재에 집중하는 알고리즘

각 단계에서 가장 최적인 선택을 한다.

간단하고 직관적인 설계가 가능하며, 실행 시간이 매우 빠르다.

 

분할정복(Divided and Conquer)

큰문제를 작은 부분 문제로 분할, 문제의 크기에 따른 성능 향상

재귀적인 구조를 가지므로 설계까 단순하고 직관적