C# 종합 문법 5 - 3 : 고급 알고리즘

김정환·2024년 9월 25일

동적 프로그래밍 Dynamic Programming

큰 문제를 작은 문제 단위로 해소해 나가는 것

작은 하위 문제의 해결 방법을 계산하여 작성하고 이를 이용해 큰 문제의 해결 방법을 도출.
이러한 저장 과정 = 메모이제이션 Memoization
중복되는 하위 문제들을 효율적으로 해결하기 위해 사용.
일반적으로 재귀적 구조를 가지며, 하향식 or 상향식 두 가지 방법으로 구현
최적 부분 구조, 중복 부분 문제의 특징을 가진 문제들을 효과적으로 풀 수 있다.
- 최적 부분 구조 :
  큰 문제를 풀기 위해 작은 문제로 나눠 해결한 방법이 큰 문제 해결로 이어진 것.
- 중복 부분 문제 :
  결국 동일한 규칙 상황에서 반복하다보면 해결되는 것

예시

// 문제: 피보나치 수열의 n번째 항을 구하는 함수를 작성하세요.
// 재귀가 아닌 반복을 이용 : O(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];
}

어떤 문제가 기초 데이터를 바탕으로 반복만 하면 풀리는 경우

그리디 알고리즘 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++;
        }
    }

    if(amount > 0) return -1; 

    return count;
}

중간 tip

큰 문제를 파악할 때, 먼저 문제를 분석하고 작은 문제로 나누는 것이 중요.
작은 문제로 나누고 나서 어떻게 규칙성을 만들지 생각할 것.

분할 정복 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);  // 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;
}