최단거리 & Trie

동전 바꿔주기

냅색 알고리즘
동전 갯수가 유한할때

let t = 20;
let coins = [
  [5, 3],
  [10, 2],
  [1, 5],
];

function solution(t, coins) {
  let answer = 0;
  let dy = Array(t + 1).fill(0);
  dy[0] = 1;
  for (let [p, n] of coins) {
    for (let j = t; j >= 1; j--) {
      for (let k = 1; k <= n; k++) {
        if (j - p * k < 0) break;
        dy[j] += dy[j - p * k];
      }
    }
  }
  console.log(dy);
  answer = dy[t];
  return answer;
}

플로이드 와샬

let n = 5;
let edges = [
  [1, 2, 6],
  [1, 3, 3],
  [3, 2, 2],
  [2, 4, 1],
  [2, 5, 13],
  [3, 4, 5],
  [4, 2, 3],
  [4, 5, 7],
];

function solution(n, edges) {
  let answer;
  let dist = Array.from({ length: n + 1 }, () => Array(n + 1).fill(1000));
  for (let i = 1; i <= n; i++) dist[i][i] = 0;
  for (let [a, b, c] of edges) {
    dist[a][b] = c;
  }
  for (let k = 1; k <= n; k++) {
    for (let i = 1; i <= n; i++) {
      for (let j = 1; j <= n; j++) {
        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
  return answer;
}

회장뽑기

플로이드 와샬 응용

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

function solution(n, edges) {
  let answer = [];
  let dist = Array.from({ length: n + 1 }, () => Array(n + 1).fill(1000));
  let score = Array.from({ length: n + 1 }, () => 0);
  for (let i = 1; i <= n; i++) dist[i][i] = 0;
  for (let [a, b] of edges) {
    dist[a][b] = 1;
    dist[b][a] = 1;
  }
  for (let k = 1; k <= n; k++) {
    for (let i = 1; i <= n; i++) {
      for (let j = 1; j <= n; j++) {
        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
  let PS = 1000;
  let cnt = 0;
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      if (i === j) continue;
      score[i] = Math.max(score[i], dist[i][j]);
    }
    PS = Math.min(PS, score[i]);
  }
  for (let i = 1; i <= n; i++) {
    if (score[i] === PS) {
      cnt++;
    }
  }
  answer.push(PS);
  answer.push(cnt);
  return answer;
}

Trie 자료구조

K사가 좋아한답니다

class Node {
  constructor() {
    this.end = false;
    this.child = {};
  }
}
class Trie {
  constructor() {
    this.root = new Node();
  }
  // cur은 어느 지점을 가르키는가를 의미(현재노드)
  insert(word) {
    let cur = this.root;
    for (let x of word) {
      // 없으면 Node할당
      if (cur.child[x] === undefined) {
        cur.child[x] = new Node();
      }
      cur = cur.child[x];
    }
    cur.end = true;
  }
  search(word) {
    let cur = this.root;
    for (let x of word) {
      if (cur.child[x] === undefined) return false;
      cur = cur.child[x];
    }
    return cur.end;
  }
  prefixS(str) {
    let cur = this.root;
    for (let x of str) {
      if (cur.child[x] === undefined) return false;
      cur = cur.child[x];
    }
    return true;
  }
}

자동완성

class Node {
  constructor() {
    this.end = false;
    // 카운팅 용
    this.cnt = 0;
    this.child = {};
  }
}
class Trie {
  constructor() {
    this.root = new Node();
  }
  insert(word) {
    let cur = this.root;
    for (let x of word) {
      if (cur.child[x] === undefined) {
        cur.child[x] = new Node();
      }
      cur = cur.child[x];
      cur.cnt++;
    }
    cur.end = true;
  }
  getCount(word) {
    let cur = this.root;
    let Count = 0;
    for (let x of word) {
      Count++;
      cur = cur.child[x];
      if (cur.cnt === 1) return Count;
    }
    return Count;
  }
}

let words = ["go", "gone", "guild"];

function solution(words) {
  let answer = 0;
  let trie = new Trie();
  for (let word of words) {
    trie.insert(word);
  }
  for (let word of words) {
    answer += trie.getCount(word);
  }
  return answer;
}