algorithm/problems

[백준]1107번 리모컨

문제 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 문제 풀이 필자는 해당 문제를 처음에는 수학적으로 접근을 하였다. 하지만 계속되는 예외 케이스들에 걸려 계속 오답처리가 되었다. 6번을 틀리고 나서 문제 풀이 방법을 변경하였다. 해당 문제의 제시된 조건을 보면 제한 시간이 2초였다. 그래서 브루트포스로 접근해보았다. 최대 목표 채널은 500,000 이므로 최대 자리수를 10의 6승에서 내려가는 것이 최대 크기일 것이다. 즉 ..

[백준] 1072번 Z _ Node_js

문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 문제 풀이 해당 문제는 규칙을 찾아 해당 규칙을 통해 답을 구하는 수학 문제이다. 숫자의 진행 방향은 Z모양으로 2^n X 2^n 단위로 진행이 된다. 그렇기에 여기서 규칙을 찾을 수 있다. 아래 그림을 보자. Z모양의 크기는 2^2k만큼 증가하는데 이를 x축과 y축 별로 증가하는지 작성해보았다. 각 x축은 2^2x, y축은 2^(1+2y)만큼 씩 증가한다. 그렇기에 시작점을 수학적..

[백준] 1003번 피보나치 함수 _ Node.js

문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제풀이 해당 문제를 조금 잘라서 나타냈는데 결국 피보나치 수열을 진행하면서 f(0)과 f(1)을 각 몇 번씩 사용하는지 출력하는 문제이다. 해당 문제는 피보나치 수열을 구하는 DP문제에서 값을 저장하는 것이 아닌 f(0)과 f(1)을 사용하는 횟수를 저장하면 된다. 제출 코드 const fs = require('fs'); const stdin = (process.platform === 'linux'? fs.readFileSync('/dev/stdin').toString() : `2 6 ..

[백준] 18111번 마인크래프트 _ Node.js

문제 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 문제 풀이 해당 문제는 문제가 길지만 정리하면 간단한 수학 문제이다. 땅을 캐는데는 2라는 시간이 소모되고, 땅을 채우는데는 1이라는 시간이 소모된다. 이 때 땅을 채우기 위해서는 인벤토리에 땅 블록이 있어야지만 가능하다. 문제는 최대 층에서 최소층까지 진행하며 해당 층을 만들기 위해서는 얼마의 시간이 필요한지 확인하면 된다. x라는 층을 만들기 위해서는 x보다 높은 블록을 제거하고, x ..

[백준] 6568번 덩치 _ Node

문제 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 문제 풀이 해당 문제의 입력의 최대 개수는 50이다. 즉 브루트 포스로 간단하게 풀이하였다. const fs = require('fs'); const stdin = (process.platform === 'linux'? fs.readFileSync('/dev/stdin').toString() : ``).split('\n'); const input = (() => { let lin..

[백준] 2805번 나무 자르기 _ Node.js

문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 풀이 처음 해당 문제를 풀 때 간단한 문제로 판단하여 완전 탐색을 시작하였다. 하지만 해당 문제의 나무의 개수는 최대 100만개, 길이는 2억이 넘는다. 그렇기에 완전 탐색으로 풀이하였을 때 시간초과가 나왔다. 해당 문제는 이진 탐색으로 풀면 시간초과를 해결할 수 있다. 나무를 자르는 기계로 자를 수 있는 높이는 최대는 가장 긴 나무의 길이, 최소..