GPD2021

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 이전의 백준 1753번: 최단경로 문제랑 같은 문제입니다. 다른 점이 있다면 중간에 반드시 통과를 해야하는 지점이 2개 존재한다는 겁니다. 그러면 두가지 경우가 있습니다. 시작점을 S, 중간점1을 X, 중간점2를 Y, 도착점을 E 라고 했을 때 S - X - Y - E 로 가던지 S-Y-X-E로 가던지 둘 중 하나를 선택하면 됩니다. 임의의 지점s 에서..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 다익스트라 알고리즘 => 힙 시간초과가 계속 나와서 예전에 썻던 방법으로 readline 모듈로 바꿔줘고, 코드에 썼던 배열도 다 큐로 바꿔줬는데 풀 수가 없었습니다. 결국 질문하기 들어가서 보니까 큐가 아니라 힙을 이용해 푸는 문제였습니다. (https://www.acmicpc.net/board/view/71956 옆에 링크에 고수분들이 잘 설명해주셨습니다. ) 큐는 ..

https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다. www.acmicpc.net 1. 집합을 반으로 나눈다. -> 집합A, 집합B const fs = require('fs'); const input = fs.readFileSync("./dev/stdin").toString().trim().split('\n'); const [N, S] = input[0].split(' ').map(v => +v); const B = input[1].split(' ').map(v => +v..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 소수 + 투포인터 이전의 부분합 문제랑 같은 문제 const fs = require('fs'); const N = +fs.readFileSync("./dev/stdin").toString().trim() const prime = new Array(N + 1).fill(true); prime[0] = false; prime[1] = false; for (let i = 2; i * i N) { sum -= nums[start]; start++; } else { end++; if (end == N) { break; } s..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 1. min(answer) 정하기 우선 가장 짧은 길이를 원소의 개수+1 로 정해준다. 만약 조건을 충족하는 연속하는 부분수열이 없을 경우 0을 출력하기 위함. 2. 투포인터, 합 초기화 시작 포인터 0, 끝 포인터 0에서 시작. 최초 합은 첫번째 원소의 값 3. 투포인터 반복 시작. start가 N과 같아지면 이미 모든 경우를 살폈으므로 종료. 4-1, 합이 S보다 크거나 같다면 ..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 0. 배열을 오름차순으로 정렬해줌. 1. min 정하기 용액의 특성값이 1부터 10억. -1부터 -10억 사이. 그러므로 최소값을 20억이라고 주고 시작. -> 두용액을 혼합했을 때 항상 20억 보다 작으므로 2.투포인터 초기화 포인터 1(start)은 0부터 시작해서 1씩 더해주고. 포인터 2(end)는 배열의 마지막부터 시작해서 1씩 빼주면서 확인 3. 두 개..

https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net const fs = require('fs'); const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n"); const N = +input.shift() const target = +input.pop(); const nums = input[0].split(' ').map..

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net const fs = require('fs'); const [N, K] = fs.readFileSync("./dev/stdin").toString().trim().split(" ").map(v => +v); class Node { constructor(item) { this.item = item; this.next = null; } } class Queue { constructor() { this.head = null; this.tail = null; this.length = null; }..