오늘의 결과

알고리즘 문제 풀이하기

탐욕법 은 요즘 코딩 테스트로 자주 나오는 문제로 이번 기회에 제대로 알고 가고자 기초 이론부터 정리를 진행합니다.

💡 그리디 알고리즘(탐욕법, Greedy Algorithm) 이란?

**각 단계에서 최적이라고 생각되는 것을 선택**해 나가는 방식으로 진행하여 최종적인 해답에
도달하는 알고리즘을 말합니다.

*- 이때, 항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표로 하고 있습니다.

• 주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용됩니다.*

그리드 알고리즘의 단계

💡 그리디 알고리즘의 단계

1. 문제의 최적해 구조를 결정합니다.

2. 문제의 구조에 맞게 선택 절차를 정의합니다 : **선택 절차**(Selection Procedure)

3. 선택 절차에 따라 선택을 수행합니다.

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

5. 조건을 만족하지 않으면 해당 해를 제외합니다.

6. 모든 선택이 완료되면 해답을 검사합니다 : **해답 검사**(Solution Check)

7. 조건을 만족하지 않으면 해답으로 인정되지 않습니다.

[출처](<https://adjh54.tistory.com/212>)

1단계: 선택 절차

<aside> 💡 이 단계에서는 ‘현재 상태’에서 ‘최적인 선택’을 합니다.

이 선택은 이후에는 바뀌지 않습니다.

</aside>

2단계: 적절성 검사

<aside> 💡 이 단계에서는 선택한 항목이 ‘문제의 조건’을 만족시키는지 확인합니다. 조건을 만족시키지 않으면 해당 항목은 제외됩니다.

</aside>