꾸준히 하자

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

프로그래머스 level 2 - 미로 탈출 배운 것, 유의할 것 레버를 방문했다가 방문 배열과 큐를 초기화한 후 출구로 가는 것만 생각할 수 있다면 전형적인 그래프 탐색 문제였고, BFS로 어렵지않게 풀 수 있었다. 그렇지만 방문배열과 큐를 초기화하는 과정에서 break 가 아닌 continue 를 쓰는 바람에 한참의 시간을 쏟아버림… 문제의 코드는 상하좌우를 확인하면서 레버를 방문하면 방문배열과 큐를 초기화해주는데, 코드를 짜면서 처음에는 continue를 사용했다. 다음 while문이 시작될 것 처럼 생각했던 것 같다. 그치만 이 때문에 위쪽 통로를 탐색하면서 레버를 발견해서 초기화되면서 '하좌우’에서 통로를 만나면 바로 방문처리를 해버리면서 문제가 발생했었다. for(let i = 0; i < 4; ..

k진수에서 소수 개수 구하기 배운 것, 유의할 것 소수판별 function isPrime(num) { if(num