[알고리즘] 그리디 알고리즘 ( 탐욕 알고리즘, Greedy Algorithm)

이전 글 : )

[알고리즘] 백트래킹 알고리즘 ( BackTracking Algorithm )

 

---

 

 

 그리디 알고리즘 greedy algorithm 

 

그리디 (Greedy)는 '탐욕스러운, 욕심 많은'이라는 뜻을 가집니다.

탐욕스러운 알고리즘의 의미는 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달한다는 의미입니다.

그리디 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이며 여러 경로 중 하나의 루트를 결정해야 할 때마다 그 순간의 최적 루트를 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달합니다.

루트를 결정하는 그 순간은 지역적으로는 최적이지만, 선택을 이어나가 전역적인 최종 해답을 만들었을 때, 그것은 최적이라고 보장할 수 없습니다.

하지만 그리디 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들입니다.

 

 

 최적 동작 조건 

 

탐욕 알고리즘이 잘 작동하는 문제는 아래와 같은 조건이 만족되며 성립하지 않는다면 최적해를 구하기 어렵습니다.

 

- 탐욕 선택 속성 greedy choice property : 한 번의 선택이 다음 선택에서 전혀 무관한 값이어야 합니다.

- 최적 부분 구조 optimal substructure : 매 순간의 최적해가 문제에 대한 최적이어야 합니다.

 

 

 문제를 해결하는 방법 

 

- 선택 절차 selection preocedure : 현재 상태에서의 최적의 해답을 선택합니다.

- 적절성 검사 feasibility check : 선택된 해가 문제의 조건을 만족하는지 검사합니다.

- 해답 검사 solution check : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차를 돌아가 위의 과정을 반복합니다.

 

 

 예제 

 

그리디 알고리즘을 이해하기 위한 예제 문제입니다.

 

 거스름돈 문제 

카운터에서 점원이 거스름돈을 주는데 동전으로 거스름돈을 준다고 가정하고 500원, 100원, 50원, 10원짜리 동전이 무한하다고 가정합니다.

거슬러줘야 할 돈이 N원일 때 거슬러 줘야 하는 동전의 최소 개수를 구하면 됩니다.

이 문제의 핵심은 가장 큰 단위의 동전 먼저 거슬러 주는 것입니다.

# 그리디 알고리즘 예제_거스름돈 문제

N=int(input())

def greedy(n):
   cnt = 0
   money = 1000 - n
   coin = [500, 100, 50, 10, 5, 1]

   for i in coin:
       cnt += money//i		# 단위가 가장 큰 동전부터 거스름돈 채우기
       money %= i		# 다음 단위의 동전이 채워야 되는 남은 거스름돈
   return cnt			

print(greedy(N))

그리디 알고리즘의 해가 항상 최적의 해는 아닙니다. 그러기에 그리디 알고리즘의 사용으로 인해 문제의 해법을 찾았을 경우에는 정당성을 따져봐야 합니다.

위의 거스름돈 문제가 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 공전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문입니다.

대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정단 한 지 검토할 수 있어야 답을 도출할 수 있습니다.

 

---

다음글 : )

 

[알고리즘] 해시(Hash), 해시 테이블(Hash Table)