그리디 알고리즘

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다.

 

그리디 알고리즘이란?

그리디 알고리즘이란 탐욕법이라고도 하며 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.

여러 경우 중 하나를 결정해야 할 때마다 그 순간 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 종합적으로 봤을땐 최적이라는 보장은 절대 없나는 것을 명심해야한다.

 

그리디 알고리즘을 적용하기 위한 조건

그리디 알고리즘을 적용하기 위한 조건으로는 탐욕스런 선택 조건과 최적 부분 구조 조건이 있으며,

이 두가지 조건이 만족되야 그리디 알고리즘이 잘 동작한다.

탐욕스런 선택 조건 
-. 앞의 선택이 이후의 선택에 영향을 주지 않는다.
최적 부분 구조 조건 
-. 문제에 대한 최적해가 부분 문제에 대해서도 역시 최적해이다.

위 조건들이 성립하지 않는다면 그리디 알고리즘은 최적해를 구하지 못한다.

하지만 이러한 경우에도 그리디 알고리즘은 근사 알고리즘으로 사용 가능하며 대부분의 경우 계산 속도가 빨라 실용적으로 사용 할 수 있다.

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만 어느정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다.

이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용 할 수 있다. 

근사 알고리즘
-. 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘
-. 근사 알고리즘은 가장 최적화되는 답을 구할 수 는 없지만 비교적 빠른 시간에 계산이 가능하고 어느정도 보장된 근사해를 계산할 수 있다. 

 

그리디 알고리즘의 정당성

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수는 없으며,

문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

 

참고자료

https://hanamon.kr/알고리즘-탐욕알고리즘-greedy-algorithm/

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

 https://fliphtml5.com/hkuy/lidy/basic

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전