[알고리즘] 그리디 알고리즘(Python)

백준을 풀다보면 알고리즘 분류에 '그리디 알고리즘'이 자주 보인다. 그리디 알고리즘은 가장 기초가 되는 알고리즘이자 복잡한 문제를 단순하고 강력하게 해결해줄 수 있는 알고리즘이다. 

 

1. 그리디 알고리즘이란 ? 

 

출처 : https://gamedevlog.tistory.com/60

그리디 알고리즘은 단순하지만 빠르고 강력하다 ! 

 

Greedy는 탐욕적이라는 뜻이다. 즉, 그리디 알고리즘은 탐욕적으로 문제를 푸는 알고리즘이라는 뜻으로 탐욕법이라고도 한다 ! 

** 탐욕적 -> 문제를 풀 때 현재 상황에서 가장 좋은 것을 고르는 방법 = 현재 상황에서 '최적'이라고 생각하는 해를 선택하는 방법 

     말 그대로 현재 상황만 고려하고 앞으로 남은 선택들은 고려하지 않기 때문에 항상 최적해(Global optimum)을 보장하진 않는다. 

 

 

2. 그리디 알고리즘의 정당성 

대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 있을까?

정당성에 대해서 따져보아야한다. 그리디 알고리즘은 항상 최적해를 보장하지 않기 때문이다. 

 

  1. 탐욕적 선택 속성(greedy choice property)  

- 앞의 선택이 이후의 선택에 영향을 주지 않는다. 

 

- 그리디한 선택이 언제나 최적해를 보장해야한다. 

그리디 알고리즘에서는 현재 상황만을 고려한다. 그런데 이렇게 고려한 현재상황들이 최적해(Global optimum)을 만족시켜야한다는 것이다 ! 즉, 현재 순간의 최적에 대한 선택을 번복하지 않는다 

 

  2. 최적 부분 구조 (optimal substructure) 

 

- 부분 최적해(Local optimum)들이 모여 전체 최적해(Global optimum)로 이루어지는 경우 

즉, 문제의 최종 해결은 부분 문제에 대한 최적 문제 해결 방법을 통해 구성된다는 것이다. 

 

 

3. 그리디 알고리즘의 한계 

 그리디 알고리즘은 항상 최적해에 도달할 수는 없다. 는 한계를 가지고 있다.

그렇기에 다익스트라와 유사하지만 정확도에서는 떨어진다는 한계를 가지고 있다. 

 

- 그리디 알고리즘은 항상 최적의 해를 구할 수는 없음 

- 최적의 해에 가까운 값을 구하는 방법으로 활용 

- 그리디 알고리즘은 근사치 추정에 활용 ( 즉, 정확성 보장이 어려움 ) 

 

 

4. 그리디 알고리즘의 예시 

 

** 예시는 백준 문제를 통해 작성하서 추가해보겠다 !! 

 

주로 많은 예시로는 동전 수 구하기 배낭 문제 등이 있다. 

 

참고  : 

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬

https://velog.io/@zz1996zz/%ED%83%90%EC%9A%95-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Greedy-Algorithm

탐욕 알고리즘(Greedy Algorithm)

 

https://seungjuitmemo.tistory.com/23

알고리즘: 그리디 알고리즘(Greedy Algorithm) 공부하고 예제 한번 풀어보자!