그리디

문제링크https://www.acmicpc.net/problem/1931 문제풀이이 문제는 정렬 기준을 확립하는게 핵심이다. 최대한의 많은 강의를 듣기 위해서는1. 강의의 끝나는 시간이 빠른 것 부터 오름차순2. 강의 끝나는 시간이 같을 때는 강의 시간이 가장늦은 것 부터 내림차순 but 시작하는 시간 = 끝나는 시간 일때는 뒤에 배치 해야한다. 위 조건대로 배열을 정렬할 시 최대 강의를 진행할 수 있다. 처음에는 확 와닿지 않겠지만 스스로 몇개의 케이스를 만들고 진행하다 보면 왜 위 조건으로 정렬하는지 바로 이해 할 수 있다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [..

문제링크https://www.acmicpc.net/problem/11399문제풀이각각의 사람이 ATM에서 돈을 빼는데 걸리는 시간의 총합이 최소가 되려면 인출하는 시간이 가장 짧은 사람일수록 앞 순서에 줄을 서야 된다. let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let N = Number(input[0]);let arr = input[1].split(" ").map((n) => Number(n));arr.sort((a, b) => { return a - b;});let dp = Array(N).fill(0);dp[0] = arr[0];for (let i = 1; i { ..

문제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/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/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/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/1092 해설큰 문제 없이 해결 가능했다. const fs = require("fs");const input = fs.readFileSync("/dev/stdin").toString().split("\n");const craneCnt = Number(input[0]);const craneArr = input[1].split(" ").map((n) => Number(n));craneArr.sort((a, b) => b - a);const boxCnt = Number(input[2]);const boxArr = input[3].split(" ").map((n) => Number(n));boxArr.sort((a, b) => b - a);if ..