문제https://www.acmicpc.net/problem/1463 문제풀이dp로 접근하지 않으면 시간초과가 나는 문제였다. 문제풀이의 핵심은 아래 점화식이다. 여기서 dp[i] 는 i를 만들기 위해서 필요한 연산 횟수이다. ( dp[1]=0, dp[2]=1, dp[3]=1 이다 )   1 ) i가 3의배수이고 2의 배수일 때dp[i] = Math. ( dp[i/3] +1 , dp[i/2] +1 , dp[i-1] +1 )    2 ) i가 3의 배수이고 2의 배수가 아닐때dp[i] = Math. ( dp[i/3] +1 , dp[i-1] +1 )    3 ) i가 2의 배수이고 3의 배수가 아닐때dp[i] = Math. ( dp[i/2] +1 , dp[i-1] +1 )     let fs = requir..

문제https://www.acmicpc.net/problem/1541 문제풀이첫번째 for문에서 [ '+1' , '-2' , '-3' , '+2' , '+2' , '3' ] 와 같은 arr를 생성하고 두번째 for문에서 answer을 계산한다 핵심은 음수 이후에 연속적으로 양수가 나올 때 해당 양수는 결국 음수로 계산해야 최솟값을 구할 수 있다는 점이다.예시) 1-2+3+3 => 1-(2+3+3)  이런식으로 음수이후로 연속적으로 나타나는 양수는 모두 음수처리 후 모든 수들을 합하면 최솟값을 구할 수 있다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim();let num = "";let numArr = [];..

문제https://www.acmicpc.net/problem/17219 문제풀이주소에 중복이 없다고 하길래 Set 객체를 안쓰고 그냥 Object를 활용해서 문제를 풀었다. 아주 기본적인 문제이다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [N, M] = input .shift() .split(" ") .map((n) => parseInt(n));let obj = {};for (let i = 0; i

문제https://www.acmicpc.net/problem/12865 풀이let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [N, K] = input[0].split(" ").map((num) => Number(num));let arr = [];for (let i = 1; i Number(num)));}let dp = Array.from({ length: N + 1 }, () => { return Array(K + 1).fill(0);});for (let row = 1; row = weight) { dp[row][col] = Math.max(dp[ro..

문제https://www.acmicpc.net/problem/15654 풀이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 num_arr = input[0].split(" ").map((n) => Number(n));// 정렬num_arr.sort((a, b) => a - b);let dfs = (arr, picked) => { if (arr.length === M) { console.log(arr.join(" ")); ..

문제https://www.acmicpc.net/problem/15652 풀이dfs 이용해서 풀 수 있었다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim();let [N, M] = input.split(" ").map((n) => Number(n));const dfs = (start, arr) => { if (arr.length === M) { console.log(String(arr.join(" "))); return; } for (let i = start; i

문제https://www.acmicpc.net/problem/9251내풀이LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.이 문제는 유명한 문제라고 하는데 처음에 어떻게 접근할 지 몰라 다른사람들의 풀이를 참고하였다.간단하게 ACAYKPCAPCAK두문자의 LCS를 찾으려면 아래와 같은 2 차원 배열을 만들고 채워서 가장 큰 수를 확인하면 된다.       A  C  A  Y  K  P     C   A   P   C   A  K    이렇게 2차원 배열을 만들고 채우면 된다. 위 2차원배열을 dp라고 칭하면 dp[0][3] 은 문자열 C와 문자열 ACAY 의 LCS길이로 채워진다...

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