트리 & 이분검색(결정알고리즘)

친구인가?

Disjoint-Set : Union & Find

let n = 9;
let nums = [
  [1, 2],
  [2, 3],
  [3, 4],
  [1, 5],
  [6, 7],
  [7, 8],
  [8, 9],
];
let s1 = 1;
let s2 = 5;

function solution(n, nums, s1, s2) {
  let unf = Array.from({ length: n + 1 }, (v, i) => i);

  function Find(v) {
    if (v === unf[v]) return v;
    else return (unf[v] = Find(unf[v]));
  }

  function Union(a, b) {
    let fa = Find(a);
    let fb = Find(b);
    if (fa !== fb) unf[fa] = fb;
  }

  for (let [a, b] of nums) {
    Union(a, b);
    console.log(unf);
  }
  if (Find(s1) !== Find(s2)) return "NO";
}

원더랜드

최소스패닝트리 : 크루스칼, Union & Find 활용

let n = 9;
let edges = [
  [1, 2, 12],
  [1, 9, 25],
  [2, 3, 10],
  [2, 8, 17],
  [2, 9, 8],
  [3, 4, 18],
  [3, 7, 55],
  [4, 5, 44],
  [5, 6, 60],
  [5, 7, 38],
  [7, 8, 35],
  [8, 9, 15],
];

function solution(n, edges) {
  let answer = 0;
  let unf = Array.from({ length: n + 1 }, (v, i) => i);

  function Find(v) {
    if (v === unf[v]) return v;
    else return (unf[v] = Find(unf[v]));
  }

  function Union(a, b) {
    let fa = Find(a);
    let fb = Find(b);
    if (fa !== fb) unf[fa] = fb;
  }
  edges.sort(([, , a], [, , b]) => a - b);

  for (let [a, b, c] of edges) {
    let fa = Find(a);
    let fb = Find(b);
    if (fa !== fb) {
      answer += c;
      unf[fa] = fb;
    }
  }
  return answer;
}

이분검색

let nums = [23, 87, 65, 12, 57, 32, 99, 81];
let m = 32;

function solution(nums, m) {
  nums.sort((a, b) => a - b);
  let answer;
  let lt = 0;
  let rt = nums.length;
  while (lt <= rt) {
    let mid = parseInt((lt + rt) / 2);
    if (nums[mid] === m) {
      answer = mid + 1;
      break;
    } else if (nums[mid] > m) rt = mid - 1;
    else lt = mid + 1;
  }
  return answer;
}

이차원배열 이분검색

let matrix = [
  [14, 7, 10, 3],
  [12, 6, 9, 1],
  [5, 8, 13, 17],
  [15, 18, 20, 23],
];
let target = 8;

function solution(matrix, target) {
  matrix.sort(
    (a, b) => a.sort((x, y) => x - y)[0] - b.sort((x, y) => x - y)[0]
  );
  let row = 0;
  let col = matrix[0].length - 1;
  while (row < matrix.length && col >= 0) {
    if (matrix[row][col] === target) return [row, col];
    if (target < matrix[row][col]) col--;
    else row++;
  }
  return;
}

랜선 자르기

결정 알고리즘

function solution2(nums, n) {
  let answer = 0;
  let lt = 1;
  let rt = Math.max(...nums);

  function count(len) {
    let cnt = 0;
    for (let x of nums) {
      cnt += Math.floor(x / len);
    }
    return cnt;
  }

  while (lt <= rt) {
    let mid = parseInt((lt + rt) / 2);
    if (count(mid) >= n) {
      answer = mid;
      lt = mid + 1;
    } else {
      rt = mid - 1;
    }
  }
  return answer;
}

뮤직 비디오

let nums = [1, 2, 3, 4, 5, 6, 7, 8, 9];
let m = 3;

function solution(nums, m) {
  let answer = 0;
  let lt = Math.max(...nums);
  let rt = nums.reduce((a, b) => a + b);

  function count(songs, capacity) {
    let cnt = 1,
      sum = 0;
    for (let x of songs) {
      if (sum + x > capacity) {
        cnt++;
        sum = x;
      } else {
        sum += x;
      }
    }
    return cnt;
  }

  while (lt <= rt) {
    let mid = parseInt((lt + rt) / 2);
    if (count(nums, mid) <= m) {
      answer = mid;
      rt = mid - 1;
    } else {
      lt = mid + 1;
    }
  }
  return answer;
}

마구간 정하기

결정 알고리즘

let nums = [1, 2, 8, 4, 9];
let c = 3;

function count(stables, dist) {
  let cnt = 1,
    ep = stables[0];
  for (let i = 1; i < stables.length; i++) {
    if (stables[i] - ep >= dist) {
      cnt++;
      ep = stables[i];
    }
  }
  return cnt;
}

function solution(nums, c) {
  let answer;
  nums.sort((a, b) => a - b);

  let lt = 1;
  let rt = nums[nums.length - 1];
  while (lt <= rt) {
    let mid = parseInt((lt + rt) / 2);
    if (count(nums, mid) >= c) {
      answer = mid;
      lt = mid + 1;
    } else {
      rt = mid - 1;
    }
  }
  return answer;
}

제품 이동

let n = 5;
let edges = [
  [1, 2, 5],
  [1, 3, 3],
  [1, 4, 2],
  [2, 4, 2],
  [3, 4, 4],
  [4, 5, 3],
];
let s = 1;
let e = 5;

function solution(n, edges, s, e) {
  let answer = 0,
    lt = 1,
    rt = 0;
  let graph = Array.from(Array(n + 1), () => Array());

  for (let [a, b, c] of edges) {
    graph[a].push([b, c]);
    graph[b].push([a, c]);
    rt = Math.max(rt, c);
  }

  function BFS(w) {
    let ch = Array.from({ length: n + 1 }, () => 0);
    let que = [];
    ch[s] = 1;
    que.push(s);
    while (que.length) {
      let a = que.shift();
      for (let [b, c] of graph[a]) {
        if (c >= w && ch[b] === 0) {
          ch[b] = 1;
          que.push(b);
        }
      }
    }
    return ch[e];
  }

  while (lt <= rt) {
    let mid = parseInt((lt + rt) / 2);
    if (BFS(mid)) {
      answer = mid;
      lt = mid + 1;
    } else {
      rt = mid - 1;
    }
  }
  return answer;
}