명왕성의 공전기록

https://www.acmicpc.net/problem/12847 문제 풀이 방식 n의 최댓값이 10만 이하이기 때문에, 최소한의 시간 복잡도로 해결할 수 있는 방식으로 접근했다. 문제 해결 방식은 단순하다. 우리에게 5일의 시간이 주어지고, 2일 간 일을 할 수 있다고 할 때, 미리 처음에서부터 2일차까지의 수익을 구한 뒤, 이 값에서부터 i일차의 수익은 가산, i-2일차의 수익은 감산해가며 전체 값을 갱신하고 이 해당값이 최댓값이라면 최댓값으로 갱신하는 것을 반복하며 최댓값을 구할 수 있었다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력...

https://school.programmers.co.kr/learn/courses/30/lessons/132266 해당 문제는 총 지역 수, 왕복 가능한 두 지역을 원소로 하는 배열, 각 부대원들이 위치한 지역, 목적지가 주어질 때, 각 부대원들이 부대로 도착할 수 있는 최소시간을 출력해야 하는 문제다. 문제 풀이 방식 출발지에서 목적지까지 도착이 가능한지 확인하는 방법도 있겠으나, 반대로 목적지에서부터 출발지에 도착할 수 있는지 기록하는 것이 메모리나 시간 측면에서 유리할 것이라 판단하여 이를 바탕으로 로직을 작성하였다. function solution(n, roads, sources, destination) { const distances = Array.from({ length: n + 1 }, (..

https://www.acmicpc.net/problem/2635 문제는 해당 규칙에 따라 만들 수 있는 수열의 최대 길이와, 최대 길이를 이루는 수들을 출력하는 문제다. 문제 해결 방식 수의 범위가 3만 이하로 작은 편이고, 만들어지는 수열 역시 길이가 크게 길지 않을 것이라 판단하여 모든 경우의 수를 탐색하는 완전 탐색으로 접근했다. N이 주어질 경우, 1부터 N까지 모든 경우를 대입하여 문제 요구에 따라 가장 길이가 길게 만들어지는 로직을 구현하면 된다. const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() .spli..

https://www.acmicpc.net/problem/14888 해당 문제에서는 연산을 통해 최댓값, 최솟값을 만들 수와 연산자의 갯수가 각각 주어지고, 해당 요소들을 통해 만들 수 있는 최댓값, 최솟값을 출력하면 된다. 문제 풀이 방식 최대, 최솟값을 구하기 위해 백트래킹 알고리즘으로 접근했다. 연산의 사용할 수를 numbers 배열, 연산자들의 갯수를 opts로 초기화한 뒤, 백트래킹 로직을 작성했다. 백트래킹 함수는 현재값, 깊이, 연산자들의 갯수를 인자로 하며, 해당 '깊이'가 글자수와 같을 때 (즉 모든 연산을 완료했을 때) 결괏값에 저장토록 했다. 함수 내부에서는 각 연산자마다 if문을 활용하여 각각의 로직을 작성할 수 있었지만, 개인적으로 좋아하지 않는 방식이기 때문에, 각 연산자마다의 ..

https://www.acmicpc.net/problem/14584 문제 풀이 방식 모든 경우의 수를 파악하는 방식으로 문제를 해결했다. 첫 번째 등장한 문자열의 charCode를 하나씩 증가시킨 문자열로 바꾼 뒤, 해당 문자열 안에 사전에 존재하는 단어가 있는지 파악하여 없을 경우 재탐색, 있는 경우 답을 출력하는 로직으로 구현했다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() .split("\n"); function solution(data) { const [str, _, ...words] = ..

https://www.acmicpc.net/problem/5014 해당 문제는 전체 층수, 시작 위치, 목적지, 업버튼으로 오를 수 있는 층수, 다운버튼으로 내려갈 수 있는 층수가 주어졌을 때, 최소 몇번으로 목적지에 도착할 수 있는지 묻는다. 문제 풀이 방식 최소 몇번으로 도착하는지 묻기 때문에, BFS 알고리즘으로 접근했다. 처음 시작 위치로 시작하여, 해당 위치에 이미 방문했는지 여부를 검증함으로써 시간복잡도를 줄이고, 다음 올라가거나 내려가는 위치가 올바른 위치인지 검증한 후 대기열(queue)에 추가하는 방식으로 문제를 해결하였다. 처음 위치와 목적지가 같을 수 있다는 것만 주의하면 어렵지 않다. 전체 소스 코드 const fs = require("fs"); const input = fs .re..

https://www.acmicpc.net/problem/1806 해당 문제는 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중 가장 짧은 것의 길이를 구하는 문제다. 문제 풀이 방식 부분 합을 구하기 위해서 두 포인터를 활용하여 문제를 해결하였다. 부분합의 길이는, 인덱스로 삼고 있는 right와 left의 차라는 것만 기억하면 풀이는 그리 어렵지 않다. const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() .split("\n"); function solution(data) { const [[N, M], arr]..

https://www.acmicpc.net/problem/1312 문제는 문제 내용 말마따나 a,b,n 의 수가 주어지고, a/b 를 나눈 소수에서 소숫점 아래 n의 자리를 구하는 문제다. 문제 해결 방식 단순한 문제라 생각되지만, 부동소수점에 대한 개념이 없다면 풀이가 어렵다. 부동소수점은 컴퓨터에서 실수를 표현하는 방식 중 하나로, 소수점을 고정된 위치에 두는 것이 아니라 소수의 위치를 조절하는 방식이다. 부동소수점은 컴퓨터 입장에서 효율적으로 실수 데이터를 저장하는데에는 좋은 방식이나, 알다시피 컴퓨터는 2진법으로 동작하기 때문에, 큰 소숫점에 경우는 계산과정에서 오차가 발생하기도 한다. 간단한 예시로 0.1과 0.2를 합할 경우를 예를 들면, 부동소수점 정확성 문제로 0.30000000000000..