백준 node.js 11657번 타임머신 벨만-포드 알고리즘 JavaScript JS

11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 기본적인 밸만 포드 알고리즘 문제입니다. 각 노드에서 모든 간선을 순회하며 모든 노드를 순회하는 O^2의 시간복잡도를 가집니다. 정확하게는 출발노드를 제외한 N-1개의 노드에서 E개의 간선을 순회하여 NE의 시간복잡도를 가집니다 문제풀이 let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n..

• format_list_bulleted 개발관련/백준
• · 2023. 7. 21.
• textsms

백준 node.js 1865번 웜홀 벨만-포드 알고리즘 JavaScript JS

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"); //테스트..

• format_list_bulleted 개발관련/백준
• · 2023. 7. 21.
• textsms

백준 node.js 13913번 숨바꼭질 4 BFS JavaScript JS

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 ..

• format_list_bulleted 개발관련/백준
• · 2023. 7. 7.
• textsms

백준 node.js 14442번 벽 부수고 이동하기2 BFS JavaScript JS

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()..

• format_list_bulleted 개발관련/백준
• · 2023. 7. 7.
• textsms

백준 node.js 1941번 소문난 칠공주 백트래킹 JavaScript JS

1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 문제풀이 방법 25명중 무작위로 7명을 뽑습니다. 7명중 4명 이상이 ‘이다솜파’라면 dfs함수를 실행합니다. dfs함수는 무작위로 뽑힌 7명이 인접한 자리에 앉아있는지 확인하는 함수입니다. dfs를 활용하여 인접한지 확인할 수 있습니다. let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n") .map((v) => v.split("")); let a..

• format_list_bulleted 개발관련/백준
• · 2023. 6. 30.
• textsms