[알고리즘] 그리디(Greedy) 기법 개념 및 구현코드

# 그리디(Greedy) 알고리즘 정의

그리디 기법(Greedy method)은 탐욕적 기법이라고도 한다.

모든 경우를 고려해 보고 가장 좋은 답을 찾는 것이 아니라 '그 순간에 최적'이라고 생각되는 답을 선택한다.

미래를 고려하지 않고, 현재 가장 저렴한 선택 or 현재 가장 가치있는 선택 or 가장 빠른 선택을 하는 것이다.

 

 

예를 들어, 아래 그림에서 시작 지점에서 가장 큰 수를 구하는 문제일 경우

가장 좋은 path는 6-128이지만, 그리디 알고리즘을 사용하면 17-23을 서택하게 된다.

이런 결과가 나오는 이유는 그리디 알고리즘은 현재 상황에서 가장 좋은 것을 선택하기에 이런 path가 나온다

출처: https://velog.io/@contea95/탐욕법그리디-알고리즘

 

 

 

 

# 그리디(Greedy) 조건

그리디 알고리즘은 항상 최적의 해를 찾는 것은 아니다.

현재의 최적 해 !== 전체의 최적 해 이기 때문이다.

따라서 근사 알고리즘이라고도 불리는데,

나름대로 좋은 결과를 찾을 수는 있지만, 항상 최적 해를 찾을 거라는 보장이 없기 때문이다.

 

탐욕적 알고리즘은 최적의 해답을 주는지 반드시 검증해야 한다.

실제로 많은 경우 최적해를 찾지 못하지만, 그리디 기법이 사용될 수 있는 경우는 다음과 같이 두 가지로 제한된다.

1. 현재 선택이 미래 선택에 영향을 미치지 않는 경우, 그리디를 써도 최적 해를 찾을 수 있다.(탐욕스런 선택 조건,Greedy Choice Property)

2. 부분의 최적 해가 모이면 전체의 최적 해가 된다.(최적 부분 구조 조건, Optimal Substructure)

 

탐욕적 기법은 결정 순간에 가능한 해 중에 지역적으로 최적인 것을 선택하고,

이러한 선택은 이후의 단계에서 다시 변경될 수 없다.

 

 

 

 

# 그리디(Greedy) 구현 코드

그리디 핵심은 정렬이다.

문제를 예시로 그리디를 구현해보자!

 

문제 : 편의점 알바

편의점에서 아르바이트를 하고 있는 중에, 하필이면 피크 시간대에 손님에게 거스름돈으로 줄 동전이 부족하다는 것을 알게 되었습니다.현재 가지고 있는 동전은 1원, 5원, 10원, 50원, 100원, 500원으로 오름차순으로 정렬되어 있고, 각 동전들은 서로 배수 관계에 있습니다.
동전 개수를 최소화하여 거스름돈 K를 만들어야 합니다. 
이때, 필요한 동전 개수의 최솟값을 구하는 함수를 작성해 주세요.

 

수도 코드

  // count =0
  //반복시작~(k!==0)
   //for(let item of arr)
    // arr = [500, 100, 50, 10, 5, 1] //k = 1230원
    // 1230/500 -->( .xxx --> 내림) --> count = 2
    // k = 1230-500*2개 = 230원
    // count = count + Math.floor(230/100)
    // k = 230-100*2 = 30 
    // k = k-(item*count)
  //return count

 

구현 코드

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

 

 

 

 

 

# 그리디(Greedy) 연습할 수 있는 백준 문제 리스트

출처 : 개발자로 취직하기 유튜브,  그리디 탐욕 Greedy 알고리즘 설명 7분만에 이해하기

 

 

 

 

 

 

 

참고 : https://velog.io/@devjade/JavaScript%EB%A1%9C-greedy-algorithm%ED%83%90%EC%9A%95-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

JavaScript로 greedy algorithm(탐욕 알고리즘) 구현하기