[Algorithms] 그리디 알고리즘 Greedy Algorithm - 탐욕 알고리즘

그리디 알고리즘 Greedy Algorithm

최적해를 구하는 데에 사용되는 근사적인 방법,

여러 경우 중 하나를 결정해야 할 때마다 구 순간에 최적이라고 생각되는 것을 선택해 나아가는 방식.

= 당장 눈 앞에 보이는 최적의 선택, 간단하고 빠르지만 항상 최적의 답이 보장되지는 않음.

✅  그리디 알고리즘 문제 해결법

선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.

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

해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

✅  그리디 알고리즘 적용에 필요한 조건

그리디 알고리즘은 두가지의 조건이 만족될 경우 최적의 답을 보장함.

아래의 조건이 없어도 그리디 알고리즘을 사용할 수는 있지만, 최적해는 못구함.

• 이전의 선택이 이후에 영향을 주지 않는 ‘탐욕 선택 속성’
• 부분 문제의 최적결과가 전체에도 그대로 적용된다는 ‘최적 부분 구조’

위의 구조를 만족하면, 그리디 알고리즘이 항상 최적해를 찾아낼 수 있다.

이 구조를 매트로이드라고 한다.

✅  가장 유명한 그리디 알고리즘 예시 - 최소 동전으로 거슬러 주기

거스름돈을 거슬러 줘야하는상황

손님: 최소 동전의 개수로만 거슬러 달라고 요청

나: 최소 동전 개수 → 단위가 큰 500짜리 동전부터 선택하여 점점 작은 동전을 거슬러 줌.

❗️그리디 알고리즘의 문제 해결 과정 적용

1. 선택절차

거스름 돈의 동전 개수를 줄여야 하니 단위가 큰 동전부터 줌

2. 적절성 검사

1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사, 초과하면 가장 마지막에 서택한 동전을 삭제하고 1번과정으로 돌아함

3. 해답 검사

선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사, 액수가 부족하면 1번 과정부터 다시 반복

결론

가장 가치가 높은 500원짜리 동전부터 거슬러주고, 잔엑을 확인하고 100원, 50원, 10원 이렇게 거슬러 줌

→ 이 문제 구조는 매트로이드, 탐욕 알고리즘을 사용해도 언제나 최적해를 구할 수 있음

 

[출처 및 도움을 준 글]

https://hanamon.kr/알고리즘-탐욕알고리즘-greedy-algorithm/

엄청 많이 도움이 된 글! 예시가 이해하기 쉽다.

세상에 너무 똑똑하고 멋진 사람들이 많다.

 

👶🏻 관련 문제 풀이

https://dev-raeun.tistory.com/30

[BOJ] 백준 11047 동전 Python3

https://dev-raeun.tistory.com/31

[BOJ] 백준 13505 주유소 Python3