DP · 그리디 · 백트래킹 — 최적화 3기법

// ❌ 순수 재귀 — O(2^n), n=40에서 몇 분
function fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

// ✅ 탑다운 DP (메모이제이션)
function fibMemo(n, memo = {}) {
  if (n < 2) return n;
  if (memo[n]) return memo[n];
  return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}

// ✅ 바텀업 DP (반복문)
function fibBU(n) {
  if (n < 2) return n;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return b;
}
// O(n) 시간, O(1) 공간

// 구간 스케줄링 — 겹치지 않는 최대 구간 수
// 정렬 기준: "끝나는 시간 빠른 순" (그리디 선택)
function maxMeetings(meets) {
  meets.sort((a, b) => a.end - b.end);
  let lastEnd = -Infinity, count = 0;
  for (const m of meets) {
    if (m.start >= lastEnd) {
      count++;
      lastEnd = m.end;
    }
  }
  return count;
}
// 증명: 교환 논증 — 첫 선택을 바꿔도 답이 더 좋아지지 않음

// 모든 순열 찾기 — 백트래킹
function permutations(arr) {
  const result = [];
  function backtrack(path, used) {
    if (path.length === arr.length) {
      result.push([...path]);
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      if (used[i]) continue;
      path.push(arr[i]); used[i] = true;
      backtrack(path, used);
      path.pop();    used[i] = false;  // ← 되돌리기
    }
  }
  backtrack([], Array(arr.length).fill(false));
  return result;
}