[알고리즘] Greedy Algorithm(욕심쟁이 알고리즘)

근 한달만의.... 게시글....

오늘은 날로먹기 위해 쉬우디 쉬운 Greedy Algorithm

1. Greedy Algorithm 이란?

탐욕적 알고리즘(욕심쟁이 알고리즘)이라고도 하며, 

여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식

사실 Greedy algorithm을 적용할 수 있는 예는 많지않다.

코딩이 쉽고, 구현이 쉬운건 사실이지만

Greedy Algorithm으로 구한 해가 항상 최적의 해인 경우는 거의 없기 때문...!!

그래서 보통,

"근사치 추정"

을 위해 Greedy Algorithm을 사용한다.

TSP와 같은 NP-complete 문제를 풀기 위한 근사값을 추정하기 위해 사용한다.

Greedy Algorithm으로 구한 해는 최적의 해는 아니지만, 최악의 해도 아니다.

여기서 구해진 해는, Backtracking 및, Branch and Bound 방식에서 사용될 수 있다.

2. Greedy Algorithm이 적용 가능한 예

대표적으로, Minimum Spanning Tree 를 구하는 방법인 Prim Algorithm, Kruskal Algorithm이 있다.

그 외에도, 가중치가 있는 방향 그래프에서 최단거리를 구해주는 Dijkstra Algorithm, 거스름돈 나누기 등이 있다.

1. Kruskal Algorithm

그래프의 모든 간선(edge)중에서 가중치가 가장 작은 것부터 차례대로 선택한다(단, Cycle을 만드는 경우는 제외)

2. Prim Algorithm

임의의 정점(vertex)에서 가중치가 가장 작은 간선(edge)을 선택, 

선택된 정점(vertex)와 연결된 간선(edge)들 중에 가장 가중치가 작은 것들을 선택(단, cycle을 만드는 경우는 제외)

3. Dijkstra Algorithm

가중치가 있는 방향그래프에서 임의의 두 노드 사이의 최단거리를 구하는 알고리즘. 

4. 거스름돈 나눠주기

어떤 금액에 대한 거스름돈을 받고자 할때, 동전을 최소 갯수로 받게 하는 알고리즘.

단, 거스름돈 나눠주기가 항상 Greedy Algorithm으로 해결되는 것은 아니다.

실생활에서는 우리의 동전이 10, 50, 100, 500원 짜리 등이 있지만

만약,

내가 7원짜리 동전과 10원, 1원짜리 동전을 가지고 있을때

거스름돈 14원을 내주어야 한다.

최소갯수의 동전으로 거스름돈을 주는 방법은 7원짜리 2개를 주는 방법이지만,

Greedy Algorithm으로 문제를 해결하게 되면 10원짜리 1개와 1원짜리 4개를 내주게 된다.

그래서, 거스름돈 나눠주기 문제가 Greedy Algorithm이 적용 되기 위한 조건은

각각의 거스름돈이 서로의 배수/약수가 되어야 한다.

위의 반례같은 경우는 7원은 1원의 배수지만, 10원이 7원의 배수가 되진 않기때문에 적용 불가능하다.

실생활속의 우리 동전도 각각의 거스름돈이 서로의 배수/약수가 되기 때문에 Greedy Algorithm이 적용 가능하다.

5. Task Scheduling Problem

어떤 Task를 수행하는데 소요되는 시간이 각각 주어질때, 대기시간을 최소로 하여 모든 Task를 수행하게 하는 방법.

아주 대표적인 예로 운영체제 Scheduling Algorithm의 SJF Algorithm을 들 수 있다.

최소 시간이 소요되는 작업을 우선으로 Greedy하게 처리하면, 대기시간을 최소화 할 수 있다.

이 외에도 Knapsack problem에서 Greedy Algorithm을 적용하는 경우도 있지만, 

거스름돈 나눠주기와 같은 이유로 적용되지 않는 경우가 더 많다.

또한 데이터통신 공부를 하다보면 나오는, 

Huffman Encoding : 자주 보내야 하는 신호(패턴)를 더 짧은 길이의 비트로 인코딩 하는 방법 또한, 

Greedy Algorithm을 적용한 방법이라 할 수 있다.

그외에도 Greedy Algorithm을 적용할 수 있는 문제가 몇가지 더 있지만, 

사실 Greedy Algorithm은 그 자체로 쓰이는 경우보다 다른 문제와 함께 나오는 경우가 더 많으므로 이쯤만 소개하겠다.

보통 나는 코딩문제를 http://www.acmicpc.net 에서 푸는 편인데

여기서 순수하게 Greedy Algorithm만으로도 풀 수 있는 문제는,

11399(ATM) : https://www.acmicpc.net/problem/11399

11047(동전 0) : https://www.acmicpc.net/problem/11047

정도 있는것 같다.

그 외의 문제들은 다른 알고리즘과 살짝 연관을 시켜서 풀어야 할것 같다..^^

크....갈길이 멀다ㅠㅠㅋㅋㅋㅋ