[JS]MaxHeap

class maxHeap{ constructor(){ this.heap = [null]; } size() { return this.heap.length - 1; } swap(a,b) { [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]]; } add(value) { this.heap.push(value); let cur = this.heap.length - 1; // 제일 나중 노드에 새로 들어온 원소를 추가한다. let parent = Math.floor(cur / 2); while(cur > 1 && this.heap[parent] < this.heap[cur]) { // 부모노드의 원소가 더 작으면 현재노드의 원소와 바꿔준다. this.swap..

→2022.02.23

Algorithm/BaeKJoon

[JS][백준]1966_프린터 큐

문제 번호 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 알고리즘 분류 구현 자료 구조 시뮬레이션 큐 문제 풀이 C++에는 STL을 활용해서 Queue와 Dequeue등을 손쉽게 사용할 수 있다. 근데? JS에는 그런거없다. 그래서 직접 만들어서 사용해야한다. 우선 queue안에 들어갈 내용물인 node를 만들어준다. class node { constructor(no, pri) { // 문서 번호와 우선순위. this.no = no; this.pri = pri; this.next = null; } } 문제에서 ..

→2022.02.01

Algorithm/BaeKJoon

[JS][백준]12865_평범한 배낭

문제 번호 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 배낭 문제 문제 풀이 DP에서 유명한 배낭문제다. 처음풀었을땐 설명을 봐도 이해하기가 너무 어려웠다. DP문제이니만큼 이전에 계산했던 값들을 계속 사용하면서 문제를 풀 수 있다. DP라는 2차원 배열을 이용할건데 이때 2차원 배열의 내용은 value, 즉 '가치'가 된다. 세로축은 물건의 갯수, 가로축은 무게로 생각한다. 물건들 | 배낭 한계 0 1 2 ..

→2022.01.19

Algorithm/BaeKJoon

[JS][백준]10844_쉬운 계단 수

문제 번호 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 문제 풀이 길이가 N인 계단수를 만드는 방법을 생각해본다. 길이가 3인 계단수 123 이 있다고 생각해보자. 이때 가장오른쪽에 있는 3뒤에 2나 4를 붙이면 1232 혹은 1234 라는 길이가 4인 계단수를 만들 수 있다. 즉 길이가 N-1인 계단수의 뒤에 숫자를 추가해서 길이가 N인 계단수를 만들 수 있다는 말이다. 이를 위해서 2차원 배열을 사용하기로 하였다. let dp = new Array(101).fill(null).map(_ => new Array(10).fill(0)); 대략 이렇게 생긴 2차원 배열을 만들 수 있다. 문..

→2022.01.17

Algorithm/BaeKJoon

[JS][백준]3009_네 번째 점 (XOR)

문제 번호 3009번: 네 번째 점 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. www.acmicpc.net 알고리즘 분류 구현 기하학 문제 풀이 하나의 점을 구하기 위한 3개의 점이 주어진다. 우리는 x좌표중에 혼자 다른애, y좌표중에 혼자 다른애를 찾아서 답으로 출력하면된다. 예를 들어 30 20 10 10 10 20 가 입력으로 주어진다고 할때, x좌표중에 혼자 다른애는 30이고, y좌표중에 혼자 다른애는 10 이다. 그러므로 정답으로 30 10을 출력하면된다. 이 문제를 처음 풀때는 입력받은 숫자들을 일일히 비교해서 다른애를 찾아서 풀었던것 같다. 근데 여기서 XOR을 사용하면 좀더 현명하게 풀 수 있다. XOR은 비교하려는 두개의..

→2022.01.03

Algorithm/BaeKJoon

[JS][백준]4948_베르트랑 공준

문제 번호 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 알고리즘 분류 수학 정수론 소수 판정 에라토스테네스의 체 문제 풀이 주어진 숫자(n)를 입력받아서 n+1 이상 2*n 이하의 소수의 개수를 구하면된다. n에 대한 소수여부를 판단할때 2이상 루트n 이하 로 나눠보면 판단할 수 있다. 전체코드 const input = require('fs').readFileSync('dev/stdin').toString().split('\n'); let TC = 0; function sol() { let answ..

→2022.01.03

Algorithm/BaeKJoon

[JS][백준]9020_골드바흐의 추측

문제 번호 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 알고리즘 분류 수학 정수론 소수 판정 에라토스테네스의 체 문제 풀이 짝수를 두개의 소수로 나타내는 문제이다. 문제에서 주어진 입력의 범위가 10000 이하 이기때문에 prime 이라는 배열을 만들어서 10000 이하의 소수들을 모두 저장해주었다. 에라토스테네스의 체 만드는거랑 같다고 생각한다. function makePrime() { for (let i = 2; i n) break; if (sum + prime[j] === n) {..

→2022.01.03

Algorithm/BaeKJoon

[JS][백준]1712_손익분기점

문제 번호 1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 www.acmicpc.net 알고리즘 분류 수학 사칙연산 문제 풀이 문제풀이 자체는 쉽다. 노트북을 X 대 판다고 했을때 A+B*X > C*X 가 되는 X를 찾으면 된다. '이상'이 아니라 초과 가 되어야 하기때문에 A/(B-C) > X 가 되는 X값을 찾기 위해서 'parseInt( A / (B-C) ) + 1' 을 활용했다. 결과는? 틀렸따. 질문게시판을 찾아보니 parseInt 와 Math.floor()의 동작방식이 달라서 이러한 문제가 생길 수 있다고 한다. 글 읽기 - nod..

→2021.12.30

티스토리툴바