[알고리즘 기본] 탐욕(Greedy) 알고리즘

1. 탐욕 알고리즘 (Greedy Algorithms)

탐욕(Greedy)은 말 그대로 지나치게 욕심이 많다는 뜻이다.

그렇다면 탐욕알고리즘은 무엇일까?

미래를 생각하지 않고 현재의 단계에서 가장 최선의 선택을 하는 것을 탐욕알고리즘이라고 한다.

동적프로그래밍은 간단한 프로그래밍에 사용 시 많은 단계를 거쳐 사용돼 비효율적이다.

(동적프로그래밍 : 경우의 수를 모두 검토해 점화식을 통해 구성)

동적프로그래밍을 대체하는 것은 아니고 동적프로그래밍과 같이 상황에 맞게 쓰이는 것이 탐욕알고리즘이다.

2. 탐욕알고리즘의 성립 조건

탐욕적 선택 속성(Greedy Choice Property) : 탐욕적 선택이 전체 문제의 최적해를 구할 수 있다 , 앞의 선택이 다음 선택의 영향을 주지 않는다.
최적 부분 구조(Optimal Substructure) : 문제에 최종 해결방법이 부분 문제에도 최적의 해결방법이다.

위 조건이 성립되지 않으면 탐욕알고리즘은 최적의 해를 구할 수 없다.

➡️ 근시안적으로 판단하고 문제를 해결하기 때문에 전체적으로 최적의 해를 구한다고 보장되지 않는다.

➡️ 대신 근사알고리즘으로 사용이 가능해 실용적으로 사용이 가능하다.

➡️ 항상 최적의 해는 아니지만 계산 속도가 빠르다.

3. 탐욕알고리즘이 최적이 될 수 없는 경우

1) 마시멜로우 이야기

1분을 기다리면 마시멜로우 1개를 받을 수 있다.

2분을 기다리면 마시멜로우 4개를 받을 수 있다.

탐욕알고리즘 선택 시 : 현재에서 가장 최선의 선택을 하므로 1분을 기다려 마시멜로우 1개만 받는다.

전체적으로 봤을 때 최적의 선택을 한다면 1분을 더 기다려 마시멜로우를 4개 받는 것이 더 이득이다.

2) 도둑 이야기

나는 도둑이다.

옆집 강부자네 집에 들어가 물건을 담아 훔치려고 한다.

하지만 내 가방은 35kg까지 밖에 담을 수 없다.

강부자네 집에서 무엇을 훔쳐야 할까?

강부자네 집 물건들

🥁 드럼 30kg $1,500
🏆 금반지 15kg $2,000
📺 티비 10kg $2,000
🎹 피아노 30kg $3,000

탐욕알고리즘으로 물건을 훔칠 때

가방에 넣을 수 있는 가장 비싼 물건을 넣는다.
그다음으로 넣을 수 있는 물건 중 가장 비싼 물건을 넣는다.

가장 비싼 물건인 피아노를 가방에 넣으면

5kg밖에 남지 않아 더 물건을 담을 수 없다.

따라서 훔칠 수 있는 물건의 가치는 $3,000이다.

하지만 피아노 대신 티비와 금반지를 넣었다면?

총 $4,000 가치의 물건을 훔칠 수 있다.

위에 설명한 거처럼 근시안적으로 문제를 판단하고 해결하기 때문에

항상 최적의 해를 보장하지 않는다는 것을 알 수 있다.

3. 탐욕알고리즘이 최적이 되는 경우

백준 알고리즘 문제 11047번 : 동전 0

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

11047번: 동전 0

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

www.acmicpc.net

위 문제는 탐욕적 선택속성과 최적 부분 구조가 성립되므로 탐욕알고리즘을 사용해 최적해를 구할 수 있다.

현재의 선택이 다음 선택에 영향을 주지 않고 전체 문제 해결방법이 부분 문제 해결방법이 된다.

동전의 개수를 줄이기 위해서 가장 가치가 높은 동전을 선택하고 이후에 한 단계 아래 있는 동전들로 남은 값을 채워나간다.

자바스크립트 예시코드

const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
let arr1 = input.shift().split(' ');

// 준규가 가진 동전의 총 개수
let length = arr1[0];

// 가치의 합
let k = arr1[1];

// 동전이 오름차순으로 들어있는 배열
let coins =  input.map(Number)

// 동전의 개수를 담기위한 변수 count
let count = 0;

// 탐욕알고리즘 사용
// 가치가 가장 큰 (값이 제일 큰) 동전으로 k를 채우고 남은 값은
// 그 아래로 가치가 큰(값이 큰) 동전들로 채워간다
for (let i = length ; i >= 0 ; i --) {
	// 동전 사용의 적절성 검사
    if (coins[i] <= k) {
    	// 동전의 개수를 몫으로 계산해 소수점을 버리고 count에 더함
        count += Math.floor(k / coins[i]);
        // 나머지 값을 k에 저장
        k = k % coins[i];
    }
}

console.log(count);