1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 이 문제는 벨만-포드 알고리즘을 이용하여 풀 수 있습니다. 일반적인 벨만-포드 문제와는 다르게, 각 노드에 도달할 수 있는 최소시간을 Infinity로 하면 풀리지 않습니다. 시작 노드가 모든 점이 될 수 있기 때문에 Infinity가 아닌 0으로 초기값을 넣어 줍니다. 문제풀이 let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().split("\\n"); //테스트..
16920번: 확장 게임 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위 www.acmicpc.net 이 문제는 2중 Queue를 구현하는 문제라 생각됩니다. value값으로 Queue를 가지는 배열 Queue를 만들어, 배열 Queue를 순회하면서 내부 Queue를 순회하는 방식으로 문제를 풀었습니다. 문제 풀이 let fs = require('fs'); const input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n"); const [N,M,P] = input[0].split(" ").map(..
1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘을 이용하여 문제를 풀었습니다. 다익스트라 알고리즘은 노드와의 가중치가 다를 경우, 노드와 노드 사이의 최단 거리를 찾는 알고리즘 입니다. 또한 가중치의 값은 양수이어야 합니다. 음수일 경우 다익스트라가 아닌 밸만 포드 알고리즘을 사용해야 합니다. 그렇지 않으면 싸이클에 빠집니다. 이번 문제는 다음과 같이 풀었습니다 X마을로 올 수 있는 최단 거리를 찾는다 X마을에서 갈 수 있는 최단 거리를 찾는다 그 둘을 더한 ..
1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net (A*B)%C = (A%C) * (B%C) % C 라는 모듈러 산술을 이용하여 문제를 풀 수 있습니다. 아래 주석을 확인해 주세요 문제 풀이 et fs = require('fs'); let [A,B,C] = fs.readFileSync('/dev/stdin').toString().trim().split(" ").map(BigInt) /* (A*B)%C = (A%C) * (B%C) % C 1. 짝수일 때 (A^B)%C = (A^(B/2) * A^(B/2)) % C = (A^(B/2)%C * A^(B/2)%C) % C 2. 홀수일..
13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 풀이 방법 다른 언어면 잘 모르겠지만, node.js로 푸니깐 메모리초과의 환장을 보여주었습니다.. 제가 생각했을 때 문제의 핵심은 다음과 같습니다 메모리초과를 생각하여 Queue를 직접 구현한 BFS를 사용한다. 메모리초과를 생각하여 방문한 노드를 링크드 리스트로 연결하여 답을 낼 때 까지 순회한다. 정답 코드 //Queue 구현을 위한 노드 구현 class Node{ constructor(value){ this.data ..
14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 나를 3시간 동안 괴롭힌 문제… 문제 자체는 쉬워 보였습니다. 그러나 메모리 초과와 시간 초과가 계속해서 나오고, 어디가 문제인지 가늠되지 않았기에 글을 조금 적어봅니다. 문제 핵심 이 문제의 핵심이라 생각되는 것은 DFS가 아닌 BFS로 푼다. Queue를 직접 만들어야 한다. 틀린 문제풀이 let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString()..