탐욕 알고리즘(Greedy Algorithm)

그리디 알고리즘

그리디알고리즘, 욕심쟁이 알고리즘이란 "매 선택에서 지금 이순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가진 알고리즘이다.

그리디 알고리즘의 간단하게 설명 해보자면 마시멜로 실험으로 설명할 수 있다.

마시멜로 실험은 어린아이에게 마시멜로 1개를 주고 15분 동안 먹지 않고 참으면 2개를 주기로 하고 아동의 행동을 관찰했을 때, 기다리고 마시멜로를 받은 아이들과 그렇지 않은 아이들이 자라서 보여주는 성적과 학업성취도를 알아보는 실험인데, 만약 이 알고리즘으로 이 실험에 참여한다면 '당장 내 손에 있는 마시멜로 하나를 먹는다'라는 결과가 나오게 된다. 이 말은 곧 이 알고리즘의 한계이기도 한데

그리디 알고리즘은 매 선택이 '그 순간'에서는 최적이지만 종합적으로 봤을 때는 최적이라는 보장은 절대 없다는 것이다.

그렇기 때문에 그리디 알고리즘은 부분의 최적인 해들의 집합이 곧 전체의 해답이 될 때 사용 할 수 있다.

 

언제 사용 하나

그리디 알고리즘은

• 탐욕 선택 속성(greedy choice property)
• 최적 부분 구조(optimal substructure)

의 특성을 가지는 문제들을 해결하는 데 좋다. 여기서 최적 부분 구조란,

A - B - C 순서로 A에서 C로 이동할 때, A에서 B로 가는 경로와 B에서 C로 가는 경로가 각각 여러개 있고, 모두 거리가 다를 때 부분적으로 접근해서 A에서 B로가는 여러 길중에 가장 짧은 길과 B에서 C로 가는 길중에 가장 짧은 길을 선택함으로써 최적의 해를 얻어내는 것 이다.

 

예시

• AI 결정 트리 학습법
• 활동 선택 문제
• 거스름돈 문제
• 최소 신장 트리
• 제약조건이 많은 대부분의 문제
• 다익스트라 알고리즘
• 허프만 코드
• 크러스컬 알고리즘

실패하는 예시

• 외판원 순회 문제 : 외판원이 각 도시를 돌면서 영업을 하는데 어떤 경로로 가야 최적의 경로가 되는지 알아내는 문제

• 배낭 문제 : 가방에 어떤 짐을 넣어야 가방의 공간을 최대한 활용 할 수 있는지 알아내는 문제