그리디 알고리즘

그리디 알고리즘 (Greedy Algorithm)

매 단계마다 최적이라고 생각되는 것을 선택하는 방식으로 최종적인 값을 구해내는 알고리즘

 

1) 탐욕 선택 속성 (Greedy Choice Property)

  : 각 단계에서 최선의 선택을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우를 뜻함.

2) 최적 부분 구조 (Optional Substructure)

  : 부분 문제의 최적해를 조합하여 전체 문제의 최적해를 구할 수 있는 경우를 뜻함.

 

* 알고리즘 과정

(i) 선택 절차 (Selection Procedure)

  : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.

(ii) 적절성 검사 (Feasibility Check)

  : 선택한 해가 문제의 조건을 만족시키는지 확인한다. 만족시키지 않을 경우, 해당 항목은 제외된다.

(iii) 해답 검사 (Solution Check)

  : 모든 선택이 완료되면, 그 최종 선택이 문제의 조건을 만족시키는지 확인한다. 만족시킨다면 해답으로 인정된다.

 

 

예시) 특정 금액을 가장 적은 동전 갯수로 지불하기

(i) 선택 절차 - 가장 가치가 큰 동전부터 선택

(ii) 적절성 검사 - 선택된 동전의 가치가 지불할 금액보다 크다면, 다음으로 작은 동전을 선택한다.

(iii) 합이 지불할 금액과 일치하면, 문제가 해결된 것이다.

 

출처: [Java/알고리즘] 그리디 알고리즘(탐욕법, Greedy Algorithm) 이해하기