데구리 블로그

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/81305 코딩테스트 연습 - 시험장 나누기 3 [12, 30, 1, 8, 8, 6, 20, 7, 5, 10, 4, 1] [[-1, -1], [-1, -1], [-1, -1], [-1, -1], [8, 5], [2, 10], [3, 0], [6, 1], [11, -1], [7, 4], [-1, -1], [-1, -1]] 40 programmers.co.kr 풀이 자바스크립트로 풀었는데 큰 문제가 있었습니다. 제출 시 몇몇 효율성 테케에서 의문의 런타임 에러를 뱉더라구요. 최대 범위 테스트 케이스를 따로 만들어 로컬에서 돌려보니 다음 에러가 원인이었습니다. RangeError: Maximum call st..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/81304 코딩테스트 연습 - 미로 탈출 4 1 4 [[1, 2, 1], [3, 2, 1], [2, 4, 1]] [2, 3] 4 programmers.co.kr 풀이 그래프 재정의 트랩에 대해 잘 생각해봅시다. 트랩에 도착하면 트랩과 연결된 모든 간선의 방향이 반대가 됩니다. 그럼 같은 트랩을 두 번 밟으면? 다시 원래대로 돌아옵니다. 트랩끼리 연결되어 있어도 마찬가지입니다. 모든 트랩을 두 번씩 밟으면 원래의 그래프로 돌아옵니다. 결국 특정 트랩을 밟았는지 여부는 최대 한 번까지만 체크하면 되고, 한 번 더 밟게 되면 밟지 않았을 때와 같은 상태라고 생각할 수 있습니다. 그럼 각 트랩마다 밟거나, 안 ..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 풀이 처음 문제를 봤을 땐 현재 행을 기준으로 위, 아래쪽 스택 두 개를 이용해서 관리하면 안 될까? 하고 생각했습니다. 근데 이러면 Z연산을 구현 못하더라구요.. 결론부터 말하면 양방향 링크드 리스트를 구현해서 풀 수 있습니다. 1) U, D 연산 이전, 다음 링크를 연속해서 타고 가는 방식으로 구현..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 풀이 간단한 BFS 문제입니다. 각 사람마다 BFS를 돌리는데, 'O'이면 진행..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/81301 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr 풀이 정규표현식을 이용하면 됩니다. 사실 원래는 정규표현식 없이 String.prototype.replaceAll()을 사용하려 했는데, replaceAll() 자체가 ES2021 완전 최신 문법이기도 하고, 프로그래머스의 Node.js 버전이 12 버전이라 완전 최신 문법을 지원 안 해줘서 정규 표현식의 'g' 플래그를 이용하여 해결했습니..

문제 링크 https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 풀이 격자의 각 칸을 Node 구조체로, 현재 단계에 존재하는 파이어 볼을 Ball 구조체로 관리합시다. 각 구조체는 다음처럼 이루어져 있습니다. Ball - int x, y, w, d, s // 현재 좌표(x, y), 무게(w), 방향(d), 속력(s) - pair move() // 공의 방향으로 s만큼 이동한 뒤 곳의 좌표를 반환 Node { ..

문제 링크 https://www.acmicpc.net/problem/21874 21874번: 모자 게임 CS-House에서는 매주 목요일에 연세대학교 컴퓨터과학과에 대한 여러 이야기를 팟캐스트 형식으로 다룬다. 2021년 3월 18일에 진행한 CS-House에서는 ICPC World Final에 진출한 윤인섭 선배가 게스트로 www.acmicpc.net 풀이 생각을 좀 해보다, 첫 사람이 전체에 대한 정보를 모두 줘야 한다고 판단했습니다. 처음에 모든 모자의 합을 알려주고, 각 사람은 내가 볼 수 있는 수와 지금까지 나왔던 수를 합에서 빼면 자기 모자의 수를 알 수 있습니다. 근데 수의 범위가 0 ~ 63입니다. 사람처럼 생각하면 덧셈, 뺄셈이 이상적이지만, 컴퓨터는 xor을 쉽게 할 수 있습니다. 처음..

문제 링크 https://www.acmicpc.net/problem/21873 21873번: 개구리 징검다리 건너기 첫 번째 줄에 개구리들을 움직여야 하는 횟수 $M$을 출력한다. 단, $M$은 $1\,500\,000$을 넘어서는 안된다. 두 번째 줄부터 $M$개의 줄에 걸쳐서 움직인 개구리의 정보를 순서대로 출력한다. $p$번째 www.acmicpc.net 풀이 그림으로 그려보다 화가나서 웹으로 간단한 시뮬레이터를 만들어 규칙을 찾았습니다. 사람은 시각에 예민한 동물입니다.. 1 1 2 1 2 3 ... 1 2 3 ... n 1 2 3 ... n 1 2 3 ... n 2 3 ... n 3 ... n ... n 이런 식으로 한 줄마다 이동해야 하는 개구리의 색이 바뀌게 됩니다. 정답 코드 const fs..

문제 링크 https://www.acmicpc.net/problem/21870 21870번: 시철이가 사랑한 GCD 첫째 줄에 정수 $N$이 주어진다. ($1 \leq N \leq 200\,000$) 둘째 줄에 자취방의 매물번호를 의미하는 정수 $a_1, a_2, \cdots, a_N$이 주어진다. ($1 \leq a_i \leq 200\,000$) www.acmicpc.net 풀이 각 단계마다 반으로 나눠진 배열의 왼쪽, 오른쪽 결과를 재귀적으로 모두 확인하면 됩니다. 재귀 호출의 깊이가 $O(logN)$이고, 각 레벨마다 gcd를 구하기 위해 모든 원소를 봐야 하므로 시간 복잡도는 $O(NlogN)$입니다. 정답 코드 const fs = require('fs'); const stdin = fs.rea..

문제 링크 https://www.acmicpc.net/problem/21869 21869번: Maximum Bishop 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 다음 그림과 같은 $5\times5$ 정사각형 체스판 위의 B라고 표시된 곳에 비숍이 있을 때, 비숍은 대각선 방향으로 움직여 X로 표시된 www.acmicpc.net 풀이 간단하게 풀 수 있습니다. 첫 열의 모든 칸에 비숍을 깔아주고, 1행, n행을 제외한 마지막 열의 모든 칸에 비숍을 깔아주면 됩니다. 정답 코드 const fs = require('fs'); const stdin = fs.readFileSync('/dev/stdin').toString().split('\n'); const input = (() =>..