탐욕 알고리즘(Greedy Algorithm)

Greedy Algorithm 이란?

• 말 그대로 탐욕스러운, 욕심 많은 이라는 뜻이다. 매번 선택을 할 때마다 항상 최선의 방법을 선택한다.
• 그리디는 매 선택(지역적)으로는 최선을 택하지만 그 선택들이 최종(전역적)으로 봤을 때 최선이라는 보장은 없다.
• 매순간 최적을 따라가면 ex) 1-1-1-100 보다는 1-1-10-10이 전체적으로 봤을때는 더 짧은 길 이기 때문.

 

그리디 알고리즘 속성

• 그리디 알고리즘이 성립하려면 두가지의 조건이 필요하다.
  1. 탐욕 선택 속성 (Greedy Choice Property) :  이전의 선택이 다음 선택에 영향을 주지 않는다.
  2. 최적 부분 구조 (optimal substructure) : 매 선택의 순간의 최선이 전역적에 대한 최선이어야 한다.

 

이해를 위한 예시 및 문제

마시멜로 실험 ( 그리디 알고리즘 X )

• 마시멜로 1개를 주고 15분 동안 먹지않고 참으면 2개를 주기로 약속.
• 그리디 알고리즘의 경우는 전역적인 최적값을 구하지 못하므로 1개를 먹게되며 최적값을 얻을 수 없다.

거스름돈 문제 ( 그리디 알고리즘 O )

• 누군가 3200원 어치의 물건을 사고 5000원을 냈으면 거스름돈은 1800원이다.
• 이 때, 최소의 개수로 거스름돈을 줘야하는 경우 ( 거스름돈은 1000원, 500원, 100원, 50원, 10원 사용가능 )
• 정답: 1000원 1개, 500원 1개, 100원 3개다.
• 현재 주어진 거스름돈에서 최적을 선택한 결과다. 

 

예시 문제

• 프로그래머스 1레벨 예산 문제 - 풀이