GPD2021

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드 와샬 알고리즘 => 거쳐가는 정점을 모두 확인 const fs = require('fs'); const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n").map(str => str.split(' ').map(Number)); const N = input.shift()[0]; const M = input.shift()..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 밸만포드 알고리즘 => 노드 수 -1 만큼 반복하면서 간선들을 확인. => 마지막에 한번 더 체크 (음의 사이클 확인) const fs = require('fs'); const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n").map(str => str.split(..

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 바로 전에 풀었던 백준 1504번: 특정한 최단경로랑 똑같은 문제입니다. 문제를 설명하는 방식이 낯설었지만 재밌었습니다. 시작점 S랑 경유지 G와 경유지 H가 주어집니다. 그리고 목적지 후보가 될 수 있는 지점 E 가 주어집니다. 예술가가 S에서 시작해서 어떤 목적지로 최단경로로 이동합니다. 이때 예술가를 추적하는 요원이 예술가가 G랑 H를 통과했다는 것을 알고 있습니다. 예술가는 항상 어떤..

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보다 크거나 같다면 ..