백준[node.js] > 14940번 쉬운 최단거리
·
🔒Algorithm
문제링크https://www.acmicpc.net/problem/14940 문제풀이너비우선탐색으로 시작점으로 부터 동서남북으로 탐색하면서 최단거리를 갱신하였다. 무리없이 풀 수 있었다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [N, M] = input .shift() .split(" ") .map((n) => Number(n));let s_row = undefined, s_column = undefined;let map = [];for (let i = 0; i Number(n)); line.forEach((v, column) => { ..
백준[node.js] > 10026번 적록색약
·
🔒Algorithm
문제링크https://www.acmicpc.net/problem/10026 문제풀이적록색약이 아닌 사람이 보는 NxN Grid 2차원배열(map1 > R,G,B 모두 존재) 과  적록색약이 보는 NxN Grid 2차원배열(map2 > G,B만 존재 )  를 각각 만든뒤 두 2차원 배열을 탐색(bfs, dfs) 하면서 그룹핑하면 색상 영역의 수를 도출할 수 있다.   let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let N = Number(input.shift());let map1 = [];let map2 = [];let map1GroupCnt = 0;let map2GroupCnt =..
백준[node.js] > 2667번 단지번호붙이기
·
🔒Algorithm
문제https://www.acmicpc.net/problem/2667 풀이일단 지도를 2차원배열 형태로 변환시켰고 이를 이용해서 단지별로 아파트를 묶었다. dfs를 이용해서 특정 아파트에서 갈수 있는 모든 아파트를 하나의 단지로 묶었고 그 과정에서 단지내의 아파트의 갯수를 확인했다.그렇게 apartment 라는 array에 단지내의 아파트 갯수를 push 한뒤 다시 아파트갯수를 오름차순으로 정렬하여 문제의 답을 구할 수 있었다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let N = Number(input.shift());// 지도 2차원 배열로 저장let map = [];// ..
백준[node.js] > 2805번 나무 자르기
·
🔒Algorithm
문제링크https://www.acmicpc.net/problem/2805문제풀이문제조건을 보고 이분탐색이라는 느낌을 받았다. ( 아래조건 참고 )만약 이분탐색을 하지 않고 나무 높이를 하나씩 낮추면서 최댓값을 구하려면 괴랄한 연산횟수가 나온다. 하지만 이분탐색으로 탐색하면 계산횟수를 획기적으로 많이 줄일 수 있다. 이렇게 획기적으로 줄어드는 이유는 나무 높이의 범위가 너무 크기 때문이다. -> 이부분은 직접 케이스를 산정해서 테스트해보면 알 수 있다. ) let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [N, M] = input[0].split(" ").map((n) => Nu..
백준[node.js] > 2630번 색종이 만들기
·
🔒Algorithm
문제https://www.acmicpc.net/problem/2630 문제풀이분할정복 하는 문제이다. 재귀로 접근하여 쉽게 풀 수 있었다.정사각형의 모든 색종이의 색이 같아야 하므로 큰 사각형부터 검사를 하고 검사하는 와중에 색종이 색이 다르면 4분할하여 다시 각 분할된 영역에서의 색종이 색이 같은지 확인하고 같으면 더 이상 분할하지 않고 해당 영역은 탐색을 끝낸다. 위 과정을 코드로 풀면 아래와 같다. let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let N = Number(input.shift());// 정사각 판을 2차원 배열 map으로 구현let map = [];for (le..
백준[node.js] > 1927번 최소 힙
·
🔒Algorithm
문제링크https://www.acmicpc.net/problem/1927 문제풀이, 후기이 문제는 힙 자료구조를 이용해서 최솟 값을 구하는 연산을 최적화 하라는 문제라고 이해하면 된다. 자바스크립트에서 힙 자료구조를 구현하기 위해서는 Class를 이용해서 직접 구현해야 하므로 직접 구현하여 풀었다.참고로 초반엔 시간초과가 났는데 알고보니 console.log때문이었다. 매번 console.log를 하지 않고 답을 구한 뒤 한번의 console.log로 답을 출력하니 시간초과가 일어나지 않았다. 생각보다 console.log가 시간을 먹는다는 걸 알 수 있었다.heap 구현은 능숙하였기 때문에 쉽게 풀 수 있었고 한번더 heap자료구조와 시간복잡도를 최적화 해주는 트리구조에 대해 생각해보는 계기가 되었다...
백준[node.js] > 21736번 헌내기는 친구가 필요해
·
🔒Algorithm
문제링크https://www.acmicpc.net/problem/21736 문제풀이dfs로 접근하여 풀 수 있었다.한번 지나갔던 장소는 map[row][column] = 'X' 로 표기하였다.  //https://www.acmicpc.net/problem/15663// TEST CASE// let data = "3 5\nOOOPO\nOIOOX\nOOOXP";// let input = data.toString().trim().split("\n");let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [N, M] = input.shift();// 캠퍼스 지도를를 2차원 배열로 생성let..
백준[node.js] > 15663번 N과 M (9)
·
🔒Algorithm
문제링크https://www.acmicpc.net/problem/15663 문제풀이-  dfs로 탐색하면서 동시에 백트래킹으로 효율성을 최대화 했다.  - Set 객체를 이용하여 중복을 방지하였다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [N, M] = input[0].split(" ").map((n) => Number(n));let arr = input[1].split(" ").map((n) => Number(n));// 정렬arr.sort((a, b) => a - b);let set = new Set([]);// 숫자 세트를 담을 arraylet group = [];..
백준[node.js] > 11727번 2xn 타일링 2
·
🔒Algorithm
문제https://www.acmicpc.net/problem/11727 풀이문제의 핵심은 다음과 같은 점화식을 구하는 것이다. dp[i] = dp[i-1] + dp[i-1]*2  dp[i] 는 2xI 직사각형의 타일을 채우는 방법이다.  해당 점화식만 도출하면 쉽게 풀 수 있다. let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim();let N = Number(input);let dp = Array(N + 1).fill(0);dp[1] = 1;dp[2] = 3;for (let i = 3; i
백준[node.js] > 30804번 과일 탕후루
·
🔒Algorithm
문제https://www.acmicpc.net/problem/30804 풀이처음 풀이는 시간초과가 나서 연산횟수를 줄이는 방법으로 접근하였다.  내가 푼 방식은 이러하다만약 과일이  1 2 2 3 3 4 5 6 7 8 9 이렇게 주어지면 [ 1 ] 을 담고 kind를 확인 한다.  ( kind:1, count: 1 )[ 1, 2 ] 를 담고 kind, count를 확인한다.  (kind:2 count:2)[ 1 , 2 , 2 ] 를 담고 kind와 count를 확인한다. (kind:2, count: 3 ) 그다음  과일을 담으면[ 1, 2 , 2, 3 ] 이 되고 kind는 3이 된다 이때 kind가 2가 될때까지 left를 올린다. 여기서는 [ 2, 2, 3] 이 될 것이다. 이후에 kind와 coun..