그리디 알고리즘(탐욕법, Greedy Algorithm)
그리디 알고리즘(탐욕법, Greedy Algorithm)
최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 각 단계에서 최적이라고 생각되는 것을 선택 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘이다.
이때, 항상 최적의 값을 보장하는것이 아니라 최적의 값의 근사한 값을 목표로 하고 있다.
주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용된다.
루트에서 출발하여 단말 노드까지 가는 경우를 생각해 보자.
거쳐가는 노드의 합이 가장 큰 경우는?
| 최적의 해 = 21 | 그리디 알고리즘 해 = 19 |
|---|---|
그리디 알고리즘 주요 속성
문제를 풀 때 두 가지 조건이 성립해야 그리디 알고리즘을 적용할 수 있다.
1. 탐욕 선택 속성(Greedy Choice Property)
각 단계에서 최선의 선택을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우를 말한다.
즉, 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져온다는 것이다.
2. 최적 부분 구조(Optimal Substructure)
전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있는 경우를 말한다.
즉, 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미한다.
그리디 알고리즘 단계
그리디 알고리즘의 단계는 매 단계마다 최적이라고 생각되는 선택을 하면서 최종적으로 전체적으로 최적인 해답을 찾아내는 과정을 의미한다.
1단계: 선택 절차(Selection Procedure)
현재 상태에서 최적인 선택을 한다. 이 선택은 이후에는 바뀌지 않는다.
2단계 : 적절성 검사(Feasibility Check)
선택한 항목이 문제의 조건을 만족시키는지 확인한다. 조건을 만족시키지 않으면 해당 항목은 제외된다.
3단계: 해답 검사(Solution Check)
모든 선택이 완료되면, 최종 선택이 문제의 조건을 만족시키는지 확인한다. 조건을 만족시키면 해답으로 인정된다.
그리디 알고리즘 예시
거스름돈
거스름 돈 문제는 전형적인 탐욕 알고리즘의 예시다.
💡 문제 확인
-거스름돈으로 6,480원을 거슬러줘야 할 때 500원, 100원, 50원, 10원짜리 동전이 무한정 존재한다면, 가장 큰 동전부터 가능한 많이 사용하는 방식으로 거스름돈을 계산한다.
💡 그리디 알고리즘 적용
선택 절차 : 거스름돈 문제에서 가장 가치가 큰 동전부터 선택한다.
적절성 검사: 만약 선택된 동전의 가치가 거스름돈보다 크다면 다음으로 작은 동전을 선택한다.
해답 검사 : 합이 일치하면 거스름돈 문제 해결
💡 거스름 돈 문제의 해법
500원으로 거슬러 줄 수 있는 만큼 거슬러 준다.
현재 금액 남은 금액 사용한 동전 수 6480원 480원 12(6480 / 500)개 100원으로 거슬러 줄 수 있는 만큼 거슬러 준다.
현재 금액 남은 금액 사용한 동전 수 480원 80원 12 + 4(480 / 100)개 50원으로 거슬러 줄 수 있는 만큼 거슬러 준다.
현재 금액 남은 금액 사용한 동전 수 80원 30원 12 + 4 + 1(80 / 50)개 10원으로 거슬러 줄 수 있는 만큼 거슬러 준다.
현재 금액 남은 금액 사용한 동전 수 30원 0원 12 + 4 + 1 + 3(30 / 10)개
💡 거스름 돈 문제 해결 코드
1
2
3
4
5
6
7
8
9
10
let money = 6480;
let coins = [500, 100, 50, 10];
let answer = 0;
for (let i = 0; i < coins.length; i++) {
answer += parseInt(money / coins[i]);
money = money % coins[i];
}
console.log(answer); // 20
📑 참고 자료