C# 문법 5주차 - 고급 알고리즘

🖥️ 동적 프로그래밍(Dynamic Programming)

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

🤔 동적 프로그래밍?

• 동적 프로그래밍은 큰 문제를 작은 하위 문제로 분할하여 푸는 접근 방식
• 작은 하위 문제의 해결 방법을 계산하여 저장하고, 이를 이용하여 큰 문제의 해결 방법을 도출한다. → "메모이제이션(Memoization)"
• 중복되는 하위 문제들을 효율적으로 해결할 수 있다.
• 일반적으로 재귀적인 구조를 가지며, 하향식과 상향식 두 가지 방법으로 구현할 수 있다.
• 최적 부분 구조와 중복 부분 문제의 특징을 가진 문제들을 효과적으로 해결할 수 있다.

동적 프로그래밍 예제 - 피보나치 수열)

// 문제: 피보나치 수열의 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];
}

시간 복잡도 : O(n), 공간 복잡도 : O(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;
}

🫡 분할 정복(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;
}