[알고리즘] Greedy Algorithm-탐욕 알고리즘

Greedy Algorithm(탐욕 알고리즘)이란?

greedy의 사전적 의미는 욕심 많은, 탐욕적인 이라는 형용사다.

 

그럼 욕심 많은, 탐욕적인 알고리즘이 도대체 뭐야??

 

간단하다 진짜 말 그대로

매 순간마다 욕심적으로 최적의 상황만을 고르는 알고리즘이다.

특징

탐욕 알고리즘은 크게 두 가지 특징이 있다.

1. 탐욕 알고리즘은 데이터 사이의 관계(단계별 관계)를 고려하지 않고 수행을 한다.

=> 이는 탐욕스러운 선택의 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다고 볼 수 있다.

2. 일단 선택한 것에 대해 절대로 번복하지 않는다.

=> 이미 선택된 데이터를 버리고 다른 것을 선택하지 않는다. (그래프 탐색은 아니라는 이야기)

 

이러한 특징들 때문에 대부분의 탐욕 알고리즘들은 매우 단순하며, 반면에 제한적인 문제들만 이 알고리즘으로 해결된다.

 

지역적 최적 => 전역적 최적?  

가장 대표적으로 동전을 거슬러 주는 상황을 보자.

 

거스름돈으로 260원을 줘야한다. 이때 동전의 개수를 최소로 하는 경우를 구한다고 치자.

그럼 남은 액수를 초과하지 않는 조건하에 '욕심내어' 가장 큰 액면의 동전을 고르면 된다.

• 500원은 안 되고 100원짜리 2개를 선택!
• 60원이 남았으니 50원짜리 1개, 10원짜리 1개면 끝!
• 100, 100, 50, 10

너무너무 간단하다. 위 조건만 만들어주고 결과값이 나올 때까지? 반복하면 된다.

 

그런데 만약 은행에서 220원짜리 동전을 발행했다면?

 

이 상황에서 액수를 초과하지 않는 조건하에 '욕심내어' 가장 큰 액면의 동전을 고르는 액션을 취하면

• 역시 500원은 안 되고 220원짜리를 선택
•  40원이 남았으니 10원짜리 4개를 선택
• 220, 10, 10, 10, 10

220원을 추가하지 않았을 때 구한 경우보다 동전 한 개가 더 많은 경우가 나오게 됐다.

 

이렇듯 그리디 알고리즘은 동전을 거슬러 준다는 문제 자체는 해결하지만, 최적의 해를 주지는 못하는 경우가 너무 많다.

이러한 문제점을 해결하기 위해 나타나 것이 동적 프로그래밍 알고리즘이다.

코테 문제 접근

실전에서 그리디로 푸는 문제임을 생각하기가 어렵다.

그래서 그리디 문제를 풀면 그리디를 사용한 이유를 설명하는 버릇을 들이고 반례를 찾는 연습을 해야한다.

 

한 문제를 예로 들어보자

---

링크: https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

---

결론부터 말하면

이 문제의 상황에서는 그리디를 적용하면 최적의 결과를 도출한다. (큰 금액의 동전부터 차감)

 

어떻게 판단하냐?

반례를 찾아보는 방법이 있는데 문제의 조건을 보면

 

A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수라고 나와있다.

 

이러한 경우에는 무조건 Ai를 안쓰고 Ai-1, Ai-2 ... 들을 이용해 Ai를 쓴 경우보다 적게 만들 수 없다.

이는 곧 반례가 없다라고 결론지을 수 있다.

그럼 바로 그리디 알고리즘을 사용해도 된다고 판단 가능!!

 

이렇게 어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾안낼 수 있다.

이 구조를 매트로이드라 함

 

장점

• 빠름
• 항상 최적이 아니라도 근사한 값을 도출

일단 요정도..?