알고리즘

문제링크https://www.acmicpc.net/problem/7662문제풀이나는 이 문제를 풀기 위해 최대힙, 최소힙을 만들고 실제로 힙에 존재해야 할 숫자들을 Map 객체로 관리하였다.( Primary Queue 를 자바스크립트로 구현하기 위해선 직접 Class 객체를 만들어야 해서 어쩔 수 없이 코드가 길어진 점 이해 부탁드립니다. )  연산 과정은 이러하다.  - I 연산일 때는 최대 힙, 최소 힙에 숫자를 넣었고 - D 1 연산일 때는 최대힙에서 최대 숫자를 뽑고- D -1 연산일 때는 최소힙에서 최소 숫자를 뽑았다. - I 연산으로 숫자를 넣을 때는 map 객체에서 해당 숫자의 갯수를 +1- D 연산으로 숫자를 뺄 때는 map 객체에서 해당 숫자의 갯수를 -1  이런 과정을 거치면 힙에 들어..

문제링크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/5430문제풀이R 연산을 해야할 시 실제 배열을 앞뒤를 변경하게 계산속도 차원에서 효율적이지 못하다. 따라서 원본 배열의 원소의 순서를 뒤집기 보다는 앞에서 원소를 제거 or 뒤에서 원소를 제거 하는 방식으로 문제를 풀어야 시간초과 없이 문제를 풀 수 있다. 나는 direction 이라는 변수의 값을 기준으로 배열의 원소를 제거하는 방향을 파악하여 이를 진행하였다. 문제를 다 풀고나서 보니 풀이가 꽤나 긴거 같은데 추후 시간나면 줄여봐야겠다. ( 다른사람풀이 : https://tesseractjh.tistory.com/250 )let fs = require("fs");let input = fs.readFileSync("/dev/stdin")..

문제링크https://www.acmicpc.net/problem/9461문제풀이dp[i] = dp[i - 1] + dp[i - 5]; 라는 점화식만 도출하면 쉽게 풀 수 있는 문제이다.( i 번째 삼각형의 한변의 길이 =  i-1번째 변의 길이 + i-5번째 변의 길이 ) let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");const testCaseCount = Number(input.shift());input = input.map((n) => Number(n));let dp = [0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9]; // P(1) P(2) P(3) P(4) p(5..

문제링크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/11279 문제풀이자바스크립트로 풀게 된다면 힙(heap) 구조를 직접 class로 구현해서 풀어야 한다.힙 구조를 이용하면 계산횟수를 현저히 줄일 수 있다. 만약 힙구조에 대해 모른다면 이를 학습하고 이 문제를 풀기를 권한다.힙구조에 대해 이해하고 있기 때문에 문제없이 해당 문제를 풀 수 있었다. let fs = require("fs");let input = fs .readFileSync("/dev/stdin") .toString() .split("\n") .map((n) => Number(n));class MaxHeap { constructor() { this.heap = []; } pu..

문제링크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/10026 문제풀이적록색약이 아닌 사람이 보는 NxN Grid 2차원배열(map1 > R,G,B 모두 존재) 과  적록색약이 보는 NxN Grid 2차원배열(map2 > G,B만 존재 )  를 각각 만든뒤 두 2차원 배열을 탐색(bfs, dfs) 하면서 그룹핑하면 색상 영역의 수를 도출할 수 있다.   let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let N = Number(input.shift());let map1 = [];let map2 = [];let map1GroupCnt = 0;let map2GroupCnt =..

문제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/2805문제풀이문제조건을 보고 이분탐색이라는 느낌을 받았다. ( 아래조건 참고 )만약 이분탐색을 하지 않고 나무 높이를 하나씩 낮추면서 최댓값을 구하려면 괴랄한 연산횟수가 나온다. 하지만 이분탐색으로 탐색하면 계산횟수를 획기적으로 많이 줄일 수 있다. 이렇게 획기적으로 줄어드는 이유는 나무 높이의 범위가 너무 크기 때문이다. -> 이부분은 직접 케이스를 산정해서 테스트해보면 알 수 있다. ) let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [N, M] = input[0].split(" ").map((n) => Nu..