[알고리즘] Greedy Algorithm (탐욕알고리즘) 이란

그리디 알고리즘이란? 

최적의 값을 구해야하는 상황에서 사용되는 방법으로

' 매선택에서 지금 이순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자'  가 모토이다.

 

비유하자면 마시멜로 실험을 생각하면된다 -> 그리디 알고리즘을 사용한다는것은 당장 눈앞에있는 마시멜로를 먹는것이다.

하지만 이방법을 사용하는것은 기다렸다가 2개를 먹는다라는 최적해를 보장해주지 못한다

 

 

사용하는이유

항상 최적의 선택을하기때문에 앞서봤던 깊이우선탐색(dp) 보다 빠른 속도를 낸다

 

특징

최적부분 구조이다. -> 한번의 선택이 다음선택에는 전혀 무관한 값이며 매순간의 최적해가 문제에대한 최적해야여한다는의미이다.

 

 

 

 

그리디의 에니메이션 출처 : 위키피디아

 

 

원리

위의 그림을 보면서 아래 설명의 봐보자. 

1. 시작 정점을 7로 설정 (최대값을 구할때)

2. 3과 12중에 하나를 골라! 당장! 12가 크네 선택

3. 5과 6중에 하나를 골라! 당장! 6이 크네

 

이런식으로 탐색을 한다. 당장의 선택에만 선택하므로. 당장의이익만보는 그리디 알고리즘이라 하는것이다.

 

장단점

장점

간단하고 직관적인 방법이다.

또한 원리를 나열할때 3번에 끝난것을보아 계산 시간이 짧아서 대용량 데이터에도 적용이 가능하다

 

 

단점

최적화가 보장되지 않는다는 것이다. 위의 에니메이션을 보면 

맨아래노드의 최대값이 99인 큰값이 존재해서   7 ->3 -> 99 로 진행한다면 더 큰 최대값을 도출할수있는데

당장의 큰값만 선택하다보니 보다 작은 값이 도출되었음을 알 수 있다.

 

 

코드

function getChange(value) {
  let changes = [10000, 5000, 1000, 500, 100, 50, 10];
  let won = Math.floor(value / 10) * 10; // 1의 자리 원화 반내림
  let i = 0;
  let counts = [];

  while (true) {
    if (won >= changes[i]) {
      let count = Math.floor(won / changes[i]);
      won = won - changes[i] * count;
      counts[i] = count;
    } else {
      counts[i] = 0;
    }

    i++;
    if (won === 0) {
      for (let j = 0; j < changes.length - i; j++) {
        counts.push(0);
      }
      break;
    }
  }

  changes.map((change, index) => {
    console.log(`${change.toLocaleString()}원 ${counts[index]}개`);
  });
}