알고리즘

알고리즘이란?

알고리즘이란 문제를 해결하기 위한 과정을 논리적 절차에 따라 구성한 일련의 단계이며, 입력값에 따른 결과가 도출됩니다

알고리즘 설계 과정

문제 이해
- 문제의 요구사항 분석, 입력과 출력의 형식 파악
예시와 테스트 케이스 작성
- 몇가지 예시를 만들어 무엇을 넣었을 때 어떤 결과가 나오는지 파악해야합니다
- 문제가 주어지면 그 예상 결과로 어떤게 나올 것이다 라는 것을 테스트 케이스로 작성
알고리즘 설계
- 정확도,효율성,Big-O값을 생각하며 의사코드를 1차로 만들어 봅니다
- 이후 이를 토대로 설게를 합니다
알고리즘 구현 및 검증
- 설계에서 만든 의사코드나 흐름도에 따라 코드를 작성합니다 제작 후에는 테스트 케이스를 통해 검증을 거칩니다
알고리즘 분석과 개선
- 작동이 정상적이면 성능 분석을 통해 최적화, 개선을 합니다

설계에서 가장 중요한건 정확도입니다 이를 위해 검증할 방법도 우선적으로 고려해야합니다

빅오 (Big-O)

빅오란 알고리즘의 성능을 수학적으로 나타내는 방법
입력크기가 N이라 할때 알고리즘의 실행속도(시간복잡도) 또는 메모리공간(공간복잡도) 이 얼마나 빠르게 증가하는지 나타내는 것
정확한 실행속도를 나타내는 것이 아닌 성능의 최고 차항만 남겨 단순화하여 표현한 것 (촤악의 경우)

주요 Big-O 유형 및 효율성 순서

표기법	명칭	설명	C#에서의 예시
O(1)	상수 시간 (Constant)	입력 크기(n)에 관계없이 항상 일정한 시간이 소요됩니다. 가장 이상적인 성능입니다.	배열의 첫 번째 요소에 접근: array[0]
O(logn)	로그 시간 (Logarithmic)	입력 크기가 커져도 실행 시간이 아주 조금씩 증가합니다. 데이터를 절반씩 줄여나가며 탐색하는 경우입니다.	이진 탐색(Binary Search)
O(n)	선형 시간 (Linear)	입력 크기에 정확히 비례하여 실행 시간이 증가합니다. (데이터가 2배 늘면 시간도 2배 늘어납니다.)	배열의 모든 요소를 순회하는 for 또는 foreach 루프
O(nlogn)	선형 로그 시간	$\mathbf{O(n)}$보다는 느리지만, 효율적인 정렬 알고리즘에서 흔히 볼 수 있습니다.	병합 정렬(Merge Sort), 힙 정렬(Heap Sort)
O(n2)	이차 시간 (Quadratic)	입력 크기의 제곱에 비례하여 실행 시간이 증가합니다. 중첩된 루프(Nested Loop)를 사용하는 경우입니다.	버블 정렬(Bubble Sort), 이중 for 문

🎯 왜 Big-O를 사용해야 할까요?

컴퓨터 환경 독립성: 실제 실행 시간(초)은 컴퓨터의 CPU, 메모리, 언어 등에 따라 달라집니다. Big-O는 연산 횟수를 기준으로 하므로 환경에 관계없이 알고리즘의 본질적인 효율성을 비교할 수 있습니다.
확장성 예측: 입력 데이터($n$)가 매우 커질 때(Scale-up), 알고리즘의 성능이 어떻게 변할지 예측하여 비효율적인 알고리즘을 피할 수 있습니다.

유명한 실전 알고리즘 들

정렬 알고리즘

주어진 데이터 집합 (배열, 콜렉션)등을 오름차순 또는 내림차순처럼 일정한 순서로 재배치 하는것
시간복잡도(Big-O)로 알고리즘의 효율을 측정함

A. 기본 정렬 알고리즘 - 데이터의 양이 적을 때 사용되며, 구현이 비교적 쉽지만 데이터가 많아질수록 성능이 급격히 떨어집니다

버블 정렬 ( Bubble Sort)

인접한 두 원소를 비교하여 순서가 잘못 되었다면 서로 교환하는 과정을 반복하여 정렬을 수행
Big-O : O(N^2)

public static void BubbleSort(int[] arr) 
{ 
	int n = arr.Length; 
	for (int i = 0; i < n - 1; i++) 
    { 
        for (int j = 0; j < n - i - 1; j++) 
        { 
        	if (arr[j] > arr[j + 1]) 
            { 
            	int temp = arr[j]; 
                arr[j] = arr[j + 1]; 
                arr[j + 1] = temp; 
            } 
         } 
     } 
}

선택 정렬 ( Selection Sort )

주어진 리스트에서 최소값을 선택하여 정렬되지 않은 부분과 정렬된 부분을 나누고 정렬되지 않은 부분에서 최소값을 선택하여 정렬된 부분에 추가하는 과정을 반복
Big-O : O(N^2)

public static void SelectionSort(int[] arr)
{
    int n = arr.Length;

    for (int i = 0; i < n - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }

        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

삽입 정렬 ( Insertion Sort )

리스트를 정렬된 부분과 정렬되지 않은 부분으로 나눈 후 정렬되지 않은 부분의 원소를 정렬된 부분의 적절한 위치에 삽입하는 과정을 반복하여 정렬을 수행
Big-O : O(N^2)

public static void InsertionSort(int[] arr)
{
    int n = arr.Length;

    for (int i = 1; i < n; i++)
    {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

B. 고급 / 분할 정복 정렬 알고리즘 - 대규모 데이터를 정렬할 때 주로 사용되며, 효율적인 시간 복잡도를 가집니다

퀵 정렬 ( Quick Sort )

분할 정복 기법을 사용하는 정렬 알고리즘으로 , 리스트를 기준값을 중심으로 반할한 후 재귀적으로 정렬합니다
Big-O : 평균적으로 O( N Log N ), 최악의 경우 O( N^2 )

public static void QuickSort(int[] arr, int low, int high) 
{
	if (low < high) 
    { 
    	int pivotIndex = Partition(arr, low, high); 
        QuickSort(arr, low, pivotIndex - 1); 
        QuickSort(arr, pivotIndex + 1, high); 
    } 
} 
private static int Partition(int[] arr, int low, int high) 
{ 
	int pivot = arr[high]; 
    int i = low - 1; 
    for (int j = low; j < high; j++) 
    { 
    	if (arr[j] < pivot) 
        { 
        	i++; 
            int temp = arr[i]; 
            arr[i] = arr[j]; 
            arr[j] = temp; 
        } 
     } 
     int temp2 = arr[i + 1]; 
     arr[i + 1] = arr[high]; 
     arr[high] = temp2; 
     return i + 1; 
 }

병합 정렬 ( Merge Sort )

분할 정복 기법을 사용하는 정렬 알고리즘으로, 리스트를 반으로 나눈 후 재귀적으로 정렬한 다음, 정렬된 부분 리스트를 병합하여 최정적으로 정렬을 수행
Big-O : O( N Log N )

public static void MergeSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;

        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);

        Merge(arr, left, mid, right);
    }
}

private static void Merge(int[] arr, int left, int mid, int right)
{
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int[] leftArr = new int[n1];
    int[] rightArr = new int[n2];

    Array.Copy(arr, left, leftArr, 0, n1);
    Array.Copy(arr, mid + 1, rightArr, 0, n2);

    int i = 0, j = 0;
    int k = left;

    while (i < n1 && j < n2)
    {
        if (leftArr[i] <= rightArr[j])
        {
            arr[k] = leftArr[i];
            i++;
        }
        else
        {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    while (i < n1)
    {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    while (j < n2)
    {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

힙 정렬 ( Heap Sort )

힙 자료구조를 이용하여 정렬을 수행하는 알고리즘, 주어진 리스트를 최대 힙 또는 최소 힙으로 구성한 후 힙에서 원소를 하나씩 꺼내 정렬된 순서로 배열
Big-O : O( N Log N )

public static void HeapSort(int[] arr)
{
    int n = arr.Length;

    for (int i = n / 2 - 1; i >= 0; i--)
        Heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--)
    {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        Heapify(arr, i, 0);
    }
}

private static void Heapify(int[] arr, int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i)
    {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        Heapify(arr, n, largest);
    }
}

탐색 알고리즘

자료구조(배열, 그래프, 트리 등) 내에서 원하는 원소나 특정 조건에 맞는 경로를 찾는 절차를 의미
탐색은 크게 선형 탐색과 비선형 탐색으로 나눌 수 있습니다.

1. 🥇 선형 자료구조 탐색 (배열/리스트)

정렬되지 않은 데이터나 선형적인 구조에서 특정 원소를 찾는 방법입니다.

A. 순차 탐색 (Sequential/Linear Search)

원리: 리스트의 첫 번째 원소부터 마지막 원소까지 순서대로 비교하면서 원하는 원소를 찾습니다.
특징: 데이터가 정렬되어 있는지 여부와 관계없이 사용할 수 있습니다.
시간 복잡도: O(N) (최악/평균).

B. 이진 탐색 (Binary Search)

원리: 반드시 정렬된 리스트의 중앙 원소와 찾고자 하는 값을 비교하여, 탐색 범위를 절반씩 줄여나가는 방식입니다.
특징: 순차 탐색보다 훨씬 빠르지만, 데이터가 정렬되어 있어야 합니다.
시간 복잡도: O(\log N) (최악/평균).

2. 🌲 비선형 자료구조 탐색 (그래프/트리)

그래프나 트리와 같은 복잡한 연결 구조에서 모든 노드를 방문하거나 특정 경로를 찾는 방법입니다.

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

원리: 한 정점에서 시작하여 연결된 정점을 따라 최대한 깊숙이 내려가며 탐색합니다. 더 이상 갈 곳이 없으면 되돌아 나와(백트래킹) 다른 경로를 탐색합니다.
사용 자료구조: 스택(Stack) 또는 재귀 호출.
주요 활용: 경로 존재 유무 확인, 사이클 찾기, 위상 정렬 등.

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

원리: 한 정점에서 시작하여 인접한 **모든 정점(같은 레벨)**들을 먼저 방문한 후, 그다음 레벨의 정점들로 넓게 탐색을 확장해 나갑니다.
사용 자료구조: 큐(Queue).
주요 활용: 최단 경로 찾기(간선의 가중치가 동일할 때), 두 노드 간의 거리 계산, 연결 요소 찾기 등.

3. 🎯 기타 고급 탐색 알고리즘

특정 조건 하에서 최적의 해답을 찾는 데 사용되는 알고리즘입니다.

다익스트라 알고리즘 (Dijkstra's Algorithm): 가중치가 있는 그래프에서 특정 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. (음수 가중치 불가)
출발지에서 모든 노드까지 최단경로 찾기, 모든 경우의 수를 다 계산해보고 최적을 찾음

A* 알고리즘 (A-star Algorithm): 다익스트라와 유사하게 최단 경로를 찾지만, 휴리스틱(Heuristic) 정보를 활용하여 목적지에 더 빨리 도달할 가능성이 높은 경로를 우선 탐색하는 효율적인 알고리즘입니다. (게임, 로봇 경로 탐색에 사용)
미리 예측을 해보고 고름, 다익스트라처럼 정확한게 아니라 약간 반반임, 목표지점까지 제일 빨리가기위해 현재까지의 비용 + 다음으로 갈 수 있는 경로 중 가장 빠른 경로를 판단하길 반복
A 알고리즘은 그래프에서 최단 경로를 찾는 데 사용되는 휴리스틱(Heuristic) 기반 탐색 알고리즘입니다.A 알고리즘은 현재 위치에서 목적지까지의 예상 거리를 휴리스틱 함수로 계산하고, 이를 기반으로 다음으로 이동할 노드를 선택합니다. 예상 거리를 작은 순서대로 선택하면서 목적지에 도달할 때까지 진행합니다. A* 알고리즘은 다익스트라 알고리즘의 확장이며, 최적의 해를 찾는 동시에 효율적인 탐색을 수행합니다

기타 심화 알고리즘

개념	주요 목적	핵심 자료구조 및 특징	주요 시간 복잡도
이진 탐색 트리 (BST)	데이터의 효율적인 탐색, 삽입, 삭제	* 모든 노드의 왼쪽 자식은 노드 값보다 작고, 오른쪽 자식은 노드 값보다 큽니다. * 정렬된 데이터를 유지하여 빠른 검색을 가능하게 합니다. * 균형이 무너지면 성능이 $O(n)$으로 저하될 수 있어 AVL 트리나 Red-Black 트리로 보완합니다.	탐색, 삽입, 삭제 (평균): O(logn) 탐색, 삽입, 삭제 (최악): O(n)
우선순위 큐 (Priority Queue)	가장 높은(또는 낮은) 우선순위를 가진 데이터를 먼저 처리	* 일반적인 큐(Queue)와 달리, 들어온 순서가 아닌 우선순위에 따라 데이터를 꺼냅니다. * 보통 힙(Heap) 자료구조(최대 힙 또는 최소 힙)를 사용하여 구현됩니다.	삽입: O(logn) 최우선 항목 제거: O(logn) 최우선 항목 확인: O(1)
최소 신장 트리 (MST)	주어진 그래프의 모든 노드를 연결하는 가중치 합이 최소인 부분 그래프(트리) 찾기	* 가중치가 있는 연결된 그래프에서 사용되는 알고리즘 개념입니다. * 사이클 없이 모든 노드를 연결하며 간선 가중치의 합이 최소가 되도록 합니다. * 주로 프림(Prim) 또는 크루스칼(Kruskal) 알고리즘으로 구현됩니다.	프림 알고리즘: O(ElogV) 또는 O(V2) 크루스칼 알고리즘: O(ElogE) 또는 O(ElogV)

BST: 데이터가 정렬된 상태를 유지해야 하는 상황(예: 데이터베이스 인덱스)에서 매우 유용합니다.
우선순위 큐: Dijkstra 알고리즘, A* 알고리즘 등 최단 경로 탐색이나 운영체제에서의 작업 스케줄링 등에 핵심적으로 사용됩니다.
MST: 통신 네트워크, 도로망 설계 등 모든 지점을 최소 비용으로 연결해야 하는 문제에 적용됩니다

'C# > 알고리즘과 디자인 패턴' 카테고리의 다른 글

디자인 패턴 (0)	2025.11.15