그리디 알고리즘이란?
그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.
쉽게 말해 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자 하여 전체적인 최적 해를 찾는 알고리즘이다.
그리디 알고리즘 단점
그리디 알고리즘은 지금 당장 좋은 것만 고르는 방법으로, 현재의 선택이 나중에 미칠 영향은 고려하지 않는다.
💡 [문제] 노드에서 가장 합이 높은 방법을 선택하는 방법을 생각해 봅니다.
최적의 선택: 3+100=103
그리디한 선택: 10+8=18
첫번 째 단계에서 최적이지만 미래 선택까지 포함한다면 최적의 알고리즘이 아닐 수 있다.
그리디 알고리즘을 통해 문제를 해결하는 방법
👉 탐욕 알고리즘 문제를 해결하는 방법
- 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
- 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
- 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.
탐욕 알고리즘 예시
❗️탐욕 알고리즘을 일상 예시 1 – 매트로이드
하나몬은 오늘도 편의점에서 열심히 아르바이트하고 있다.
손님으로 온 박해커는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔다.
박해커는 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였다.
👉 이때 하나몬은 어떻게 거슬러 주어야 할까?
-
탐욕 알고리즘으로 동전의 개수를 헤아리는 일은 일반적으로 거스름돈으로 동전을 선택하는 방법과 동일하다.
-
거스름돈 960원을 채우기 위해서 먼저 500원짜리 동전을 한 개를 선택한다.
-
그다음은 100원짜리 동전을 네 개 선택하고, 그다음엔 50원짜리 동전과 10원짜리 동전을 각각 하나씩 선택할 것이다.
👉 탐욕 알고리즘의 문제 해결 과정을 적용
- 선택 절차
- 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.
- 적절성 검사
- 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다.
- 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.
- 해답 검사
- 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다.
- 액수가 부족하면 1번 과정부터 다시 반복한다.
👉 이 과정을 통해 얻은 문제에 대한 해답
가장 가치가 높은 동전인 500원 1개를 먼저 거슬러 주고 잔액을 확인한 뒤, 이후 100원 4개, 50원 1개, 10원 1개의 순서대로 거슬러 준다.
참고 자료
반복되는 실수를 기록을 통해 줄여가보자!