<aside> 💡 그리디 알고리즘이란, 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 ‘각 단계에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘이다.

</aside>

→ 이때 항상 최적의 값을 보장하는 것이 아닌, 최적의 값의 근사한 값을 목표로 한다.

두 가지 조건이 성립해야 그리디 알고리즘을 적용할 수 있다.

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

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

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

   • 전체 문제의 최적해가 ‘부분 문제의 최적해로 구성’될 수 있는 경우

그리디 알고리즘 단계

<aside> 💡 그리디 알고리즘의 단계는 매 단계마다 최적이라고 생각되는 선택을 하면서 최종적으로 전체 최적인 해답을 찾아내는 과정을 의미한다.

</aside>

(1) 문제의 최적해 구조를 결정한다.

(2) 문제의 구조에 맞게 선택 절차를 정의한다. → 선택 절차(Selection Procedure)

• 이 단계에서는 ‘현재 상태’에서 ‘최적인 선택’을 한다. 이 선택은 이후에 바뀌지 않는다.

(3) 선택 절차에 따라 선택을 수행한다.

(4) 선택된 해가 문제의 조건을 만족하는지 검사한다. → 적절성 검사(Feasibility Check)

• 이 단계에서는 선택한 항목이 ‘문제의 조건’을 만족시키는지 확인한다. 조건을 만족시키지 않으면 해당 항목은 제외된다.

(5) 조건을 만족하지 않으면 해당 해를 제외한다.

(6) 모든 선택이 완료되면 해답을 검사한다. → 해답 검사(Solution Check)

• 이 단계에서는 모든 선택이 완료되면, ‘최종 선택’이 ‘문제의 조건을 만족’시키는지 확인한다. 조건을 만족시키면 해답으로 인정된다.

(7) 조건을 만족하지 않으면 해답으로 인정되지 않는다.

⭐Greedy Algorithm in Programmers

프로그래머스에 있는 그리디 문제들

체육복

조이스틱

큰 수 만들기

구명보트