[알고리즘] 그리디 알고리즘(Greedy Algorithm)

 

 

그리디 알고리즘(Greedy Algorithm)

- "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법

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

 

 

 

 

◾ 그리디 알고리즘 문제를 해결하는 방법

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

 

◾ 예시

그리디 알고리즘의 예로 거스름돈 계산 문제가 있다.

거스름 돈 n이 있고, 500원, 100원, 50원, 10원으로만 거슬러 주어야 할 때, 최소 개수의 동전으로 거슬러 주고, 동전의 개수를 구하는 문제이다.

 

만약, 주어진 n이 1380이라면 다음과 같은 순서로 문제를 풀 수 있다.

1. 최소 개수의 동전을 거슬러 받기 위해 가장 큰 화폐 단위부터 돈을 거슬러 준다.
2. 500원으로 거슬러 줄 수 있는 돈은 1,000원으로 2개이고 남은 돈은 380원이다.
3. 남은 돈에서 100원으로 거슬러 줄 수 있는 돈은 300원으로 3개이고 남은 돈은 80원이다.
4. 남은 돈에서 50원으로 거슬러 줄 수 있는 돈은 50원으로 1개이고 남은 돈은 30원이다.
5. 마지막으로 10원으로 거슬러 줄 수 있는 돈은 30원으로 3개이고 남은 돈은 0원이 된다.
6. 따라서 동전의 최소 개수는 2 + 3 + 1 + 3인 9가 된다.

// 거슬러 주어야 할 돈
let n = 1380;
// 동전의 개수를 셀 count
let count = 0;

// 거스름 돈의 종류를 담은 배열
const type = [500, 100, 50, 10];

for (let i = 0; i < type.length; i++) {
    // 500원부터 거슬러 줄 수 있는 동전의 개수 세기
    count += Math.floor(n / type[i]);
    n %= type[i];
}

console.log(count);

[출처] https://ittrue.tistory.com/196 [IT is True:티스토리]