Dynamic Programming과 Greedy

본 블로그 작성 글들은, 강의를 목표로 하고 제작되었습니다. 또한 작성된 글의 정보도 틀렸을 수 있으니, 주의해주세요.

Dynamic Programming과 Greedy는 큰 문제를 작은 선택으로 나누지만, 선택을 다루는 방식이 다르다.

Dynamic Programming

같은 작은 문제가 반복되고, 작은 문제의 최적해로 큰 문제의 최적해를 만들 수 있을 때 사용한다.

int Fibonacci(int N)
{
    if (N <= 1)
    {
        return N;
    }

    std::vector<int> DP(N + 1, 0);
    DP[1] = 1;

    for (int i = 2; i <= N; ++i)
    {
        DP[i] = DP[i - 1] + DP[i - 2];
    }

    return DP[N];
}

계산한 결과를 저장하므로 같은 재귀 문제를 반복하지 않는다. 상태 정의와 점화식을 제대로 세우는 것이 핵심이다.

Greedy

현재 순간에 가장 좋아 보이는 선택을 하고 이전 선택을 되돌리지 않는다.

활동 선택 문제처럼 종료 시간이 가장 빠른 작업을 계속 고르면 최적해가 되는 문제가 있다. 하지만 동전 단위가 임의로 주어진 거스름돈 문제에서는 가장 큰 동전부터 고르는 방식이 최적이 아닐 수 있다.

동전: 1, 3, 4
금액: 6

Greedy: 4 + 1 + 1 = 3개
최적해: 3 + 3 = 2개

Greedy는 빠르고 메모리를 적게 쓰지만, 지역 최적 선택이 전체 최적해로 이어진다는 증명이 필요하다. 예제 몇 개가 맞았다는 것만으로 Greedy를 선택하면 반례에서 실패한다.