Algorithm

문제링크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/1181 문제풀이set 객체를 통해 중복된 문자열을 제거하고sort()로 알파벳 순서대로 문자를 배열 한 뒤다시 글자 길이를 비교하여 정렬하였다.딱딱히 어려움 없이 풀 수 있었다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [n, ...words] = input;let set = new Set();words.forEach((word) => { set.add(word);});let arr = [...set];arr.sort();arr.sort((a, b) => { if (a.length !== b.le..

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

문제링크https://www.acmicpc.net/problem/1063 풀이const fs = require("fs");const input = fs.readFileSync("/dev/stdin").toString().split("\n");const obj = { A: 0, B: 1, C: 2, D: 3, E: 4, F: 5, G: 6, H: 7, 0: "A", 1: "B", 2: "C", 3: "D", 4: "E", 5: "F", 6: "G", 7: "H",};const move = (r, c, direction) => { switch (direction) { case "R": ..

문제링크https://www.acmicpc.net/problem/1449 제출코드어려움 없이 풀 수 있었다.const fs = require("fs");const input = fs.readFileSync("/dev/stdin").toString().split("\n");let [n, l] = input[0].split(" ").map((n) => Number(n));let positionArr = input[1].split(" ").map((n) => Number(n));positionArr.sort((a, b) => a - b);let count = 0;for (let i = 0; i = positionArr[idx] + 0.5) { ++i; ++idx; } ++i..

링크https://www.acmicpc.net/problem/11501 문제풀이1. 메모리 초과로 실패한 코드-> 굳이 새로운 배열(refArr) 을 만들고 2번의 순회를 할 필요가 없었다.const fs = require("fs");const input = fs .readFileSync("/dev/stdin") .toString() .split("\n") .map((str) => { return str.split(" ").map((n) => Number(n)); }); for (let i = 1; i 1) { let benefit = 0; let prices = input[i]; let max = 0; le..

문제링크https://www.acmicpc.net/problem/11000 제출코드 일단 수업들을 시작시간이 빠른순으로 정렬하고 시작시간이 같으면 끝나는 시간이 빠른시간 순으로 정렬하였다.그리고 정렬한 수업들을 순회하면서 최소 힙과 비교하면서(힙을 안쓰고 정렬을 이용하면 연산횟수가 기하급수적으로 많아서 시간초과가 발생한다.) 비어있는 강의실이 없는 경우 힙에 새롭게 추가하였다. 여기서 추가할 때 수업의 끝나는 시간만 힙에 추가했다. ( 우리가 필요한 정보는 수업이 끝나는 시간이기 때문이다. )마지막에 힙의 사이즈를 통해 몇개의 강의실이 쓰였는 지 알 수 있다.참고) 자바스크립트에서는 힙 자료구조를 직접 구현해야 한다.class MinHeap { constructor() { this.he..