문제https://www.acmicpc.net/problem/1753 풀이이번 문제는 다익스트라 알고리즘 문제이다. 필자는 BFS를 이용한 다익스트라 알고리즘 구현을 시도했지만, 시간 초과 에러가 발생했다.이유는 BFS의 탐색 방식에 있다. 필자의 BFS는 큐에 탐색할 경로의 정보를 담고 하나씩 가져오며 완전 탐색을 진행했다. 불필요한 경로까지 검증하면 시간 복잡도가 높아진다.... 이를 해결하기 위해서는 항상 최소의 값을 가져올 수 있는 최소힙을 이용해야 한다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim..
백준
문제https://www.acmicpc.net/problem/21610 풀이이번 문제는 조건이 까다로운 구현 문제이다. 이 문제에서 가장 어려웠던 것은 기능의 구현이 아닌 문제 설명에 대한 이해이다. 구름이 처음 생성되는 구역은 [N-1, 0], [N-1, 1], [N, 0], [N, 1]이며, 이후 한 명령의 동작이 모두 끝나면 새로운 구름의 구역이 생성되는데 이 새롭게 생성된 구름을 이용해 다음 동작을 해야한다...... 이 부분을 햇갈려서 조금 오래 걸렸다...https://www.acmicpc.net/board/view/112464 그리고 다시한번 주의해야할 점을 알게되었다.바로 동기적인 데이터 갱신이다. 이 문제에서는 구름의 이동 동작을 구현할 때 구름의 생성과 삭제를 연속해서 했지만, 사실 구..
문제https://www.acmicpc.net/problem/2606 풀이해당 문제는 DFS와 BFS 풀이 모두 가능한 문제이다. 간단한 문제이기 때문에 DFS와 BFS를 다시 연습하기 위해 풀이했다. BFS 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n');const n = +input.shift();const linked = +input.shift();const arr = input.map(e => e.split(' ').map(Number));const map = {};const ..
문제https://www.acmicpc.net/problem/2292 풀이벌집의 방 수가 6의 배수대로 증가하는 모습을 보며 2 번째 방의 시작인 2와 끝인 7의 변화를 지정해 주며, 입력되는 N이 해당 범위 내에 속하는 지를 확인하며 시뮬레이션 한다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n');let n = +input.shift();if (n === 1) console.log(1);else { let cnt = 1; let [min, max] = [2, 7]; while ..
문제https://www.acmicpc.net/problem/2003 풀이투포인터의 기본 문제이며, 주어지는 수열에서 연속된 수들의 합이 M이 되면 카운트를 올리는 문제이다. 이 문제에서 while 문을 이용해 반복해주는 부분이 있는데, 이 while 문의 조건에 원래는 lp 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n');const [n, m] = input.shift().split(' ').map(Number);const arr = input[0].split(' ').map(Num..
문제https://www.acmicpc.net/problem/5972 풀이다익스트라다와 BFS 알고리즘을 이용한 문제이며, 필자는 큐를 이용한 풀이를 진행했다. 1번부터 시작하며 큐에 시작하는 위치를 저장하고 순회를 시작한다. 순회하며 각 지점에 도달하기 까지의 최소 비용을 측정한다. 최단 거리의 경우 st 지점부터 ed 지점까지 소요되는 비용을 더하며 최소 비용을 구한다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e);const [n, m] = input.shi..
