그리디 알고리즘 ( 탐욕 알고리즘)
말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.
탐욕 알고리즘으로 문제를 해결하는 방법은 다음과 같이 단계적으로 구분할 수 있다.
1. 선택 절차 (Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사 (Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사 (Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.
탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간 , 최적이라 생각되는 해답 (locally optimal solution)을 찾고, 이를 토대로 최종 문제의 해답 (globally optimal solution)에 도달하는 문제 해결방식이다. 그러나 항상 최적의 결과를 보장하지는 못한다는 점을 명심해야 한다.
따라서 두 가지의 조건을 만족하는 " 특정한 상황" 이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못한다.
탐욕 알고리즘을 적용하려면 해결하려는 문제가 2가지 조건을 성립하여야 한다.
- 탐욕적 선택 속성 (Greedy Choice Property) : 앞의 선택이 이후의 선택에 영햐을 주지 않는다.
- 최적 부분 구조 (Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
즉, 탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다.
그리디 알고리즘을 활용한 문제들을 살펴보자
편의점 알바
편의점 알바중, 하필 피크 시간대 손님에게 거스름돈으로 줄 동전이 부족하다는것을 알게 되었습니다.
현재 가지고 있는 동전은 1 원, 5원, 10원, 50원, 100원, 500원으로 오름차순으로 정렬되어 있고, 각 동전들은 서로 배수 관계에 있습니다.
동전 개수를 최소화하여 거스름 돈 K를 만들어야 합니다. 이때, 필요한 동전 개수의 최소값을 구하는 함수를 작성해 주세요.
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;
}
동전의 총 갯수를 저장하는 변수를 count로 두고 0으로 초기화 해준다음
arr 배열에 동전 단위를 큰 순서대로 정의해줍니다.
동전 단위에 대해 반복하는 for 문을 돌면서 현재 동전 단위로 몇 개의 동전을 만들 수 있는지 계산하여 count에 더합니다.
여기서 Math.floor(k/item)은 해당 동전 단위로 만들 수 있는 최대 갯수를 의미합니다.
k = k - item * Math.floor(k/item);은 남은 돈을 계산하여 k를 업데이트하고 이렇게 하면 이미 계산한 동전의 가치를 제외한 나머지 돈이 남게 됩니다. 반복문 모두 실행 후 최종적으로 함수는 계산된 동전의 총 갯수를 반환하게됩니다.
짐 나르기
김코딩과 박해커는 사무실 이사를 위해 짐을 미리 싸 둔 뒤, 짐을 넣을 박스를 사왔다. 박스를 사오고 보니 각 이사짐의 무게는 들쭉날쭉한 반면, 박스는 너무 작아서 한번에 최대 2개의 짐 밖에 넣을 수 없었고 무게 제한도 있었다.
예를 들어, 짐의 무게가 [70kg, 50kg, 80kg, 50kg] 이고 박스의 무게 제한이 100kg이라면 2번째 짐과 4번째 짐은 같이 넣을 수 있지만 1번째 짐과 3번째 짐의 무게의 합은 150kg이므로 박스의 무게 제한을 초과하여 같이 넣을 수 없다.
박스를 최대한 적게 사용하여 모든 짐을 옮기려고 합니다.
짐의 무게를 담은 배열 stuff와 박스의 무게 제한 limit가 매개변수로 주어질 때, 모든 짐을 옮기기 위해 필요한 박스 개수의 최소값을 return 하도록 movingStuff 함수를 작성하세요
function movingStuff(stuff, limit) {
let count = 0;
// 물건들을 무게순으로 정렬
let sortedStuff = stuff.sort((a, b) => a - b);
// 정렬된 물건들이 모두 옮겨질 때까지 반복
while (sortedStuff.length !== 0) {
// 가장 가벼운 물건과 가장 무거운 물건의 무게 합이 제한을 넘지 않는 경우
if (sortedStuff[0] + sortedStuff[sortedStuff.length - 1] <= limit) {
// 옮긴 횟수를 증가시키고, 가장 가벼운 물건과 가장 무거운 물건을 배열에서 제거
count++;
sortedStuff.shift();
sortedStuff.pop();
} else {
// 제한을 넘는 경우에는 가장 무거운 물건만 옮긴다
count++;
sortedStuff.pop();
}
}
return count;
}
