[Algorithm] 그리디 알고리즘(Greedy Algorithm)이란?

 

1. 그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘은 다음과 같이 불리기도 한다.

• 욕심쟁이 방법
• 탐욕적 방법
• 탐욕 알고리즘 

이렇게 불리는 이유는 단어의 정의 때문이다.

Greedy
1. 욕심 많은
2. 탐욕적인

최적화 문제를 해결하는 알고리즘 중 하나이다. 각 단계에서 선택가능한 해들 중에서 가장 좋은 해를 찾는 문제이다. 데이터 간의 관계를 고려하지 않고 수행 과정에서 단계에 최적해인 최솟값 또는 최댓값을 가진 데이터를 선택한다.이를 '근시안적 선택'이라고 말하기도 한다.  

각각의 단계에서의 선택(부분해)을 모아서 문제의 최적해를 도출한다.

 

2. 그리디 알고리즘의 특징

섬 A에서 섬 C를 가는 최소 경로를 구하는 문제를 통해 알아보겠다.

섬 A 에서 섬 C로 가려면 A to B, B to C로 가야한다.

A to B 의 부분해, B to C 의 부분해를 구해서 문제의 최적해를 구한다.

여기서 특징을 알 수 있다. 각 단계에서 구한 답은 절대로 번복하지 않으며, 이후 단계는 이전 단계의 데이터를 통해 계산하지 않는다.(독립적)

 

다시 특징을 정리하자면

 

1. 한번 선택한 해답 (각각의 단계에서 구한 부분해)은 절대로 번복하지 않는다. 즉, 선택한 데이터를 버리고 다른 것을 취하지 않는다.

2. 알고리즘은 단순하며, 매우 제한적인 문제들만 그리디 알고리즘으로 해결가능하다.

3. 다른 알고리즘에 비해 계산시간이 매우 빠른 편이다.

 

그리디 알고리즘을 문제를 해겷하기 위해선 각각의 최적해들이 항상 최적임을 보장해야한다. 

 

3. 그리디 알고리즘과 동적 계획법의 차이

( Greedy Algorithm vs Dynamic Programming(DP))

구분	Greedy Algorithm	Dynamic Programming
기본 원리	매 단계에서 지역적으로 최적인 선택을 한다. 부분해들을 모아 전체 문제를 해결한다.	부분 문제의 최적해를 찾아 전체 문제를 해결한다.
접근 방식	각 단계에서의 문제만을 해결한다.	문제를 작은 부분 문제로 나누어 해결한다.
메모리 사용	적다.	많다. ( 부분 문제의 해를 저장)
속도	빠르다.	느릴 수 있다. (부분 문제 계산 시간에 따라 다르다)
정확성	항상 최적해를 보장하지 않는다.	항상 최적해를 보장한다. (부분문제들을 모두 고려했기 때문이다.)
장점	구현이 빠르고, 속도가 빠르다.	복잡한 문제에서도 최적해를 항상 보장한다.
단점	최적해를 항상 보장하지 않는다.	메모리 사용량이 크며 문제에 따라 구현이 복잡할 수 있다.

 

4. 그리디 알고리즘 예시 

다음은 그리디 알고리즘을 사용하는 예시이다.

4.1 동전 거스름돈 ( Coin Change)

https://giliit.tistory.com/61

4.2 최소신장 트리 ( MST, Minimum Spanning Tree)

• Kruskal MST
• Prim MST

4.3 최단경로 찾기 ( Shortest Path)

• Dijkstra Shortest Path

4.4 부분 배낭 문제 ( Fractional Knapsack)

 

4.5 부분 집합 문제 ( Set Covering)

 

4.6 작업 스케줄링 ( Task Scheduling)

 

4.7 허프만 압축 ( Huffman Coding)