[알고리즘 개념] 그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘 (Greedy Algorithm)

개념

• 그리디 알고리즘(욕심쟁이 알고리즘)이란 매 선택에서 지금 당장 최적인 답을 선택하는 알고리즘 설계 기법이다

• 그리디 알고리즘을 사용하면 매 선택에서는 최적이지만 종합적으로 최적은 보장할 수 없다

문제가 다음과 같은 조건일 때 그리디 알고리즘을 사용할 수 있다

• 탐욕 선택 속성(Greedy Choice Property)

• 최적 부분 구조(optimal substructure)

한번의 선택이 다음 선택에 전혀 무관한 값이여야 하며 매 순간 최적해가 문제 전체의 최적해여야 한다

대표적인 그리디 알고리즘 문제 : 거스름돈 구하기

• 문제 : 동전이 500원, 100원, 50원, 10원이 있을 때 3760원을 만들 수 있는 동전의 최소 개수를 구하라

  이 문제는 동전 가치가 큰 동전부터 최대 개수를 구해가면 해결할 수 있는 문제로 탐욕 선택 속성과 최적 부분 구조의 특성을 가진다

  500원 * 7 = 3500원

  100원 * 2 = 200원

  50원 * 1 = 50원

  10원 * 1 = 10원

  = 3760원 => 11개

  
  
  

• 만약 동전이 500원, 400원, 300원, 10원 이런식으로 있었다고 가정하고 1700원을 만들 수 있는 동전의 최소 개수를 구해보자

  그리디 알고리즘으로 풀면 500원의 최대 개수인 3개를 구할 것이다

  그렇다면 남은 200원은 10원으로 채워야 하기 때문에 총 23개라는 답이 나온다

  하지만 동전의 최소값은 500원이 2개, 400원 300원이 각각 1개인 총 4개 이다

  이는 동전들에 배수관계가 성립하지 않아서 그리디 알고리즘의 조건에 맞지 않았고 결국 최적값을 구하지 못하였다

• 그리디 알고리즘은 100% 최적해를 보장하지 않지만 적당한 방법을 제시한다. 특히 정확한 알고리즘에 비해 빠른 경우가 많기 때문에 실용적으로 사용할 수 있다

출처 : 나무위키