문제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/2573 풀이DFS나 BFS를 이용해도 다 되는 문제이며 필자는 BFS를 이용해 문제를 풀었다. 나는 실수로 BFS의 방문 처리를 잘못해 에러가 발생했었다.. 이런 실수는 조심하자.... 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n');let [n, m] = input.shift().split(' ').map(Number);const map = input.map(e => e.split(' ').map(Number));const..
문제https://www.acmicpc.net/problem/23288 풀이해당 문제는 구현이 조금 까다로울뿐 BFS를 이용한 탐색 문제이다. 주사위가 굴러가는 조건들을 조심히 구현하는 것이 중요하다. 필자도 조건을 잘못 설정해서 10분정도 해맸다... 주사위가 굴러간 좌표에 있는 숫자와 주사위 하단의 숫자를 비교한 뒤 주사위를 굴릴 방향을 정하고, 현재 위치의 숫자의 크기와 인접 좌표에 같은 숫자의 개수를 구해주면 문제의 풀이는 끝난다. 인접 좌표에서 같은 숫자의 수를 구할 때 BFS가 사용되는데, 필자는 주사위를 굴릴때 마다 방문 여부를 기록하는 객체를 생성해 방문여부를 기록했다. 코드const input = require('fs') .readFileSync(process.platform === '..
문제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 ..
