Coding Test with Javascript

문제 문제 보러 가기 풀이 Dynamic Programming 문제이다. 먼저 값을 저장할 배열을 선언해주고, 점화식을 찾은 후, 초깃값을 설정하여 해결한다. d[k]: 2*k 크기의 직사각형을 채우는 방법 수 점화식: d[k] = d[k-1] + d[k-2] d[k]는 다음과 같은 두 가지 방법의 수를 합하여 구할 수 있다. 2*(k-1) 크기의 직사각형 뒤에 1*2 크기의 직사각형을 배치하는 방법 수 2*(k-2) 크기의 직사각형 뒤에 2*1 크기의 직사각형 2개를 배치하는 방법 수 초기값: d[1] = 1, d[2] = 2 처음 시도에서 값을 `Number` 자료형으로 설정하니 통과하지 못했다. 그래서 `BigInt` 자료형으로 변경하여 문제를 해결했다. "use strict" const n = N..

문제 문제 보러 가기 풀이 Map 자료형을 사용하여 각 숫자의 개수를 세고, 이를 활용하여 가장 많은 카드를 찾는다. 이 때, 카드의 숫자 범위가 매우 크므로 BigInt 자료형을 사용해주어야 한다. BigInt 자료형을 사용하지 않아서 계속 틀렸다. BigInt의 범위를 확인하기가 어려운데, 다음 명령어를 사용해서 판별할 수 있다. console.log(Number.isSafeInteger(Math.pow(2, 62))); "use strict" const [n, ...cards] = require('fs').readFileSync('./dev/stdin').toString().trim().split('\n').map(BigInt); function solution(n, cards) { const cn..

문제 문제 보러 가기 풀이 뿌요를 터뜨리는 데 distance를 알 필요가 없으므로 구현이 쉬운 DFS를 사용하여 탐색을 진행하였다. 탐색 결과, 뿌요가 4개 이상인 경우 뿌요를 지웠다. 그리고 필드에 대해서 DFS를 모두 수행해주고, 연쇄가 일어났다면 중력에 따라 뿌요를 재배치하고 다시 DFS를 수행할 수 있도록 코드를 작성하였다. ⚠️ 문제를 꼼꼼히 잘 읽는 습관이 아직 모자란 듯 하다. 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다는 지문 한 줄을 정확하게 읽지 않아서, 세 번의 시도를 실패하고 성공하였다. "use strict" const field = require('fs').readFileSync('/dev/stdin').toStri..

문제 문제 보러 가기 풀이 문제를 보고 간단하게 이중 for문을 사용하여 푸는 방법이 떠올랐지만, N의 최댓값이 1,000,000이므로 시간 초과가 날 것이라고 생각하였다. 그래서 처음에는 스택을 두개 사용하는 방법을 통해서 풀이해봤지만, 메모리 초과가 발생하였다. "use strict" const [[n], a] = require('fs').readFileSync('./dev/stdin').toString().trim().split('\n').map(str => str.split(' ').map(Number)); function solution(n, a) { const answer = []; const s1 = [...a.reverse()]; for (let i = 0; i < n; i++) { con..

문제 문제 보러 가기 풀이 N과 M 시리즈 문제로 백트래킹을 사용한다. 이 문제는 주어지는 수열에 중복인 수가 존재하여 중복 수열이 발생할 수 있어 이에 대한 처리를 해주어야 한다. 최초 풀이 최초 풀이의 경우, 정답을 출력하기 이전에 answers 배열에 기존 수열이 존재하는지 체크하기 위해서 includes 메소드를 사용하였다. 시간 초과가 날 것이라고 예상한 것과 다르게 통과하였다. 하지만 시간 초과가 날 수 있는 확률이 큰 부분을 제거하는 방법이 없을까 풀이를 찾아보았다. "use strict" const [[n, m], arr] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(str => str.split(..

문제 문제 보러 가기 풀이 이 문제는 기존 N과 M 문제에서 숫자 배열을 주는 문제이다. 마찬가지로 오름차순으로 정렬해야하는데, 이를 위해 배열을 먼저 오름차순으로 정렬한 후 백트래킹 작업을 수행하였다. "use strict" const [[n, m], arr] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(str => str.split(' ').map(Number)); function solution(n, m, arr) { const answers = []; const answer = []; const sArr = arr.sort((a,b)=>a-b); const isUsed = Array(n).fill(fals..

문제 문제 보러 가기 풀이 15650번 N과 M(2)에서 중복을 허용하는 문제이다. 간단한 백트래킹을 통해서 풀 수 있다. "use strict" const [n, m] = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(Number); function solution(n, m) { const answer = []; const arr = []; function bt(k) { if (k === m) return answer.push(arr.join(' ')); for (let i = 1; i

문제 문제 보러 가기 풀이 백트래킹 문제로 수열을 만들고 출력하는 문제이다. 수열의 출력 형태가 공백으로 구분되어 있는 것을 보고 정답 배열에 arr.join(' ')을 추가해주는 형식으로 구현하였다. 문제의 조건 중, 수열은 사전 순으로 증가하는 순서로 출력해야 한다는 조건이 있는데, 이는 백트래킹 구현시 해당 조건을 만족시키면서 증가하기 때문에 따로 정렬하지 않았다. "use strict" const [n, m] = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(Number); function solution(n, m) { const answer = []; const isUsed = Array(n+1).fill(fa..

문제 문제 보러 가기 풀이 계속해서 재귀와 백트래킹 문제를 풀고 있는데, 문제 유형이 조금만 달라져도 풀기가 어려워지는 것이 느껴진다. 이 문제의 경우, 어떤 값에 대해서 추가할지 아닐지를 정해나가는 문제이기 때문에 그 두 가지 경우에 대해서 모두 재귀함수를 호출하면서 반복해나가는 형태라 떠올리기 힘들었다. 재귀와 백트래킹 문제를 계속해서 풀어봐야겠다. "use strict" const [[n, s], inputs] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(str => str.split(' ').map(Number)); function solution(n, s, inputs) { let answer = 0; ..