GPD2021

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

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. 두 개..