그리디(탐욕 알고리즘)에 대해

“매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자”

동전 거스름돈 문제를 예로 들어보자.
500원, 100원, 50원, 10원이 있을 때 가장 최소한의 동전의 개수로 돈을 거슬러줘야 한다. 1230원이라면 500원 2개, 100원 2개, 10원 3개가 될 것이다. 이게 왜 그리디이냐 하면

1. 1230원 - 500 * 2 = 230원 // 이제 230원인 상황에서 최적의 답을 구한다.
2. 230 - 100 * 2 = 30원 // 이제 30원인 상황에서 최적의 답을 구한다.
3. 30 - 10 * 3 = 0원 // 끝

한번의 선택이 다음 선택과 무관한 것이 특징이다.
만약 거스름돈 동전이 [500원, 400원, 100원] 이라면 어떨까?
800원의 거스름돈을 주기 위해서 그리디알고리즘을 사용한다면.
500원 _ 1개, 100원 _ 3개 = 4개의 동전이 필요하다.
그러나 이것은 정답이 아니다. 정답은 400원 * 2개다.
그래서 그리디알고리즘을 적용할 때는 부분의 해가 최적의 해가 되는가를 잘 따져봐야 한다.

체육복 문제

프로그래머스 문제 이 문제는 두단계로 나뉜다.
우선 lost와 reserve 배열에 중복을 제거한다. 본인이 체육복을 잃어버렸을 경우 다른사람한테 빌려줄 수 없기 때문이다. 그 후에 lost를 돌면서 체육복을 빌릴 수 있는지 없는지 판단한다. 1번 학생이 2번 학생의 체육복을 빌리든 다음 선택과 관련이 없다. 그래서 처음부터 배열을 돌면서 하나씩 생각하면 된다.

두 배열에서 중복을 제거할 때 filter를 사용하면 된다.

const lost = [2, 4, 5];
const reserve = [1, 2, 4];

const realLost = lost.filter(v => !reserve.includes(v));
const realReserve = reserve.filter(v => !lost.includes(v));

그 후에 lost를 훑으면서 reserve에서 받을 수 있는지 없는지 판단한다.

realLost.map(v => {
  if (realReserve.includes(v - 1)) {
    borrowCnt++;
    //이 부분은 filter 사용
    return realReserve.filter(r => !realReserve.indexOf(v - 1));
  }
  if (realReserve.includes(v + 1)) {
    borrowCnt++;
    //이 부분은 indexOf를 사용했다.
    return realReserve.splice(realReserve.indexOf(v + 1), 1);
  }
});
return n - (realLost.length - borrowCnt);

indexOf와 filter의 속도비교
결론 : filter를 사용하는게 좋다.