그리디 알고리즘

그리디 알고리즘은 "지금 당장 눈앞에 보이는 최적의 상황만을 쫒는 알고리즘"이다.

그리디 알고르짐은 항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있다는 장점이 있습니다.

또한 특정한 상황에는 그리디 알고리즘이 최적의 해를 구할 수도 있습니다.

 

 

예제로 거스름돈 문제를 풀어보겠습니다.

예를 들어 670원을 걸러줘야하는 상황입니다.

이는 10원짜리 67개보다

500원짜리 1개 50원짜리 1개 10원짜리 1개를 주는 것이 총 3개로 더 효율적입니다.

따라서 이 경우 "무조건 더 큰 화폐 단위부터 거슬러준다"라는 알고리즘만 지키면 최적의 해를 구할 수 있습니다.

 

이러한 그리디 알고리즘은 기본적으로

무조건 큰 경우대로, 무조건 작은 경우대로,

무조건 긴 경우대로, 주고건 짧은 경우대로 등으로 극단적으로 문제에 접근한다는 점에서 정렬기법과 함께 사용되는 경우가 많습니다. 그 대표적인 예시가 이전에 다뤘던 크루스칼알고리즘입니다.

크루스칼 알고리즘은 모든 간선을 정렬한 이후 간선부터 연결하는 최소비용 신장트리 알고리즘이었습니다.

 

다시 거스름돈 예제를 보겠습니다

우선 무조건 큰 숫자의 화페부터 거슬러줍니다.

그리고 다음 화폐인 100원으로 거슬러 주는 경우를 구합니다.

이후 50원의 경우와 10원의 경우도구해줍니다.

 

남은돈이 0원이 되면 몇 개의 동전을 거슬러주면 되는지 확인하면 됩니다.

총 8개입니다.

이렇게 단순하게 큰 경우부터 알고리즘과 같이 간단하게 탐욕적으로 문제를 해결하는 기법을 그리디 알고리즘이라고 합니다.

 

function moneyChange(k) {
  let count = 0;
  const arr = [500,100,50,10];
  for(let item of arr){
    count = count + Math.floor(k/item); //동전의 개수
    k = k - item * Math.floor(k/item); // 남은 돈 계산
  }
  return count;
}

 

 

이후 포스팅에서 그리디에 관련된 문제를 풀어보겠습니다. 감사합니다.