명왕성의 공전기록

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..

https://www.acmicpc.net/problem/1948 문제는 시작 도시에서 도착 도시까지의 최대로 걸리는 시간과, 최대 시간에 맞춰 도착하는 도시의 갯수를 출력하는 문제다. 문제 해결 방식 모든 도로가 일방 통행(양방향 그래프)이며, 싸이클이 없다(위상 정렬 가능)는 점에서 최근에 학습한 위상정렬로 풀이하는 것으로 접근했다. (다익스트라로도 풀이가 가능할 것 같지만, node.js 환경이다 보니, 최소힙 구현까지는 번거로워 위상 정렬을 선택한 이유도 있다.) 그리고 이때 DP 프로그래밍을 활용하여, 시작지점에서 다른 지점으로 이동할 때 걸리는 최대시간을 저장하는 방식으로 데이터를 저장했다. 위상 정렬 부분 소스 코드 const [[N], _, ...arr] = data.map((el) => ..

https://www.acmicpc.net/problem/2252 이 문제를 맞닥뜨렸을 때, 어떻게 풀지 오래 고민하다가 구글의 도움을 받았다. 그리고 이로부터 알게 된 개념은 위상 정렬에 대한 개념. 내 알고리즘 풀이 실력에 비해 너무 어렵거나 쉽지 않아 재밌게 공부할 수 있었다.  위상 정렬의 정의 위상 정렬은 방향 그래프에서 각 정점들의 선후 관계에 따라 정점을 나열하는 알고리즘으로, 해당 알고리즘은 선행 관계가 있는 것들을 순서에 맞게 정렬하는 방법, 또는 의존성을 파악하거나 순서에 맞게 수행할 때 유용한 방법이라고 한다. 위상 정렬의 단계 진입차수 계산 - 각 정점의 진입차수(입력으로 들어오는 간선의 수)를 계산한다. 이는 각 정점이 몇 개의 선행 작업을 가지고 있는지를 의미한다. 진입차수가 ..

https://www.acmicpc.net/problem/22993 문제 풀이 방식 정렬과 반복문을 통해 풀이했다. 먼저, 두번째 줄에서 첫 번째 원소는 준원이의 공격력 K라고 하고, 나머지 원소를 플레이어 공격력의 집합 arr 라고 하자. 이후, 문제에서 자신보다 공격력이 낮은 플레이어를 잡을 경우, 해당 플레이어의 공격력을 흡수하는 조건이 주어졌기 때문에, 공격력의 집합인 arr를 오름차순으로 정렬하여 낮은 플레이어부터 맞상대하며 최대한 공격력(K)을 올릴 수 있도록 했다. 이 과정에서 맞닥뜨린 플레이어의 공격력이 준원이의 공격력보다 높다면 여기서 반복문을 중지하고 'No' 반환, 모든 플레이어를 순회하여 무찌를 수 있다면 'Yes'를 반환하도록 했다. (추가로 1