문제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 = [];// ..

문제링크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..

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

문제링크https://www.acmicpc.net/problem/1927 문제풀이, 후기이 문제는 힙 자료구조를 이용해서 최솟 값을 구하는 연산을 최적화 하라는 문제라고 이해하면 된다. 자바스크립트에서 힙 자료구조를 구현하기 위해서는 Class를 이용해서 직접 구현해야 하므로 직접 구현하여 풀었다.참고로 초반엔 시간초과가 났는데 알고보니 console.log때문이었다. 매번 console.log를 하지 않고 답을 구한 뒤 한번의 console.log로 답을 출력하니 시간초과가 일어나지 않았다. 생각보다 console.log가 시간을 먹는다는 걸 알 수 있었다.heap 구현은 능숙하였기 때문에 쉽게 풀 수 있었고 한번더 heap자료구조와 시간복잡도를 최적화 해주는 트리구조에 대해 생각해보는 계기가 되었다...

문제링크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..

문제링크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 = [];..

문제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

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

문제https://www.acmicpc.net/problem/1463 문제풀이dp로 접근하지 않으면 시간초과가 나는 문제였다. 문제풀이의 핵심은 아래 점화식이다. 여기서 dp[i] 는 i를 만들기 위해서 필요한 연산 횟수이다. ( dp[1]=0, dp[2]=1, dp[3]=1 이다 )   1 ) i가 3의배수이고 2의 배수일 때dp[i] = Math. ( dp[i/3] +1 , dp[i/2] +1 , dp[i-1] +1 )    2 ) i가 3의 배수이고 2의 배수가 아닐때dp[i] = Math. ( dp[i/3] +1 , dp[i-1] +1 )    3 ) i가 2의 배수이고 3의 배수가 아닐때dp[i] = Math. ( dp[i/2] +1 , dp[i-1] +1 )     let fs = requir..

문제https://www.acmicpc.net/problem/1541 문제풀이첫번째 for문에서 [ '+1' , '-2' , '-3' , '+2' , '+2' , '3' ] 와 같은 arr를 생성하고 두번째 for문에서 answer을 계산한다 핵심은 음수 이후에 연속적으로 양수가 나올 때 해당 양수는 결국 음수로 계산해야 최솟값을 구할 수 있다는 점이다.예시) 1-2+3+3 => 1-(2+3+3)  이런식으로 음수이후로 연속적으로 나타나는 양수는 모두 음수처리 후 모든 수들을 합하면 최솟값을 구할 수 있다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim();let num = "";let numArr = [];..