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

SungWoo·2024년 11월 23일

알고리즘 탐욕법

알고리즘

목록 보기

5/8

Greedy Algorithm (탐욕법)

그리디 알고리즘은 매 순간 최적이라고 판단되는 선택을 하며 문제를 해결하는 방식

특징

잘못된 선택을 했을지라도 이전 선택으로 되돌아가지 않는다. 즉, 하향식 접근으로 동작한다.
각 단계에서 최적이라고 판단되는 선택을 하기 때문에 전체 문제에 대한 최적의 결과를 제공하지 않는다.

알고리즘 적용 조건

그리디 알고리즘을 사용하기 위해서는 크게 2가지 조건을 만족해야 한다.

1) Greedy Choice Property (탐욕스러운 선택 조건)

각 단계에서 최적의 선택만으로도 전체 문제의 최적 해결 방안을 도출할 수 있는 경우
이전 선택을 재검토 하지 않아도 문제가 해결될 수 있는 경우

즉, 현재의 선택이 이후 선택에 영향을 주지 않아야 한다.

2) Optimal Substructure (최적 부분 구조)

하위 문제의 해결이 전체 문제의 해결로 이어지는 구조인 경우

즉, 전체 문제의 해결 방안이 부분 문제의 최적 해결 방안이어야 한다.

위 조건이 성립하지 않는다면, 그리디 알고리즘으로 해결할 수 없다.

예제

1) 최장 경로 찾기

맨 위의 루트 노드로부터 리프 노드까자의 최장거리를 구하는 문제를 그리디 알고리즘으로 풀 경우.

루트 노드인 20에서 시작해 2와 3중 최적의 선택인 3을 선택하고 이후 유일한 경로인 1로 이동하여, 경로의 길이는 20 + 3 + 1인 24가 된다.

하지만 최적의 경로는 그림을 통해 알 수 있듯이 20 → 2 -> 10 = 32이다.

즉, 이 문제는 부분 문제의 해결이 전체 문제의 해결로 이어지지 않으므로, 그리디 알고리즘 적용 조건 중 두 번째 조건인 최적 부분 구조를 만족하지 못하기 때문에 그리디 알고리즘으로 풀 수 없다.

참조 : Programiz - Greedy Algorithm

2) 설탕 배달

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다.
상근이는 지금 사탕가게에 설탕을 정확히 N킬로그램을 배달해야 한다.
설탕공장에서 만드는 설탕은 봉지에 담겨져 있으며, 3kg과 5kg 봉지가 있다.

상근이는 귀찮기 때문에 최대한 적은 봉지를 들고 가려고 한다.
예를 들어, 설탕 18kg을 배달해야 할 때, 3kg 봉지 6개를 가져가도 되지만, 5kg 3개와 3kg 1개를 배달하면 총 4개로, 더 적은 봉지의 개수를 전달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 <= N <= 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 배달할 수 없다면 -1을 출력한다.

나의 풀이

const fs = require('fs');
const input = fs.readFileSync('dev/stdin').toString().trim();
let num = Number(input);

let count = 0;
while (num > 0) {
	if (num % 5 === 0) {
		num -= 5;
	} else {
		num -= 3;
	}
	count++;
}

const answer = num === 0 ? count : -1;
console.log(answer);