알고리즘

---

알고리즘

문제를 해결하기 위한 단계적 절차.

입력 > 명확한 단계 > 출력 구조를 가지며 어떤 입력이 주어져도 정확하고 예측 가능한 결과를 도출해야 한다.

---

Big O 표기법

Big O는 알고리즘의 성능(시간/공간)을 측정하는 표현 방식이다.

입력 크기(n)가 증가할 때 연산 횟수나 메모리 사용량이 어떻게 변하는 지를 설명한다.

특히 최악의 경우를 기준으로 표현한다.

• O(1): 상수 - 입력 크기와 무관
• O(n): 선형 - 입력 크기에 비례
• O(n^2): 이차 - 이중 반복문
• O(2^n): 지수 - 이진 탐색
• O(log n): 로그 - 피보나치 재귀 등

복잡도 계산 원칙

상수제거: O(2n) -> O(n)

최고 차수 유지: O(n^2 + n) -> O(n^2)

중첩 반복문은 곱으로 해석: for{for} -> O(n^2)

 

 

---

시간 복잡도

시간 복잡도는 알고리즘이 실행되는 연산 횟수의 증가율을 측정한다.

실제 소요 시간이 아닌 입력 크기 기준으로 계산하며, Big O로 표현한다.

int Sum(int n) {
    int sum = 0;
    for (int i = 0; i <= n; i++) {
        sum += i;
    }
    return sum;
} // → O(n)

int Fibonacci(int n) {
    if (n <= 1) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
} // → O(2^n)

공간 복잡도

공간 복잡도는 알고리즘 실행 중 필요한 추가 메모리 양을 의미한다.

배열, 변수, 재귀 호출 스택 등을 포함하며, 입력 크기 기준으로 Big O로 표현한다.

int FindMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.Length; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}
// 시간 복잡도: O(n), 공간 복잡도: O(1)

int FindMax2(int[] arr) {
    for (int i = 0; i < arr.Length; i++) {
        bool isMax = true;
        for (int j = 0; j < arr.Length; j++) {
            if (arr[j] > arr[i]) {
                isMax = false;
                break;
            }
        }
        if (isMax) return arr[i];
    }
    return -1;
}
// 시간 복잡도: O(n^2), 공간 복잡도: O(1)

필요 시 시간/공간 복잡도를 고려해 알고리즘을 선택해야 하며, 현실적 제약 하에서 가장 효율적인 방법을 찾는 것이 중요하다.

---

정렬 알고리즘

선택 정렬 (Selection Sort)

매번 가장 작은 값을 찾아 현재 위치와 바꾸는 방식.

• 시간 복잡도: O(n^2)
• 공간 복잡도: O(1)

for (int i = 0; i < arr.Length - 1; i++) {
    int min = i;
    for (int j = i + 1; j < arr.Length; j++)
        if (arr[j] < arr[min]) min = j;
    (arr[i], arr[min]) = (arr[min], arr[i]);
}

삽입 정렬 (Insertion Sort)

정렬되지 않은 값을 왼쪽 정렬된 부분에 적절한 위치로 삽입하는 방식.

• 시간 복잡도: 최악 O(n^2), 정렬된 경우 O(n) 
• 공간 복잡도: O(1) 

for (int i = 1; i < arr.Length; i++) {
    int key = arr[i], j = i - 1;
    while (j >= 0 && arr[j] > key) arr[j + 1] = arr[j--];
    arr[j + 1] = key;
}

퀵 정렬 (Quick Sort)

기준값(피벗)을 정해 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할 후 재귀 정렬하는 방식.

• 시간 복잡도: 최악 O(n^2), 평균적으로 O(n log n)
• 공간 복잡도: 평균적으로 O(log n) 최악의 경우 O(n) - 재귀 호출에 필요한 스택 공간

void QuickSort(int[] arr, int l, int r) {
    if (l >= r) return;
    int pivot = arr[r], i = l - 1;
    for (int j = l; j < r; j++)
        if (arr[j] < pivot) (arr[++i], arr[j]) = (arr[j], arr[i]);
    (arr[i + 1], arr[r]) = (arr[r], arr[i + 1]);
    QuickSort(arr, l, i); QuickSort(arr, i + 2, r);
}

병합 정렬 (Merge Sort)

배열을 반씩 나눈 후 정렬된 상태로 병합하는 방식

• 시간 복잡도: 모든 경우에 대해 O(n log n)
• 공간 복잡도: O(n) - 정렬을 위한 임시 배열이 필요

void MergeSort(int[] arr, int l, int r) {
    if (l >= r) return;
    int m = (l + r) / 2;
    MergeSort(arr, l, m); MergeSort(arr, m + 1, r);
    // 병합 과정 생략
}

C# 내장 정렬

Array.Sort(arr);  // 배열 정렬
list.Sort();      // 리스트 정렬

---

탐색 알고리즘

선형 탐색 (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;
}

이진 탐색 (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)와 무방향 그래프(Undirected Graph)
  • 가중치 그래프(Weighted Graph)는 간선에 가중치가 있다.

그래프 탐색은 깊이 우선 탐색(Depth-First Search, DFS)과 너비 우선 탐색(Breadth-First Search, BFS)이 대표적이다.

DFS는 가능한 깊이까지 탐색하고 이전 노드로 돌아가는 방식이다.

BFS는 루트에서 시작하여 가까운 노드부터 방문한 뒤에 다음 레벨의 노드를 방문하는 방식이다.

• 시간 복잡도: O(V + E)
  • V: 노드수
  • E: 간선수

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

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

• 다익스트라 알고리즘 (Dijkstra Algorithm)
  • 하나의 정점에서 다른 정점까지의 최단 경로를 찾는다.
  • 음수 가중치가 없는 경우에만 사용 가능하다.
  • 시간 복잡도: O(V^2) 또는 O(E log V)

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

    for (int i = 0; i < V; i++)
        Console.WriteLine($"{i}\t{distance[i]}");
}

 

• 벨만-포드 알고리즘 (Bellman-Ford Algorithm)
  • 모든 간선에 대해 여러 번 완화(Relaxation) 작업을 반복하여 최단 경로를 구한다.
  • 음수 가중치 간선이 있어도 사용할 수 있으며, 음수 사이클 존재 여부도 탐지 가능하다.
  • 다익스트라보다 느리지만, 더 다양한 그래프에 적용 가능하다.
  • 시간 복잡도: O(VE)

for (int i = 0; i < V - 1; i++)
{
    foreach (var edge in edges)
    {
        int u = edge.from;
        int v = edge.to;
        int weight = edge.weight;

        if (distance[u] != int.MaxValue && distance[u] + weight < distance[v])
        {
            distance[v] = distance[u] + weight;
        }
    }
}

• A* 알고리즘 (A-Star Algorithm)
  • A* 알고리즘은 시작점에서 목표점까지의 최적 경로를 찾기 위해 실제 거리와 휴리스틱 거리의 합을 기준으로 탐색한다.
  • 우선순위 큐(Priority Queue)를 사용하며, 휴리스틱 함수는 일반적으로 유클리드 거리나 맨해튼 거리 등을 사용한다.
  • 경로의 효율성과 정확성을 동시에 추구하며, 게임 개발 등에서 널리 사용된다.
  • 시간 복잡도: 휴리스틱에 따라 다르지만 일반적으로 매우 효율적이다.

f(n) = g(n) + h(n);
// g(n): 시작점에서 현재 노드까지의 실제 비용
// h(n): 현재 노드에서 목표 지점까지의 예상 비용 (휴리스틱)

---

고급 알고리즘

동적 프로그래밍 (Dynamic Programming)

동적 프로그래밍은 큰 문제를 작은 하위 문제로 나누고, 각 결과를 저장해 중복 계산을 피하는 방식이다.

메모이제이션(Memoization) 또는 테이블을 사용하는 바텀업 방식으로 구현할 수 있다.

중복되는 하위 문제가 많고 최적 부분 구조를 가지는 문제에 효과적이다.

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

그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘은 매 단계에서 가장 좋아 보이는 선택을 하는 방식이다.

항상 전역 최적해를 보장하지는 않지만, 일부 문제에선 효과적이고 빠르다.

단순하고 구현이 쉬우며, 정렬된 조건에서 주로 쓰인다.

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++;
        }
    }
    return amount > 0 ? -1 : count;
}

분할 정복 (Divide and Conquer)

문제를 작게 나누고, 각각을 해결한 뒤 병합하여 원래 문제를 해결한다.

재귀 호출로 구현되며, 독립적인 하위 문제는 병렬화에도 적합하다.

퀵 정렬이나 병합 정렬 등에서 사용된다.

public void QuickSort(int[] arr, int low, int high)
{
    if(low < high)
    {
        int pi = Partition(arr, low, high);
        QuickSort(arr, low, pi - 1);
        QuickSort(arr, pi + 1, high);
    }
}

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

---

문제 해결 전략

문제 해결의 시작은 문제의 정확한 이해에서 출발하며, 입력과 출력 조건을 꼼꼼히 분석해야 한다.

알고리즘을 설계한 후에는 효율성과 구현 가능성을 고려해 코드를 작성해야 한다.

디버깅과 테스트, 시간 관리, 반복 연습을 통해 문제 해결 능력을 체계적으로 향상 시킬 수 있다.

 

실전 연습을 위한 플랫폼: 백준, 프로그래머스, LeetCode, 바킹독 블로그 등

다양한 난이도와 유형의 문제에 접근함으로서 실전 감각을 기를 수 있다.

타인의 풀이를 분석하고 적용하는 과정 또한 매우 중요.