탐욕 알고리즘 (Greedy Algorithm)

⚡탐욕알고리즘(Greedy Algorithm)이란?

 

매순간 최적 해를 선택하면서 최종적으로 최적해에 도달하는 알고리즘 설계기법

쉽게 생각하면 당장 눈 앞에 놓인 선택지 A, B 중 당장 더 좋은 선택지를 고르는걸

반복하는 것으로 최종적인 해답에 도달하는 방법입니다.

 

욕은 인간에게는 죄악이지만

문제를 풀 때에는 아주 좋은 방법이 될 수도 있군요

 

지역적으로는 최적인 선택이지만 항상 전역적으로 최적이라는 보장은 없지만

보통 탐욕알고리즘을 활용하는 문제는 지역적으로 최적이면서 전역적으로도 최적인 문제들입니다.

 

 

---

 

⚡탐욕알고리즘 정리

 

1. 매순간 최적해를 선택하면 최종적으로 최적해에 도달

2. 현재 상황에서 지금 당장 좋은 것만 고르는 방법

3. 일반적으로 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력이 필요함.

4. 정당성 분석이 중요(지역적으로 최적인 선택을 반복하는것으로 최적해를 구할 수 있는지 검토할 능력)

 

---

🔍대표적인 문제

 

거스름돈 문제

당신은 음식점의 계산을 도와주는 점원입니다.
카운터에 거스름돈으로 사용할 500, 100, 50 , 10원짜리 동전이 무한히 존재한다.
손님에게 거슬러 주어야할 돈이 N원일 때 거슬러 주어야할 동전의 최소개수를 구할 것
거슬러줘야할 돈 N은 항상 10의 배수임.

 

거스름돈은 가장 큰 화폐 단위부터 돈을 거슬러 주면 최적해를 얻을 수 있습니다.

위 문제에서 동전은 큰 단위가 항상 작은 단위의 배수이므로

작은 단위의 동전들을 조합해서 더 좋은 해를 만들 수가 없기 때문에

그리디 알고리즘을 사용할 정당성이 있는 문제라고 볼 수 있을것입니다.

 

let n = 1260
let counter = 0
let arr = [500,100,50,10]

for(i=0 ; i<arr.length; i++) {
	counter += Math.floor(n / coin)
    n = n % arr[i]
}

 

강의를 보면서 참고하고 있는데 강의는 파이썬으로 들어서

제가 자바스크립트로 간단하게 구현해봤습니다.

이런식으로 구현하면 항상 최적해를 구할 수 있겠네요

자료구조랑 결합되지 않으면 방법론 자체는 간단한데 이거저거 섞여서 나와서 어렵게 느껴지는건지