명왕성의 공전기록

https://www.acmicpc.net/problem/17390 문제에서는 N개의 질문, Q개의 테스트 케이스 갯수, 원소가 숫자로 이루어진 집합, 그리고 합을 구하기 원하는 시작점과 끝점이 주어진다. 문제 접근 방식 문제에서 주어진 내용처럼, 먼저 숫자들이 원소로 주어진 집합을 정렬한 후 각기 테스트케이스에 맞는 합을 구해주면 된다. 다만 이때 테스트케이스가 주어질 때마다 합을 구하기 위해 새로 연산하는 것보다, 각 인덱스까지의 누적값을 해쉬 테이블에 저장한 뒤 활용해주는 방식으로 문제를 해결하는 것이 보다 시간을 절약할 수 있다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux"..

https://www.acmicpc.net/problem/20115 문제 풀이 방식 에너지 드링크의 양을 최대로 하기 위해선 버리는 음료의 양을 최소화하여야 하기 때문에, 양에 따라 오름차순으로 정렬한 뒤, 가장 양이 많은 음료에 합치는 방식으로 구현했다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() .split("\n"); function solution(data) { const N = +data[0]; const arr = data[1] .split(" ") .map(Number) .sort((..

https://www.acmicpc.net/problem/1326 해당 문제는 BFS 알고리즘으로 해결할 수 있는 문제다. a가 꼭 b보다 작다는 조건이 없기 때문에, 양쪽 방향으로 모두 이동이 가능하다는 점을 주의하면 된다. 다만 먼저 방문처리를 하지 않으면 queue에 삽입되는 원소가 많아 시간이 오래 걸릴 수 있으므로 queue 삽입 전 방문 처리를 하는 방식으로 처리하는 것이 좋아보여 아래와 같이 로직을 작성했다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() .split("\n"); func..

https://www.acmicpc.net/problem/4889 문제 해결 방식 일반적인 스택 문제를 응용하여 해결했다. 먼저 스택에 '{}'이 삽입될 경우, 이는 문자열이 안정된 경우이므로 우선 삭제하여 스택에 쌓이는 원소를 최소화하였다. 이후 스택에 남은 원소들을 변화시키되, 괄호를 변환시키는 횟수를 최소화하여야 하는데, 이때는 스택에 쌓인 원소를 두개씩 짝을지어 삭제시키고 때마다 변환시키는 횟수에 추가했다. 예를 들어, '}{'로 두 원소가 다른 경우는 올바른 문자열로 만들기 위해서 두 원소를 모두 변화시켜야 하므로 2회를 변환 횟수에 추가하고 '}}' 또는 '{{'와 같이 두 원소가 모두 같은 경우는 둘 중 하나만 바꾸어도 올바른 문자열이 되기 때문에 1회 연산을 변환 횟수에 추가했다. 전체 소..

https://www.acmicpc.net/problem/25516 자바스크립트 정답자가 2명 뿐이라 포스팅하게 된 문제. BFS 알고리즘에 대해 이해하고 있다면 어렵지 않다. 문제 해결 방식 먼저 문제에서 제시된 트리 구조를 구현한 뒤, BFS 알고리즘을 구현했다. 이때, 문제에서는 '수확할 수 있는 사과까지의 거리'가 주어져 있으므로, 큐(대기열)에 원소를 삽입 시 루트 노드까지의 거리를 담아 삽입하는 방식으로 구현했다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() .split("\n"); fu..

https://www.acmicpc.net/problem/17103 문제 해결 방식 수의 범위가 100만 이하이기 때문에, - 에라스토테네스의 체를 활용하여 모든 소수를 탐색하고 - 테스트케이스에 따라 조건에 맞는 파티션을 찾아내는 방식으로 접근했다. 에라스토테네스의 체는 다음과 같은 로직으로 생성하였다. function makingPrimes(n) { // 소수를 판정하기 위한 배열 const primes = Array.from({ length: n + 1 }, () => true); (primes[0] = false), (primes[1] = false); for (let i = 2; i

https://www.acmicpc.net/problem/23747 문제는 지도의 크기, 알파벳으로 이루어진 영역, 시작 위치, 한별이가 실행하는 행동이 주어질 때, 한별이의 시야를 출력한다. 문제 해결 방식 문제 해결을 위한 접근으로 세 가지를 구분하여 접근했다. 1. 'LRUD'와 같이 한별이의 움직임에 관한 입력이 주어졌을 시 현재 위치를 변동시키는 로직 구현. 2. 'W' 입력인 와드 설치가 주어졌을 시 현재 위치의 영역(알파벳)의 시야를 밝히는 BFS 로직 구현. 3. 마지막으로는 한별이의 마지막 위치에서의 상하좌우 시야 밝히기 구현. 소스 코드가 길다보니, 주석으로 설명을 대체한다. 변수 선언 4 5 // Y, X 지도 크기 aaabc // matrix 영역 dcbbc dccaa ddaaa 3..

https://www.acmicpc.net/problem/18112 해당 문제 역시 자바스크립트로 해결된 풀이가 없어 포스팅하게 되었다. 문제 풀이 방식 이진수와 비트마스킹에 대해 조금이라도 이해하고 있다면 풀이가 어렵지 않은 문제. 하지만, 항상 비트마스킹 연산자는 정확히 기억나지 않으니, 이전에 포스팅했던 내용을 참고했다. (기특해 과거의 나...) 2023.11.17 - [개발/Python | Java] - Python 문법 & 비트마스킹 해당 문제에서 가장 중요한 부분은 한 자리 숫자를 보수로 바꾸는 방식이기에 이에 대한 설명만 남긴다. 한 자리의 숫자를 보수로 바꾸는 연산은 연산자(^ XOR) 하나로 해결이 가능하다. XOR 연산은 두 개의 비트가 서로 다를 때 1을 반환하는 연산이기 때문에, ..