➕문제링크https://www.acmicpc.net/problem/1697🔨문제풀이bfs를 이용하돼 불필요한 연산은 처리하지 않는 방향으로 최적화 하였다. ( dp[ i ] 는 i지점을 가는 데 걸리는 최소시간 )let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim();let [N, K] = input.split(" ").map((n) => Number(n));let dp = Array(100001).fill(Infinity);let endPoint = 100000;let index = N;let answer = undefined;dp[N] = 0;let queue = [[N, 0]];while (queue.le..

문제링크https://www.acmicpc.net/problem/1446문제풀이DP로 연산횟수를 최적화하여 풀 수 있다. dp[1]은 1의 거리를 갔을 때 최소거리를 의미하며 순서대로 dp[1], dp[2], dp[3] ... 채워가면서 마지막에 dp[D]를 구할 수 있다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [N, D] = input .shift() .split(" ") .map((n) => Number(n));let dp = Array(D + 1).fill(0);let shortcut = input.map((str) => { return st..

문제링크https://www.acmicpc.net/problem/11403풀이문제를 풀긴 풀었는데 플로이드 와샬의 점화식을 이용하진 않았다. 해당 점화식을 이용해서 풀면 더 짧은 코드로 작성이 가능하다. 나는 하나의 점을 방문하면서 기존 graph를 갱신하는 방향으로 문제를 풀고 이미 방문한 점은 다시 방문하지 않는 방식으로 계산을 최적화 하였다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [pointsCnt, ...arr] = input;let graph = arr.map((str) => { return str.split(" ").map((n) => Number(n)..

문제링크https://www.acmicpc.net/problem/14940 문제풀이너비우선탐색으로 시작점으로 부터 동서남북으로 탐색하면서 최단거리를 갱신하였다. 무리없이 풀 수 있었다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [N, M] = input .shift() .split(" ") .map((n) => Number(n));let s_row = undefined, s_column = undefined;let map = [];for (let i = 0; i Number(n)); line.forEach((v, column) => { ..

문제https://www.acmicpc.net/problem/2667 풀이일단 지도를 2차원배열 형태로 변환시켰고 이를 이용해서 단지별로 아파트를 묶었다. dfs를 이용해서 특정 아파트에서 갈수 있는 모든 아파트를 하나의 단지로 묶었고 그 과정에서 단지내의 아파트의 갯수를 확인했다.그렇게 apartment 라는 array에 단지내의 아파트 갯수를 push 한뒤 다시 아파트갯수를 오름차순으로 정렬하여 문제의 답을 구할 수 있었다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let N = Number(input.shift());// 지도 2차원 배열로 저장let map = [];// ..

문제https://www.acmicpc.net/problem/1629 풀이js에서 BigInt를 많이 다뤄보지 않아서 굉장히 생소해서 많이 버벅 거렸다.BigInt는 2^53-1를 js 내에서 다룰 수 있는 내장객체이다. 이 문제를 풀기 위해서는 해당 객체를 이용해야 한다. 왜냐하면 주어진 A,B,C 의 범위가 2,147,483,647 이하이기 때문에 2,147,483,647의 제곱승만 되도 이미 BigInt를 다뤄야 한다.  이 문제를 풀기위해서 핵심은 다음과 같다 1. (A * B) % C  =  ((A%C) * (B%C))%C 이다-> 자바스크립트에서 큰숫자의 연산보단 작은숫자의 연산 속도가 훨씬 빠르기 때문에 이를 이용하여 나머지들을 곱하는게 속도차원에서 좋다 2. 2^10 을 구하기 위해 2를 ..

문제링크https://www.acmicpc.net/problem/11660 문제풀이이 문제는 언뜻보면 쉬어보인다. 하지만 단순하게 풀면 연산횟수가 너무 많아 시간초과가 난다. 연산횟수를 확인히 줄이기 위해 dp(동적계획법-dynamic programming)를 이용해야 한다. dp를 생각하는 순간 문제는 쉬어진다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [tableInfo, ...arr] = input;let [N, M] = tableInfo.split(" ").map((num) => Number(num));let table = [];for (let i = 0; i N..

문제링크https://www.acmicpc.net/problem/1149 풀이처음에는 가장 작은 수를 더하는 방식으로 하여 최솟값을 구하려고 생각했는데 아래와 같은 케이스를 생각해보니 그렇게 접근하면 안될 것 같다는 생각이 들었다. 31 2 34 5 6100 100 1200 200 1 결국 모든 경우의 수를 탐색하기 위해선 아래와 같이 코드를 작성해야 한다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let dp = Array.from({ length: input.length - 1 }, () => { return Array(3).fill(0);});let map = [];f..

문제링크https://www.acmicpc.net/problem/1141 문제풀이문자들을 비교하면서 문자가 긴 단어일 수록 다른 단어의 접두어가 될 확율이 떨어진다. 이를 고려하여 두 단어중 하나의 단어가 다른 단어의 접두어가 될 때 두 문자중 이왕이면 긴 문자를 집합에 포함함으로 써 최대한 많은 단어를 집합에 포함시킬 수 있다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().split("\n");let dic = [];for (let i = 1; i

문제링크https://www.acmicpc.net/problem/1105 풀이주어진 예시로는 풀기 힘들어서 테스트 케이스를 계속 찾아내며 문제를 풀수 있었다.8888, 88908860, 900088800, 89000요 정도의 추가 케이스를 설정해서 해당 문제를 풀 수 있었다.  let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString();const [L, R] = input.split(" ").map((n) => parseInt(n));let lArr = String(L) .split("") .map((n) => Number(n));let count = 0;for (let i = lArr.length - 1; i >= ..