1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 다익스트라 알고리즘과 비슷하게 문제를 풀었습니다. 차이가 있다면 다익스트라는 우선순위 큐를 구현하여 사용한다는 점이지만, 이번 문제 풀이에서는 DFS, 즉 Stack을 사용하여 문제를 풀어도 충분한 문제입니다. 트리는 사이클이 없다는 점을 생각한다면 트리의 지름은 다음과 같이 구할 수 있습니다. 임의의 점 하나를 선택한 후, 그 점에서 가장 멀리 떨어져 있는 노드를 찾고, 그 노드에서 가장 멀리 떨어진 노드와의 거리가 트리의 지름입니다. 문제 풀..
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()..
1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 문제풀이 체스판을 두 개의 체스판으로 나누어 생각하는게 문제의 포인트입니다. 체스판은 하얀색과 검은색, 두 가지 색의 격자로 이루어 져 있습니다. 비숍은 대각선으로만 움직이기 때문에 검은색 자리에선 하얀색 자리에 영향을 줄 수 없기 때문에 나누어 생각하여 시간 복잡도를 현저히 줄일 수 있습니다. let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n"); c..