그리디 알고리즘이란?

• 탐욕 알고리즘, 탐욕법이라고도 불린다. 각 단계에서 가장 최선의 선택을 하여 최적의 해를 구해내는 기법이 그리디 알고리즘이다.

• 순간마다 하는 선택은 그 순간에 대해서는 최선의 해답이겠지만, 최종적으로 모아 놓고 보았을 때 그 답이 최적이라는 경우라고는 보장할 수 없다.

• 보통 코딩테스트에서는 그리디 알고리즘과 dp 알고리즘 등을 혼용해서 사용하는 문제가 많고 sort는 세트라고 생각하면 된다고 들었다..

조건

• 그리디 알고리즘은 2가지 조건을 만족해야 한다.

1. 탐욕 선택 속성(Greedy Choice Property)
2. 최적 부분 구조(Optimal Substructure)

• 1번은 이전의 선택이 이후에 영향을 주지 않음을 의미하며, 2는 부분 문제의 최적 결과가 전체에도 그대로 적용될 수 있어야 한다.

예시1) 거스름돈

• 대표적인 문제의 예로 거스름돈 문제가 있다.

문제
돈의 종류: 1000원, 500원, 100원, 50원, 10원
계산할 돈: 3470원
낸 돈 : 10000원
이라고 가정할 때 거스름 돈을 최소의 돈의 개수로 주는 경우는 각각 몇 개씩 줘야 하는가?

let money = 10000; // 이라고 가정해보자

1. 1000원의 개수 -> Math.floor(money/1000);
   그리고 나머지로 money 초기화 -> money = money % 1000;
   == 6개

2. 500원의 개수 -> Math.floor(money/500);
   그리고 나머지로 money 초기화 -> money = money % 500;
   == 1개

3. 100원의 개수 -> Math.floor(money/100);
   그리고 나머지로 money 초기화 -> money = money % 100;
   ==0개

4. 50원의 개수 -> Math.floor(money/50);
   그리고 나머지로 money 초기화 -> money = money % 50;
   ==0개

5. 10원의 개수 -> Math.floor(money/10);
   그리고 나머지로 money 초기화 -> money = money % 10;
   ==3개

• 따라서 정답은 1000원: 6개, 500원: 1개, 10원: 3개 가 된다.

예시2) 프로그래머스(LV1) 체육복

• 문제 설명
  점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

https://school.programmers.co.kr/learn/courses/30/lessons/42862

function solution(n, lost, reserve) {  
    let setLost = lost.filter(v=> !reserve.includes(v));
    let setReserve = reserve.filter(v=> !lost.includes(v));
    
    //먼저 확실하게 들을 수 있는 친구들의 배열
    let possible = [];
    let borrow = [];
    
    for(let i=1; i<=n; i++){
        if(!setLost.includes(i)){
            possible.push(i);
        };
    }
    
    setLost.sort((a,b)=> b-a);
    setReserve.sort((a,b) => b-a);
    
    for(let i=0; i<setReserve.length; i++){
        for(let j=0; j<setLost.length; j++){
            if(setReserve[i]+1 == setLost[j] || setReserve[i]-1 == setLost[j]){
                borrow.push(setLost[j]);
                setLost.splice(j,1);
            }
        }
    }
    
    return possible.length + borrow.length;
}

풀이방법

1) 빌려줄 수 있는 학생들의 배열 reserve와 체육복을 잃어버린 학생들의 배열 lost의 중복값을 없애주었다. 왜? 겹치는 요소는 여벌을 잃어버린 것이기 때문에 빌려줄 수 때문이다. 사전에 미리 set을 해놓으면 시간복잡도도 줄어들 수 있다.

2) 확실하게 체육수업을 들을 수 있는 사람을 possible 배열에 추가해 놓았다.
3) 문제에 주어진 조건대로 정렬 및 연산을 하여 가장 최적의 해를 구해 체육복 빌리기를 성공한 사람들의 배열인 borrow에 추가해주었다.
4) 두 배열의 길이를 더해 리턴해주었다.