반응형
반응형
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(..
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. 홀수일..
18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 풀이 방법 배양액을 뿌릴 수 있는 케이스를 모두 찾습니다. 케이스를 순회하며 꽃이 피는 개수를 BFS를 통해 구합니다. DFS가 아닌 BFS로 구하는 이유는, 꽃이 핀다면 시간이 지나도 배양액은 흘러가지 않고, 꽃이 핀 자리에서 확산이 멈추기 때문입니다. 따라서 DFS로 구하면 정답을 구할 수 없다고 판단했습니다. 아래 코드 주석을 통해 확인해주세요 let fs = require('fs'); let inp..
9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N-Queen문제 풀이 복습차원에서 적습니다. let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().trim() const N = +input; let answer = 0; next(0, Array(N).fill(0)) console.log(answer) function next(row,board) { if(row === N){ answer++ return } for(let i=0; i