오늘의 알고리즘 👍

📝 1. 예산

• S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다.
• 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다.
• 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다.
• 물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다.
• 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다.
• 부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때,
• 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 solution 함수를 완성해주세요.

▷ 입출력 예

solution([1,3,2,5,4], 9) // 3
solution([2,2,3,3], 10)  // 4
solution([2,2,3,3], 1)  // 0
solution([1,2,3,4,5,6,7,8,9], 1)  // 1

▷ 내 풀이

function solution(d, budget) {
  d.sort((a, b) => (a > b ? 1 : -1));
  sum = 0;
  answer = d.length;
  count = 0;

  d[0] === budget ? count++ : -1;
  for (let i = 0; i < d.length; i++) {
    sum += d[i];
  }

  for (let i = 1; i < d.length; i++) {
    if (sum > budget) {
      sum -= d[d.length - i];
      answer--;
    }
  }
  if (d[0] >= budget) {
    return count;
  } else {
    return answer;
  }
}

▷ 수업풀이

function solution(d, budget) {
  let answer = 0;
  // 각각의 부서가 신청한 금액을 오름차순으로 정렬 (= 신청한 금액이 낮은 부서가 앞으로 정렬)
  d.sort((a, b) => (a > b ? 1 : -1));

  let sum = 0; // 부서들이 신청한 금액의 총 합산
  for (let i = 0; i < d.length; i++) {
    sum += d[i];

    // 부서에게 지급한 금액이 전체 예산을 넘어설 때
    if (sum > budget) return answer;
    answer++;
  }
  return answer;
}

▷ while문 사용 풀이

function solution(d, budget) {
  // 각각의 부서가 신청한 금액을 오름차순으로 정렬 (= 신청한 금액이 낮은 부서가 앞으로 정렬)
  d.sort((a, b) => (a > b ? 1 : -1));

  let idx = 0;
  while (budget - d[idx] >= 0) {
    budget -= d[idx];
    idx++;
  }
  return idx;
}

▷ filter 매서드 사용 풀이

function solution(d, budget) {
  // 각각의 부서가 신청한 금액을 오름차순으로 정렬 (= 신청한 금액이 낮은 부서가 앞으로 정렬)
  return d
    .sort((a, b) => (a > b ? 1 : -1))
    .filter((money) => {
      budget -= money;
      return budget >= 0;
    }).length;
}

📝 2. 피보나치 수

• 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
• 예를들어

F(2) = F(0) + F(1) = 0 + 1 = 1
F(3) = F(1) + F(2) = 1 + 1 = 2
F(4) = F(2) + F(3) = 1 + 2 = 3
F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

• 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

▷ 입출력 예

solution(3) // 2
solution(5) // 5

▷ 해결 못함 ❌

▷ 수업 풀이

0, 1, 1, 2, 3, 5, 8, 13, 21, ...
function solution(n) {
  // 피보나치 수의 결과를 저장하는 배열
  // 0번째 인덱스에는 0번째 피보나치의 결과
  // 1번째 인덱스에는 1번째 피보나치의 결과
  const answer = [0, 1];

  for (let i = 2; i <= n; i++) {
    answer[i] = (answer[i - 1] + answer[i - 2]) % 1234567; // Int의 범위가 있기 때문에 안쪽에서 나눠줘야 한다.
  }
  return answer[n];
}

❗ Int의 범위

12312313123123213123123123 // 1.2312313123123213e+25

Int는 범위가 있기 때문에 컴퓨터에서는 내가 입력한 대로 나오지 않는다.

• Int의 범위

2 ** 53 - 1;

• Int의 범위 확인 방법

Number.isSafeInteger(2 ** 53) // false
Number.isSafeInteger(2 ** 53 - 1) // true

▷ from, reduce 매서드 사용 풀이

0, 1, 1, 2, 3, 5, 8, 13, 21, ...
function solution(n) {
  let prev = 0; // 0번째 피보나치 수를 저장

  // return new Array(n).fill(1) // 이 기능을 하나의 매서드를 사용해서 변경
  return Array.from(new Array(n - 1), (_) => 1) // 1번째부터 시작했기 때문에 n - 1을 해줘야 한다.
    .reduce((acc) => {
      const sum = (acc + prev) % 1234567;
      prev = acc; // F(n - 2)에 F(n - 1)을 재할당

      return sum;
    }, 1); // 1번째 피보나치 수를 초기값으로 사용
}

출처: 프로그래머스
출처: 코드캠프