알고리즘

문제링크https://www.acmicpc.net/problem/16953풀이최소 연산 횟수를 구하는 작업이기 때문에 dfs 보단 bfs로 푸는게 더 좋은 방법이다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString();let [start, target] = input.split(" ").map((n) => Number(n));let arr = [[start, 1]];let answer = undefined;while (arr.length) { let [num, cnt] = arr.shift(); if (num === target) { answer = cnt; break; } l..

문제https://www.acmicpc.net/problem/9095 풀이dp로 푼 문제풀이이다. 이 풀이가 최적화된 풀이이고 밑에 보면 dfs로도 푼 문제가 있다. let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");input = input.map((n) => Number(n));for (let i = 1; i   처음에 dfs로 접근했는데 그럴 필요가 없었다. 참고차 남겨둔다. let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");input = input.map((n) ..

문제링크https://www.acmicpc.net/problem/15650 풀이-1let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString();const [N, M] = input.split(" ").map((n) => parseInt(n));if (N === M) { answer = ""; for (let i = 1; i { if (rest === 0) { answer = answer + `${arr.join(" ")}\n`; } else { for (let i = start; i  풀이-2같은 문제를 다른 방식으로도 풀어봤다.let fs = requi..

문제https://www.acmicpc.net/problem/1966 풀이배열자체를 변형시키기 보단 바라보는 idx를 증가시키면서 배열을 순회했다. 어려움 없이 풀 수 있었다.const fs = require("fs");const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [caseCnt, ...caseArr] = input;caseCnt = +caseCnt;for (let i = 0; i Number(num)); let max = Math.max(...arr); let answer = 1; let idx = 0; while (1) { if (arr[idx] !== -1 && arr[..

문제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/1916 풀이처음에 dfs로 접근해서 풀었는데 시간초과로 틀려서 dp를 이용했다. 일단 map이라는 2차원 배열을 구현한다. 이 2차원 배열의 map[ i ][ j ] 는 i도시에서 j 도시로 갈 시 가장 가격이 싼 버스 요금을 나타 낸다. 만약 map[ i ][ j ] = Infinity 이면 해당 루트는 버스가 다니지 않는다고 생각하면 된다.  그리고 dp라는 2차원 배열을 구현한다. dp[ i ][ j ] 는 i 도시에서 j 도시로 가는 루트는 가장 버스요금이 싼 루트의 요금을 나타낸다.우리는 모든 경로를 탐색하면서 2차원 배열 dp를 완성시키고 최종적으로 dp[출발점][도착점] => 최소비용 을 구하면 된다.  const fs = req..

문제링크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/9465 풀이처음에는 dp(다이나믹 프로그래밍) 을 생각하지 못하여 고전했다.여기서 map은 스티커들의 배열을 의미하고 dp[0][i] 는 첫번째줄의 i+1번째 스티커 사용했을 때 가질 수 있는 최대 총점dp[1][i] 는 두번째줄의 i+1번째 스티커를 사용했을 가질 수 있는 최대 총점dp[2][i] 는 i+1번째의 스티커 어느것도 사용하지 않았을 때 가질 수 있는 최대 총점 이다.  dp[0][0] dp[1][0] dp[2][0] 부터 마지막 열까지 진행하면 나올 수 있는 최대 점수들을(dp[0][n-1], dp[1][n-1], dp[2][n-1]) 구할 수 있고 dp[0][n-1], dp[1][n-1], dp[2][n-1] 값중 최댓 값..

문제링크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