탐욕 알고리즘(Greedy)

Greedy Algorithm(탐욕 알고리즘): 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택함
2. 적절한 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복함

탐욕 알고리즘의 예시

동전 거슬러주기

편의점에서 물건의 가격이 총 4,040원이 나왔다. 5,000을 내밀며 거스름돈은 최소한으로 거슬러주어야 함.

1. 선택 절차: 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택함.
2. 적절성 검사: 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사함. 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택함.
3. 해답 검사: 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사함. 액수가 부족하면 1번 과정부터 다시 반복함.

이 과정을 통해 얻은 문제에 대한 해답

가장 가치가 높은 동전인 500원 1개를 먼저 거슬러주고 잔액을 확인한 뒤, 이후 100원 4개, 50원 1개, 10원 1개의 순서대로 거슬러줌.

해결하려는 문제가 가져야하는 조건

• 탐욕적 선택 속성(Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않음
• 최적 부분 구조(Optimal Substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됨

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있음. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있음.