꾸준히 하자

큐를 이용한 알고리즘 문제를 풀 때 매번 shift 메소드를 이용해서 문제를 풀다보니 시간초과를 많이 겪게 된다. shift 메소드를 이용하면 맨 앞의 원소를 꺼내고 다른 모든 원소들을 한칸씩 인덱스를 당겨줘야하기 때문인데 연결리스트를 구현하게 되면 O(N)의 시간복잡도를 O(1)로 줄일 수 있다. class Node { constructor(data) { this.data = data; this.next = null; } } class Queue { constructor() { this.head = null; this.tail = null; this.size = 0; } enqueue(data) { const newNode = new Node(data); // 기존 데이터가 없는 경우 if (!this..

프로그래머스 - 부대 복귀 풀이과정 각 부대원들이 부대로 복귀하는 최단경로를 찾는 문제인데, bfs를 통해 각 부대원별로 목적지까지 최단 경로를 구하려다보니 시간초과가 발생했다. 아래는 시간 초과가 발생한 코드 function solution(n, roads, sources, destination) { const answer = []; const graph = [...Array(n+1)].map(()=>[]); for(const road of roads){ const [a,b] = road; graph[a].push(b); graph[b].push(a); } // source에서부터 graph를 순회하여 destination에 도착하는 최단거리를 구하는 bfs 함수 function bfs(start){ ..

백준 1406 에디터 풀이과정 나쁜 습관을 고치자 이전에도 알고리즘 리뷰를 남기면서 원래 데이터를 변형하는 방법으로는 웬만하면 풀지 말자고 생각을 했었는데, 아무 생각 없이 주어진 input을 shift()로 가져다 쓰고 있었다… 아무리 고치고 고치고 해봐도 방법이 없어서 command를 받는 부분에서 shift()가 아니라 그냥 인덱스로 값에 접근하는 방식으로 하니까 바로 풀려버렸다… 사실 뭔가 배웠다 할만한 내용도 아니긴 한데, 항상 뭔가를 할 때 나쁜 습관이 아닌지 의식해야겠다. 정답코드 const filePath = process.platform === 'linux' ? 'dev/stdin' : './input.txt'; const input = require('fs').readFileSync(f..

1912 연속합 풀이과정 첫번째 접근 : 2차원 배열로 모든 경우의 수 때려넣기 다이나믹 프로그래밍이라 하면 주어진 문제 해결을 위해 여러 개의 하위 문제로 나누어 푸는 방법을 말한다. 부분 문제가 다른 문제들을 해결하는데 사용될 수 있어 답을 여러 번 계산하는 대신 한 번만 계산하고 그 결과를 재활용하는 메모제이션 기법으로 속도를 향상시킨다. 근데 나는 다 구해버렸다… dp[i][j]가 i번째 원소부터 j번째 원소까지의 합이 되도록 모든 값들을 구하고, 각 행에서 최대값을 maxArr에 넣어 그 중 최대값을 반환하도록 구현했다. 풀면서도 안되겠구나 생각은 했지만, 내가 원하는 방식으로 구현하는 연습을 하기 위해 그냥 끝까지 구현은 했다. 결과는 메모리 초과… // 2차원 배열로 각 원소의 행 i, 열 ..

1463 - 1로 만들기 풀이과정 정답은 맞췄지만 개선이 필요함을 느낌 문제 자체는 dp를 이용하면 크게 어렵지 않았는데, N으로 부터 1로 가는 과정에서 i를 만드는데 필요한 연산횟수인 dp[i]를 구하기 위해서는 i+1과 2*i, 3*i번째 값들의 최소값을 가져와야 했다. 그래서 Math.min(dp[i + 1], dp[2 * i], dp[3 * i])라는 연산이 필요한데, dp배열의 원소의 개수를 N개로 설정할 경우 i+1, 2*i, 3*i가 undefined이기 때문에 NaN이 리턴된다. 그래서 dp배열의 범위를 3*N + 1로 설정해 문제를 해결하긴 했는데, 이건 또 너무 메모리 낭비가 될 것 같았다. 개선방법 결국 아래의 부분에서 Math.min 메소드의 인자로 undefined가 들어가기 때..

2839_설탕배달 풀이과정 정답코드 const filePath = process.platform === 'linux' ? 'dev/stdin' : './input.txt'; const input = require('fs').readFileSync(filePath).toString(); const N = Number(input); const dp = [...Array(N + 1)].map(v => 5000); dp[3] = 1; dp[5] = 1; for (let i = 6; i

숫자 변환하기 풀이과정 처음 시도에서는 단순히 bfs를 통해 x -> y로 만드는 최소 count를 찾으려 했다. num > y 인 경우만 예외처리 했지만 불충분 했음 두 번째 시도에서는 checked 배열을 통해 체크한 적이 있는 숫자는 큐에 넣지 않도록 수정함 불충분… 세번째 시도에서는 x -> y가 아닌 y -> x를 만드는 방법을 구현했다. 2와 3으로 나눠서 나오는 수가 정수가 아니라면 큐에 담기지 못하기 때문에 경우의 수가 확 줄어들게 된다. 첫번째 시도(시간초과) function solution(x, y, n) { var answer = 0; function bfs(x){ const q = [[x, 0]]; while(q.length){ const [num, count] = q.shift()..

뒤에 있는 큰 수 찾기 정답코드 function solution(numbers) { const answer = [...Array(numbers.length)].map(v => -1); numbers.forEach((number, idx) => { // 각 number가 이전 number보다 크다면 if(number > numbers[idx - 1]){ let backTrackingIdx = 0; // number > numbers[idx - 1 - backTrackingIdx] 를 만족하는 동안만 반복하는 이유는 // 만약 반대의 경우라면 이전 인덱스의 answer 원소들은 이미 numbers[idx - 1 backTrackingIdx]를 // 부여받았을 것이기 때문 while(number > numbe..

택배상자 정답코드 function solution(order) { var answer = 0; const container = [...Array(order.length)].map((v,i)=>v = i + 1); const stack = []; let containerIndex = 0, orderIndex = 0; while(containerIndex 보조컨테이너 stack.push(container[containerIndex]); containerIndex++; } return answer; }

(롤케이크 자르기)[https://school.programmers.co.kr/learn/courses/30/lessons/132265] 배운 것, 유의할 것 Set을 활용한 풀이 해당 문제는 형과 동생이 각자 중복된 토핑을 갖고 있다면 하나로 보기 때문에 배열로 풀 경우 중복 값을 삭제해주는 별도의 연산이 필요로 하기 때문에 Set을 사용했다. 평소 잘 활용하지 않던 Set의 메소드들 간단 정리 add const set1 = new Set(); set1.add(1); set1.add(2); console.log(set1); // Set(2) { 1, 2 } clear, size const set1 = new Set(); set1.add(1); set1.add('foo'); console.log(set1..