약수 구하기

const getDivisors = (num) => {
    const divisors = [];
    
    for(let i = 1 ; i <= num / 2; i++){
        if (num % i === 0) divisors.push(i);
    }
    
    return divisors;
}

최대공약수 공식

function gcd(...arr: [number, number]) {
    let [a, b] = arr.sort((a, b) => b - a);
    
    while(b !== 0) {
        const r = a % b;
        a = b;
        b = r;
    }

    return a;
}

console.log(gcd(12, 18));

최소공배수(최대 공약수 활용)

function lcm(a: number, b: number) {
    return (a / gcd(a, b)) * b;
}

console.log(lcm(12, 18));

2stack queue(dequeue 성능 좋음)

class TwoStackQueue {
  constructor() {
    this.inStack  = [];
    this.outStack = [];
  }

  enqueue(x) {
    this.inStack.push(x);
  }

  // 필요할 때만 호출
  _transfer() {
    while (this.inStack.length) {
      this.outStack.push(this.inStack.pop());
    }
  }

  dequeue() {
    if (!this.outStack.length) this._transfer();
    this.outStack.pop();
  }

  front() {
    if (!this.outStack.length) this._transfer();
    console.log(this.outStack[this.outStack.length - 1]);
  }
}

BFS 템플릿

function bfs(start, graph) {
  const visited = new Set();
  const queue = [start];
  
  visited.add(start);

  const order = [];

  while (queue.length) {
    const node = queue.shift();
    order.push(node);

    for (const next of graph[node]) {
      if (!visited.has(next)) {
        visited.add(next);
        queue.push(next);
      }
    }
  }

  return order;
}

DFS 템플릿

function dfsIterative(start) {
  const visited = new Set();
  const stack = [start];

  while (stack.length > 0) {
    const node = stack.pop();

    if (visited.has(node)) continue;
    visited.add(node);
    console.log(node);

    // 스택은 뒤에서 꺼내니까, 순서를 맞추고 싶으면 역순으로 push
    const neighbors = graph[node];
    for (let i = neighbors.length - 1; i >= 0; i--) {
      const next = neighbors[i];
      if (!visited.has(next)) {
        stack.push(next);
      }
    }
  }
}

dfsIterative('A');