algorithm

[백준] 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억이 넘는다. 그렇기에 완전 탐색으로 풀이하였을 때 시간초과가 나왔다. 해당 문제는 이진 탐색으로 풀면 시간초과를 해결할 수 있다. 나무를 자르는 기계로 자를 수 있는 높이는 최대는 가장 긴 나무의 길이, 최소..

[백준] 1261번 알고스팟_Node.js

문제 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 풀이 해당 문제는 BFS문제이다. 하지만 도달하는 최단 거리가 아닌 벽을 최소한으로 부수는 경우를 찾는 것이다. 그렇기에 탐색에 있어서 우선순위가 존재한다. 벽을 최대한 부수지 않는 방식으로 진행하되 목적지에 도달 할 수 없을 때 최소의 벽을 부순다. 이를 구현하기 위해서는 BFS에서 사용되는 queue에 우선순위 별로 넣으면 된다. 기존의 문제에서 queue를 사..

[백준] 14225번 부분수열의 합 _ Node.js

문제 https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 문제 풀이 해당 문제는 부분 수열로 나타낼 수 없는 수 중 가장 작은 수를 출력하는 문제이다. 해당 문제는 조합으로 부분 수열을 탐색이 가능하지만 간단하게 이진수로 나타내어 풀었다. 부분 수열은 해당 수열의 요소가 존재하거나 안하거나로 나타낼 수 있다. 부분 수열에 존재 할 때는 1, 아닐 경우는 0으로 나타낸다. 문제의 1..

[백준] 14226번 이모티콘 - Node.js

문제 문제 풀이 해당 문제는 3가지 진행 방식으로 진행하여 원하는 개수의 이모티콘을 만드는 최소의 방법을 구하는 문제이다. 최소의 방법을 구하기 위해 BFS를 사용하였다. 3가지의 진행 방식을 아래와 같이 오브젝트로 생성하였다. count는 현재 이모티콘의 길이, x는 클립보드의 저장된 이모티콘의 길이이다. const actionCase = { copy (count ,x){ return [count ,count] }, paste (count ,x){ return [count + x, x] }, deleteOne (count,x){ return [count-1,x] } } 해당 진행 방식으로 BFS로 진행하면 된다. 하지만 일반적인 BFS문제와 다른 점이 있다. 그것은 클립보드이다. 일반적인 BFS문제는 ..