[Algorithm] Greedy Algorithm

 

오늘부터 본격적으로 알고리즘 공부를 시작하려 한다.

 

쫄지마 나 자신...!

 

우선 그 첫 번째 시작을 Greedy Algorithm에 관한 포스팅으로 시작하려 한다. 

 

Greedy Algorithm 이란 무엇인가?

 

탐욕적 알고리즘(Greedy Algorithm)은 각각의 작은 단계에서 최선의 선택을 내림으로서 전체적으로 최적의 솔루션을 찾아내는 알고리즘 전략을 말한다. 즉 탐욕적 알고리즘은 순간순간마다 결과는 신경 쓰지 않고 최선의 솔루션을 선택하게 된다는 뜻이다. 최선의 아웃풋을 즉각적으로 골라내지만, 전체적인 그림은 고려하지 않기 때문에 '탐욕적'이라고 부른다. 

 

탐욕적 알고리즘은 각가의 단계에서 최적의 해답을 선택하고 끝이 나타날 때까지 다음 단계로 넘어가는 방식으로 동작한다. 각각의 단계에서 선택하는 해답이 전체적으로도 최적의 해답이기를 기대를 하지만 종종 전체적으로는 최적이 아닌 경우가 생긴다. 사실, 대부분의 최적의 최단거리 찾기 문제에서는 전체적으로는 최악의 결과를 도출해 낸다.

 

공장에서 제품을 빨리 만드는 방법으로 한 번 생각해보자. 단기간적으로는 대량생산은 단가를 낮추지만 결국에는 생산품의 질 저하로 판매량이 줄어들고 소비자들이 싼 브랜드로 인식하게 하는 부작용이 있을 수 있다. 하지만 이런 경우만 있는 것은 아니다. Huffman tree나 decision learning tree와 같이 수많은 애플리케이션에서 탐욕적 알고리즘은 최적의 혹은 가장 근접한 결과를 찾아낼 수 있다. 

 

예: 아래 트리에서 합이 가장 큰 루트를 찾으라고 한다면, 탐욕적 알고리즘은 전체적으로 더 큰 합을 가지는 오렌지 색이 아닌 근시안 적으로 파란색 경로를 따를 것이다. 

 

 

출처: https://www.techopedia.com/definition/16931/greedy-algorithm