Greedy (p. 365)

Greedy Algorithm Recipe#

Greedy Algorithm(탐욕 알고리즘)은 매 단계에서 가장 좋아보이는 선택을 반복해 전체 최적해를 구성하는 알고리즘이다. 정당성을 증명하는 과정은 DP문제와 매우 유사하다.

아래는 그리디 알고리즘을 설계할 때 사용하는 대표적인 방법이다.

1. 문제의 답을 만드는 과정을 여러 조각으로 분해한다.#

전체 문제를 해결하기 위해 수행해야 하는 과정을 여러 개의 의사결정 단계(decision steps)로 나눈다.

ex)

스케쥴링 문제 → “어떤 작업을 다음으로 선택할 것인가?”를 단계로 바라보기
동전 거스름돈 문제 → “다음으로 어떤 동전을 사용할 것인가?”를 단계로 나누기

2. 각 단계에서 어떤 우선순위로 선택해야 하는지 기준을 세운다.#

그리디의 핵심은 바로 **선택 기준(selection rule)**이다.

이를 찾기 위해 보통 다음과 같은 과정을 거친다.

예제 입력을 직접 손으로 풀어보기
다양한 작은 입력을 임의로 만들어보며 패턴 찾기
“항상 이걸 먼저 선택하면 좋더라” 같은 직관 생성하기

이 선택 기준이 항상 최적해를 향하도록 작동해야 한다.

3. 선택 기준이 맞는지 두 가지 속성으로 증명한다.#

그리디 알고리즘이 올바르게 동작한다는 것을 보이려면 다음 두 성질을 만족해야 한다.

탐욕적 선택 속성 (Greedy-choice Property)

각 단계에서 그리디가 선택한 결정이, 전체 최적해에도 포함될 수 있음을 보이는 것.

즉, 현재 단계에서 최선이라고 판단한 선택이 실제로 어떤 최적해에도 모순되지 않도록 정당화해야 한다.

증명 방법은 대체로 다음 패턴을 따른다.
1. 그리디 선택과 다른 선택을 하는 최적해가 존재한다고 가정한다.
2. 그 최적해를 “조작(swap argument)”해서 그리디 선택을 포함하는 새로운 최적해로 바꿀 수 있음을 보인다.
3. 따라서 “항상 그리디 선택을 포함하는 최적해가 존재한다”는 결론에 도달한다.
→ 이걸 보이면 “지금의 최선이 전체에서도 최선이다”임을 증명하게 된다.
최적 부분 구조 (Optimal Substructure)

그리디 선택을 하고 남은 문제도 원래 문제와 동일한 구조를 가져야 하며, 이 부분 문제에 또다시 그리디한 선택을 반복해도 전체 최적해를 만들 수 있음을 보이는 성질이다.

다른 말로 표현하면,

전체 최적해 = 현재 단계의 최적 선택 + 남은 부분 문제의 최적해
즉, 어떤 순간의 선택이 전체 구조를 망가뜨리지 않아야 하고, 남은 부분도 “같은 방식으로 풀 수 있는 문제”여야 한다.

이를 보이는 일반적인 방법은 다음과 같다.
1. N번째 단계에서 그리디 선택이 최적이라고 가정한다.
2. 그 선택 이후에 남는 문제가 원래 문제와 (구조가) 동일한지 확인한다.
→ 이걸 보이면, 남은 문제의 최적해와 그리디 선택을 합쳤을 때, 전체 최적해가 성립함을 증명하게 된다.

만약 이 성질이 꺠지면 그리디는 DP로 대체해야 한다.

📌 결론#

그리디 알고리즘은 다음 두 가지 성질을 증명할 수 있을 때만 유효하다.

탐욕적 선택 속성

→ 각 단계에서 고른 선택이 전체 최적해에 포함될 수 있어야 한다.
최적 부분 구조

→ 그 선택 이후의 나머지 문제도 동일한 구조를 갖고, 계속 최적 선택을 반복하면 전체 최적해가 완성되어야 한다.

이 두 조건이 함께 성립해야만 “단계별로 최선만 고르는 단순한 방법”이 전체적으로도 최적이 된다.

그렇지 않다면 대부분의 경우 DP를 사용해야 한다.