필수 알고리즘 암기(자바스크립트)

1.이분 탐색

백준: 1920번

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

let fs = require('fs');

let filePath = process.platform === 'linux' ? '/dev/stdin': './input.txt'

let input = fs.readFileSync(filePath).toString().split('\n');

const [N,A,M,B] = input.map(el => el.split(' ').map(Number));

A.sort((a,b)=>a-b);

function solution(list,target,left,mid,right){

  mid = Math.floor((left+right)/2);

  if(left > right) return list[mid]===target?1:0;

 

  if(list[mid] > target) right = mid - 1;

  else if(list[mid] === target) return list[mid]===target?1:0;

  else left = mid + 1;

  return solution(list,target,left,mid,right);

}

const result = B.map(el => solution(A,el,0,0,A.length-1));

console.log(result.join('\n'));

 

2.DFS(깊이 탐색)

백준: 2606번

https://www.acmicpc.net/problem/2606

2606번: 바이러스

(1)DFS

let fs = require('fs');

let filePath = process.platform === 'linux' ? '/dev/stdin': './input.txt'

let input = fs.readFileSync(filePath).toString().split('\n');

let node = Number(input.shift());

let edge = Number(input.shift());

let graph = [...new Array(node + 1)].map(e => []);

for(let i = 0 ; i < edge; i++){

  let [from, to] = input[i].split(' ').map(Number);

  graph[from].push(to);

  graph[to].push(from);

}

const dfs = (graph, start) => {

  const checked = [];

  let willCheck = [];

  willCheck.push(start);

  while(willCheck.length !==0){

    const node = willCheck.pop();

    if(!checked.includes(node)){

      checked.push(node);

      willCheck.push(...graph[node].reverse());

    }

  }

  return checked;

};

console.log(dfs(graph, 1).length - 1);

 

(2)BFS

let fs = require('fs');

let filePath = process.platform === 'linux' ? '/dev/stdin': './input.txt'

let input = fs.readFileSync(filePath).toString().split('\n');

let node = Number(input.shift());

let edge = Number(input.shift());

let graph = [...new Array(node + 1)].map(e => []);

for(let i = 0 ; i < edge; i++){

  let [from, to] = input[i].split(' ').map(Number);

  graph[from].push(to);

  graph[to].push(from);

}

const bfs = (graph, start) => {

  const checked = [];

  let willCheck = [];

  willCheck.push(start);

  while(willCheck.length !==0){

    const node = willCheck.shift();

    if(!checked.includes(node)){

      checked.push(node);

      willCheck.push(...graph[node]);

    }

  }

  return checked;

};

console.log(bfs(graph, 1).length - 1);

 

 

3.투포인터