C# #24 동적 프로그래밍, 그리디 알고리즘, 분할 정복, 코딩 테스트 문제의 종류

동적 프로그래밍(Dynamic Programming, DP)

• 어떤 문제를 더 작은 하위 문제들로 나누어 해결하고 그 결과를 저장하여 중복 계산을 피하면서 효율적으로 문제를 해결하는 알고리즘 설계 기법.
• 탑다운 방식: 큰 문제를 해결하기 위해 작은 하위 문제들을 재귀적으로 푸는 방식. 중복 계산을 피하기 위해 계산한 결과를 메모이제이션(저장)하고 이미 계산한 값이 필요할 때마다 참조하여 재사용.
• 바텀업 방식: 더 작은 하위 문제부터 시작하여 문제의 크기를 점점 키워가며 해결하는 방식. 보통 반복문을 사용하여 작은 문제부터 큰 문제까지 순차적으로 해결하며 중복 계산을 피함.
• 동적 프로그래밍은 최적 부분 구조와 중복 부분 문제의 특징을 가진 문제들을 효과적으로 해결할 수 있음.

// 문제: 피보나치 수열의 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];
}
//바텀업 방식, DP 테이블 사용

 

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

 

코딩 테스트나 알고리즘 문제의 종류

• 탐색과 정렬: 배열, 리스트, 문자열 등의 데이터에서 특정 값을 찾거나 정렬하는 문제입니다. 선형 탐색, 이진 탐색, 퀵 정렬, 병합 정렬 등의 알고리즘이 주로 활용됩니다.
• 그래프: 그래프 구조를 활용하여 문제를 해결하는 문제입니다. 최단 경로, 신장 트리, 네트워크 연결 등의 문제가 있을 수 있으며, 대표적인 알고리즘으로는 DFS(Depth-First Search), BFS(Breadth-First Search), Dijkstra, 크루스칼, 프림 등이 있습니다.
• 동적 프로그래밍: 큰 문제를 작은 하위 문제로 분할하여 해결하는 동적 프로그래밍 알고리즘을 활용하는 문제입니다. 피보나치 수열, 최장 공통 부분 수열, 0-1 배낭 문제 등이 있습니다.
• 그리디 알고리즘: 각 단계에서 가장 최적인 선택을 하는 알고리즘으로, 지역적 최적해를 찾는 문제입니다. 거스름돈 문제, 회의실 배정, 작업 스케줄링 등이 있습니다.
• 분할 정복: 문제를 작은 부분으로 분할하여 해결하는 분할 정복 알고리즘을 사용하는 문제입니다. 퀵 정렬, 병합 정렬, 이진 탐색 등이 있습니다.
• 동적 그래프: 그래프 구조에서 동적인 변화를 다루는 문제입니다. 플로이드-와샬 알고리즘, 벨만-포드 알고리즘 등이 있습니다.
• 문자열 처리: 문자열에 대한 다양한 처리를 다루는 문제입니다. 문자열 압축, 회문 판별, 문자열 매칭 등이 있을 수 있습니다.
• 기타: 그 외에도 수학적인 문제, 비트 연산 문제, 시뮬레이션 문제, 동적 계획법과 그래프의 결합 문제 등 다양한 유형의 문제가 출제될 수 있습니다.