[알고리즘] Greedy Algorithms 그리디 알고리즘 개념 이해하기

1 | Greedy 알고리즘의 개념

그리디 알고리즘 (Greedy Algorithms) 은 한국어로 탐욕법, 탐욕 알고리즘라고 부른다.

그리디 알고리즘은 문제를 해결하는 과정에서 순간 순간 최적이라고 생각되는 방법을 찾으면서 결국 최종의 문제 해결로 도달하는것을 말한다.

 

 

2 | Greedy 알고리즘의 장점

빠른 계산속도! 그래서 Greedy의 방법이 통하는 문제에서는 최적해를 빠르게 구할 수 있다.

또한 일을 너무 많이해서 문제인 다이나믹 프로그래밍(Dynamic Programming) 과 서로 보완하는 개념으로 알려져 있다.

 

 

3 | Greedy 알고리즘이 통하는 문제 유형

 

1. 활동 선택 문제 (Activity Selection Problem)

시작시간, 종료시간이 주어지고 최대한 많은 작업을 소화할 수 있게끔 구현해야하는 문제. 어떻게 하면 하나의 작업만 어떤 시간에 스케쥴링 하면서 겹치치 않고 많은 스케쥴을 할 수 있는지에 대한것. ex) 적용사례 :  Meeting Room 알고리즘 문제

 

2. 허프만 부호화 (Huffman Coding)

주어진 문자열을 트리를 이용해 2진수로 압축하는 알고리즘 중 하나이다. 최소 힙(Heap)을 이용한다.

 

3. 작업 시퀀싱 문제 (Job Sequencing Problem)

Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes the single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be scheduled at a time.

Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes the single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be scheduled at a time.

작업해야할 배열과 작업이 끝나는 시간(Deadline)이 주어지고 작업이 데드라인 전에 끝난다면 이익/수익이 있는 문제

 

4. 배낭 문제 (Fractional knapsack Problem)

배낭에 물건들을 넣어서 판매할때 얻을 수 있는 최대의 이윤을 구하는 문제. 물건의 무게, 이윤액, 배낭의 크기가 주어진다.

 

5. Prim's Minimum Spanning Tree (MST)

MST는 graph의 vertex들을 최소 비용으로 연결한 tree이다.

 

 

 

참고1 : www.geeksforgeeks.org/job-sequencing-problem/

참고2 : greatzzo.tistory.com/51