행복 유치원 ( 백준 13164)

문제 풀이 못떠올림, 접근 못함
K개의 조가 있어야 한다는 것 ⇒ K-1개 만큼의 조 구분이 필요하다
양 옆의 차이를 받아옴, 그리고 그 양 옆의 차이가 가장 큰 수 만큼 제거가 최소 비용

⇒ 양 옆의 차이를 배열로 만들고, 그 배열을 정렬해서 값을 구한다

const input = require("fs")
  .readFileSync("input.txt")
  .toString()
  .trim()
  .split("\n");
const [N, K] = input.shift().split(" ").map(Number);
const arr = input.shift().split(" ").map(Number);

const diff = [];
for (let i = 0; i < arr.length - 1; i++) {
  diff.push(arr[i + 1] - arr[i]);
}
const sorted_diff = diff
  .sort((a, b) => a - b)
  .slice(0, N - K)
  .reduce((acc, cur) => acc + cur, 0);
console.log(sorted_diff);

문제 풀이의 핵심은 K-1개의 조를 나누었을 때, 조 내부의 최소값을 구분할 필요가 없다는 것
양 옆의 값들을 전부다 계산이 될 수 밖에 없음. 그렇기에 차이값들의 배열 중 K-1개 까지의 값만 생각하면 된다.

reduce

[1, 2, 3, 4].reduce((acc, cur) => acc + cur, 0);
// acc => 누적합, cur => 현재 값, 콜백 => 누적합과의 현재값 계산, 추가 인자 => 시작 값

크루스칼 알고리즘 (= 최소비용 신장트리 계산 )

노드의 개수가 7개라면 간선의 개수는 6개가 되어진다.
간선의 비용 중 가장 작은 수 부터 순차적으로 찾아 올라가며, 사이클이 발생되어지지 않도록 계산하는 것이 핵심

⇒ 구현하기 위해서는 유니온 파인드의 이해가 필요

유니온 파인드 (합집합 찾기)

const getParent = (parent, x) => {
  if (parent[x] === x) return x;
  return (parent[x] = getParent(parent, parent[x]));
};

const union = (parent, a, b) => {
  let pA = getParent(parent, a);
  let pB = getParent(parent, b);
  if (pA > pB) parent[pA] = pB;
  else parent[pB] = pA;
};

const find = (parent, a, b) => {
  let pA = getParent(parent, a);
  let pB = getParent(parent, b);
  if (pA === pB) return 1;
  return 0;
};

const arr = [];
for (let i = 1; i <= 10; i++) {
  arr[i] = i;
}
union(arr, 1, 2);
console.log(find(arr, 1, 2));

각 노드에 대한 부모 배열을 만들고, 각 노드들은 자신이 속한 집합의 대표 노드 ( 가장 작은 값 )을 가리킴
초기에는 모든 노드가 자기 자신을 부모로 가지지만, union을 통해 최상위 부모를 찾아 하나로 연결
find를 통해서 같은 집합인지 (= 같은 루트 노드를 가지는지) 확인이 가능

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];
rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const [N, M] = input.shift().split(" ").map(Number);

  const getParent = (parent, idx) => {
    if (parent[idx] === idx) return idx;
    return (parent[idx] = getParent(parent, parent[idx]));
  };

  const unionParent = (parent, a, b) => {
    const pA = getParent(parent, a);
    const pB = getParent(parent, b);
    if (pA < pB) parent[pB] = pA;
    else parent[pA] = pB;
  };

  const findParent = (parent, a, b) => {
    const pA = getParent(parent, a);
    const pB = getParent(parent, b);
    return pA === pB ? "YES" : "NO";
  };

  const parent = Array.from({ length: N + 1 }, (_, idx) => idx);
  const answer = [];

  for (const line of input) {
    const [key, a, b] = line.split(" ").map(Number);
    if (key === 0) unionParent(parent, a, b);
    else answer.push(findParent(parent, a, b));
  }

  console.log(answer.join("\n"));
});

예제문제 ⇒ 백준1717번, 전형적인 unionFind 할 수 있어? 문제

이해와 구현이 어렵지 않은 알고리즘이니 챙겨가자.

MST ( Minimum Spanning Tree ) 최소 신장 트리

그래프에서 최소 비용으로 모든 구간을 연결한 트리
Tree 이기 때문에 Cycle이 존재하면 안되는 것이 핵심
정점의 개수가 N개 일 때, 간선의 개수는 N-1개

섬 연결하기

function getParent(parent, idx) {
  if (parent[idx] === idx) return idx;
  return (parent[idx] = getParent(parent, parent[idx]));
}
function unionParent(parent, idx1, idx2) {
  const p1 = getParent(parent, idx1);
  const p2 = getParent(parent, idx2);
  if (p1 < p2) parent[p2] = p1;
  else parent[p1] = p2;
}
function findParent(parent, idx1, idx2) {
  const p1 = getParent(parent, idx1);
  const p2 = getParent(parent, idx2);
  if (p1 === p2) return true;
  return false;
}
function solution(n, costs) {
  costs.sort((a, b) => a[2] - b[2]);
  const parent = Array.from({ length: n }, (_, i) => i);
  let total = 0;
  let count = 0;
  for (const [a, b, cost] of costs) {
    if (count === n - 1) break;
    if (getParent(parent, a) !== getParent(parent, b)) {
      unionParent(parent, a, b);
      total += cost;
      count++;
    }
  }
  return total;
}

크루스칼 예제 문제
간선 연결 최소 비용 구하기
가중치 값을 기준으로 정렬 후, Union-Find 자료구조를 이용해 간선 선택
섬을 이동하는데 드는 비용을 기준으로 정렬 후 UF 조건을 맞추면서 N-1까지의 값을 구함
간선에 드는 최소 비용을 고르면서도, 집합 (= 연결되지 않은 ) 것들만을 연결, Find면 버리기

단속 카메라

그리디 문제, 회의실 배정 문제와 동일

function solution(routes) {
  var answer = 1;
  const sortedRoutes = routes.sort((a, b) => a[1] - b[1]);
  let camera = sortedRoutes[0][1];
  for (let i = 1; i < sortedRoutes.length; i++) {
    const [start, end] = sortedRoutes[i];
    if (start > camera) {
      console.log(start, camera);
      answer++;
      camera = end;
    }
  }
  return answer;
}

풀이방법이 아예 동일해서 그냥 구현
차량이 나가는 시점 기준으로 정렬하는 방식으로 접근한다면 풀이가 어렵지 않음
나가는 시간순으로 정렬, 다음 값의 시작 지점이 기존 값의 끝나는 지점보다 더 낮은 경우, 그 지점의 끝나는 부분부터 값을 다시 잡기

머리 식히기 문제로 푼 백준 13987번 Six sides

const input = require("fs")
  .readFileSync("input.txt")
  .toString()
  .trim()
  .split("\n");
const arr1 = input.shift().split(" ").map(Number);
const arr2 = input.shift().split(" ").map(Number);
let cwin = 0;
let cdraw = 0;
for (let i = 0; i < arr1.length; i++) {
  for (let j = 0; j < arr2.length; j++) {
    if (arr1[i] > arr2[j]) cwin++;
    else if (arr1[i] === arr2[j]) cdraw++;
  }
}
console.log((cwin / (36 - cdraw)).toFixed(5));

구현은 간단한 주사위 승리 확률 추측
내가 원하는건 ⇒ 승리했을 때 확률, 무승부는 제외
그 말은 전체 경우의 수 중 무승부는 제외하고, 승리할 확률만 찾으면 됨.
뇌정지오면 이런거 꼭 못품; 주기적으로 문제를 풀어 익숙해지자