탐욕 알고리즘(Greedy Algorithm)

안녕하세요. 부산 공수니 입니다. 오늘은 탐욕 알고리즘에 대해 알아보겠습니다. Dynamic Programming과 Divide and Conquer 과 더불어 중요하다고 판단이 되는 알고리즘입니다. 

 

단어의 부정적인 부분 때문에 탐욕 알고리즘을 안 좋다고 생각할 수도 있지만 사실 탐욕 알고리즘이 효율적이고 간단한 경우도 많습니다. 

 

: 미리 정한 기준에 따라 가장 좋아보이는 답을 선택 !

 

이는 동적 프로그래밍과 더불어 최적화 문제를 푸는데 사용됩니다. 상대적으로 탐욕 알고리즘이 설계하기 더 쉽습니다. 물론 이게 최적화된 알고리즘인지에 대한 증명이 반드시 필요합니다 .동적 프로그래밍은 재귀 관계식을 세워서 입력사례를 더 작은 입력사례로 분할하짐나 탐욕 알고리즘은 입력사례를 분할하지 않습니다. 그저 더 좋아보이는 답을 순서대로 하나씩 모아서 최종 답을 구축합니다. 즉 그 순간(locally)에는 최적이라는 말 입니다.

 

예를 들어 편의점에서 560원을 거슬러줘야하는데 10원짜리 56개를 줄 수는 없을 겁니다 최적은 일단 제일 큰 500원, 그 다음으로 가능한 수에서 큰게 50원 그리고 10원을 줄 겁니다. 이와 같이 순간에 최적을 선택하는 게 탐욕 알고리즘입니다. 

 

어느 동적이 가장 좋은지(locally 최적) - 선택과정(selection procedure) 

동전이 거스를 돈에 총액을 넘지 않는지 확인 - 적절성검사(feasibility check)

그리고 다 거슬러줬는지 확인 - 해답점검(solution check)

 

 

 

정리

-선택과정 : 집합에 추가할 다음 원소 고른다. 그 당시 최적을 선택하는 탐욕 기준에 따라 선택

-적절성 검사 : 새로운 집합이 해답이 되기 적절한지 검사

-해답 점검 : 새로운 집합이 문제의 해답인지 검사