[Algorithm] 그리디, 탐욕 (Greedy)

1. 개요

그리디 (Greedy), 탐욕 알고리즘 (이하 그리디) 은 어떠한 것을 선택할 상황이 발생하면 항상 그 시점의 최선의 선택을 해나가는 방식을 의미한다.
근사적인 최적해 (이하 근사해) 를 구할 수 있다는 특징이 있다. 근사해가 최적해 만큼 의미있게 취급될 경우 주로 사용한다.

* 근사해라고 표현되는 이유는 그리디가 항상 최적해를 구할 수 있는 것은 아니기 때문이다. 따라서 최적해를 구하기 위한 근사적인 방법 이라는 것만 이해하면 충분하다.

그리디를 적용하기 전, 다음의 경우를 만족하는가를 파악할 필요가 있다.

현재 선택이 미래의 선택에 독립적인가?
하위 문제를 통해 전체 문제를 해결할 수 있는가?

2. 의의

그리디는 DP를 사용하는 경우 중, 특정 경우에 대해 속도를 향상 시키기 위해 사용한다.

2.1. DP와의 비교

	DP	그리디
장점	최적해를 보장함	빠름
단점	경우에 따라 느림	최적해를 보장하지 못함

3. 조건

그리디의 조건

1. Greedy Choice Property (탐욕적 선택 조건)
2. Optimal Substructure (최적 하위 구조)

3.1. Greedy Choice Property (탐욕적 선택 조건)

그리디는 현재의 선택이 미래의 선택에 영향을 미치지 않아야 한다.

3.2. Optimal Substructure (최적 하위 구조)

그리디는 하위 문제의 최적의 해 (Optimal Solution) 를 통해 전체 문제의 최적의 해를 구할 수 있어야 한다.

3.3. 예시) 최적 경로 구하기

구역 $A$, $B$, $C$ 에 대해 $A$ 구역에서 $C$ 구역으로 가는 모든 경로 중 가장 최적의 경로를 찾아보자.

* 경로가 최적이다는 것은 "가장 적은 시간이 걸림"이나, "가장 거리가 짧음" 등 설정하기 나름이다.

먼저, $A$ 구역에서 $B$ 구역으로 가는 경로를 선택하는 것은 $B$ 구역에서 $C$ 구역으로 가는 경로의 선택에 어떠한 영향도 주지 않는다. 이것이 바로 탐욕적 선택 조건(Greedy Selection Property) 이다.

$A$ 구역에서 $C$ 구역으로 바로(Directly)가는 경로가 없고 항상 $B$ 구역을 경유해야 한다고 가정할 때,

$A$ 구역에서 $C$ 구역으로 가는 최적의 경로를 찾는 문제는 다음의 두 하위 문제로 나뉠 수 있다.

1. $A$ 구역에서 $B$ 구역으로 가는 최적의 경로를 찾는 문제
2. $B$ 구역에서 $C$ 구역으로 가는 최적의 경로를 찾는 문제

위 하위 문제 1, 2 에서 각각 구한 최적의 경로를 통해 $A$ 구역에서 $C$ 구역으로 가는 최적의 경로를 찾을 수 있다. 이것이 최적 하위 구조(Optimal Substructures) 이다.

가령, 서울 에서 대전 을 거쳐 부산 을 간다고 할 때, 서울 에서 대전 으로 가는 최적 경로와 대전 에서 부산 으로 가는 최적 경로를 선택해야 비로소 서울 에서 부산 으로 가는 최적 경로를 이용할 수 있다.

3.4. 최적해가 보장되지 않는 경우

예시) 동전 조합

10원, 50원, 100원, 500원짜리 동전이 각각 무한히 있다고 가정하자.

위 네 종류의 동전으로 870원을 가장 적은 수의 동전의 조합으로 나타내야 한다면, 그리디의 사용을 고려할 수 있다.

절차	계(원)	남은금액(원)	500원	100원	50원	10원
1	500	370	1	0	0	0
2	800	70	1	3	0	0
3	850	20	1	3	1	0
4	870	0	1	3	1	2

가장 높은 가치의 동전부터 내림차순으로 목표 금액 (870원) 을 초과하기 직전 개수를 포함해나가면 위 표와 같이 나타낼 수 있다.

즉, 500원 1개, 100원 3개, 50원 1개, 10원 2개, 총 동전 7개가 있으면 860원을 최소 개수의 동전으로 조합할 수 있다.

이렇듯 동전 조합 문제에서는 그리디를 사용하는 것이 문제가 없어 보인다.

하지만, 이는 단위 동전 간 배수관계가 존재한다는 특정한 경우에 해당 하기 때문에 가능한 것이다.
10, 50, 100, 500 의 네 숫자는 서로 배수관계에 있다.

문제의 조건을 살짝 바꿔보자.

동전의 네 종류를 10원, 40원, 90원, 150원으로 변경하고 같은 문제를 해결해보자.

목표 금액은 870원이다.

절차	계(원)	남은금액(원)	150원	90원	40원	10원
1	750	120	5	0	0	0
2	840	30	5	1	0	0
3	840	30	5	1	0	0
4	870	0	5	1	0	3

이 경우, 그리디를 사용하였을 때, 150원 5개, 90원 1개, 40원 0개, 10원 3개, 총 9개의 동전을 사용해서 870원을 조합할 수 있다.

그럴듯하게 보이지만, 위 해는 최적해가 아니다.

150원 5개, 90원 0개, 40원 3개, 10원 0개를 사용하여 총 8개의 동전으로 870원을 만들 수 있기 때문이다.

위 문제에서는 표의 [절차 2]에서 오류가 발생한다.

남은금액인 120원을 소모하기 위해서 90원 1개를 선택하는 것이 이후 40원과 10원의 선택에 영향을 준다. 이는 탐욕적 선택 조건을 만족하지 못한다.

120원을 소모하기 위해 90원 1개 선택하는 것은 그 당시에 최선의 선택일 수 있지만, 이는 10원을 3개 선택하는 결과를 낳으며, 90원을 포기하고 40원을 3개 선택하는 선택지가 더 최선인 상황을 고려하지 못한다. 즉, 현재의 선택이 미래의 선택에 영향을 미친다!

동전 조합 문제 같은 경우에 이와 같은 탐욕적 선택 조건을 강제하는 세부 조건이 바로 단위 동전의 가치가 서로 배수 관계에 있다는 것이다.

4. 구현

그리디는 명확한 구현 형태가 존재하지 않는다. 여러 문제에 따라 형태가 매우 달라진다. 다만, 선택의 기로에서 항상 그때의 최선의 선택을 한다는 점은 변하지 않는다.

5. 적용

그리디는 항상 최적의 해를 보장하지 않기 때문에 조건을 만족하는지 확실하게 파악할 필요가 있다.

그리디를 활용할 수 있는 문제들 사이의 패턴의 상이 또한 해당 알고리즘의 적용을 고려하는데 난이도를 증가시킨다. 하지만 대체적으로 정렬 알고리즘을 사용한다는 공통점이 존재한다.

특정 문제를 해결하려고 할 때, 그리디를 적용하기 위해서는 보통 다음의 절차를 따른다.

그리디 적용 절차

1. 그리디 적용 가능 여부 파악
2. 명확한 선택 기준 정의
3. 데이터 정렬
4. 구현

5.1. 그리디 적용 가능 여부 파악

위에서 살펴본 탐욕적 선택 조건과 최적 하위 구조 조건을 만족하는지 여부를 판단한다.

동전간 배수관계가 존재할 때에 한한 동전 조합(이하의 동전 조합의 언급은 모두 해당 조건의 동전 조합만을 의미함) 의 경우, 탐욕적 선택 조건을 만족하며, 목표 금액의 동전 조합 문제를 남은 금액의 동전 조합 문제로 쪼갤 수 있으므로 최적 하위 구조 조건도 만족한다.

5.2. 명확한 선택 기준 정의

그리디는 매 순간 마다 선택을 하기 때문에, 어떠한 선택이 최선의 선택인지에 대한 명확한 기준을 설정할 필요가 있다.

동전 조합의 경우, 선택할 동전이 남은 금액을 초과하지는 않지만 가장 많은 개수가 되도록 선택한다는 기준을 설정하였다.

5.3. 데이터 정렬

반드시 모든 경우에서는 아니지만, 대부분의 경우 데이터의 정렬을 필요로 한다.

동전 조합의 경우, 더 높은 가치의 동전부터 내림차순으로 선택해나간다는 점에서 정렬이 사용된다.

5.4. 구현

매 선택의 순간의 최선의 선택을 하도록 구현한다.

6. 예제 문제 유형

• Fractional Knapsack (분수 배낭 문제)
• Activity Selection (활동 선택 문제)
• Huffman Coding (허프만 코딩)
• Coin Change (거스름돈 문제)

---

관련 포스팅

• [Problem] 배낭 문제 (Knapsack Problem)

참고 자료

• 그리디 탐욕 Greedy 알고리즘 설명 7분만에 이해하기
• 탐욕 알고리즘