그리디 알고리즘에 대하여(Greedy Algorithm)

그리디 알고리즘이란?

최적의 값을 구하는 알고리즘중 하나로써 각 단계에서 문제에 대한 가장 좋은 선택지를 선택해나가는 것을 반복하여 우리가 원하는 최종 해에 대한 근사한 값을 가지는게 목표이다.

(보통 문제를 단계별로 나누어 가장 좋은 선택지를 고르고 이후에 가장 좋은 선택지를 모두 더 해서 전체적인 해를 도출해내는 것이다.)

 

밑에 그림이 가장 간단하게 보여주는 것 같은데 문제는 더했을 때 가장 큰 수를 찾아라

우선 첫 번째 그림은 그냥 아무 선택지나 골라서 간 것이다.

https://velog.io/@kyunghwan1207/%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Greedy-Algorithm-%ED%83%90%EC%9A%95%EB%B2%95

 

두 번째 그림은 각 각의 선택지에서 가장 큰 수를 찾아서 더하는 것이다.

(정답은 아닐 수도 있지만 정답에 근사값을 구할 수 있다)

https://velog.io/@kyunghwan1207/%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Greedy-Algorithm-%ED%83%90%EC%9A%95%EB%B2%95

 

 

그럼 그리디 알고리즘을 적용할 수 있는 조건을 보자

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

각 단계에서 가장 좋은 선택을 했을 때 문제 천제에 대한 최적의 해를 구할 수 있다는 경우이다.
(가장 이상적인 선택을 하는 것이 전체적으로 봤을 때 최적의 결과를 불러올 수 있나?) 를 따져보라는 이야기다.

 

 

2. 최적 부분 구조(Optimal Substructure)

전체 문제의 최적의 해가 부분 문제의 최적의 해로 될 수 있나?
(전체적인 문제를 작은 문제 단위로 나누어 최적의 해를 구하고 전체적인 해로 합칠 수 있나?) 를 따져보는 이야기다.

 

그리디 알고리즘의 실행 단계

1. 문제의 해를 어떻게 구할건지 구조를 결정하고 그에 맞는 선택 절차를 정의합니다
   (선택 절차 : Selection Procedure)
2. 선택 절차에 따라 해를 구하고 문제의 조건에 맞는지 검사합니다, 단 조건에 맞지않으면 해당 해를 제외합니다.
   (적절성 검사 : Feasibility Check)
3. 모든 선택이 완료되면 해답을 검사합니다.
   (해답 검사 : Solution Check)
4. 조건이 만족된다면 해로 인정하지만 그렇지 않을경우 해답으로 인정되지 않습니다.

 

선택 절차 : Selection Procedure

전체적인 문제를 부분적인 문제로 나누었을 때의 상태에서 최적인 선택을 고릅니다.

(나중에 바꿀 수 없습니다)

 

적절성 검사 : Feasibility Check

선택한 항목이 문제의 조건을 만족시키는지 검사합니다.

(만족시키지 못했다면 해당 해를 제외합니다)

 

해답 검사 : Solution Check

모든 선택이 완료되면 최종 선택으로 만들어 문제의 조건을 만족시키는지 확인합니다.

(만족시켰다면 해답으로 인정합니다)

 

---

 

추가적인 자료

그리디 알고리즘 vs 동적 계획법

출처 : https://adjh54.tistory.com/212