명왕성의 공전기록

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

https://www.acmicpc.net/problem/3182 문제 풀이 방식 깊이 우선 탐색인 DFS 알고리즘을 활용하여, 각 노드에 방문할 때 깊이를 누적하여 반환하고 저장한 뒤, 저장된 데이터에서 가장 높은 값을 가진 인덱스를 답안으로 출력했다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() .split("\n"); function solution(data) { const arr = data.map(Number); const N = arr[0]; let visited = Array.from(..

https://www.acmicpc.net/problem/1051 문제는 다음과 같이, 꼭짓점에 쓰여있는 수가 모두 같은 가장 큰 정사각형을 찾는 문제다. 문제 풀이 방식 사각형의 크기를 의미하는 첫 줄에 주어진 데이터 N,M이 모두 50으로 작은 편이기에, 가능한 모든 상황을 탐색하는 완전탐색으로 접근했다. 각 좌표마다 가능한 크기만큼의 꼭짓점의 수를 구하고, 만약 모두 일치한다면 결괏값을 수정해주는 방식으로 로직을 구현했다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() .split("\n"); ..

https://www.acmicpc.net/problem/4673 문제는 문제에서 말하는 셀프넘버를 모두 구하는 문제다. 문제 해결 방식 문제에서 말하는 셀프 넘버인 수를 직접 구하기는 어렵단 생각이 들어, 셀프 넘버가 아닌 수를 먼저 모두 찾은 뒤, 전체 10000 이하의 자연수에서 셀프 넘버가 아닌 수를 제외하는 방식으로 로직을 구현했다. const table = {}; for (let i = 1; i

https://www.acmicpc.net/problem/17352 문제는 섬의 갯수 N과 각 섬끼리의 간선들이 주어질 때, '두 섬'을 연결하는 것만으로 모든 섬을 연결할 수 있는 '두 섬'을 찾아 하나만 출력하는 문제다. 문제 풀이 방식 집합을 효율적으로 관리하기 위해 find-union 알고리즘을 활용했다. 먼저 주어진 간선들을 사용하여 각 집합을 구분한 뒤, 반복문을 통해 두 섬이 속한 집합이 다른 경우 해당 두 섬 번호를 출력하고 종료시키는 방식으로 로직을 구현했다. const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .tri..

https://school.programmers.co.kr/learn/courses/30/lessons/169199 해당 문제는 너비우선탐색 알고리즘인 BFS에 대한 이해가 되어 있다면 시간을 들여 충분히 해결할 수 있는 문제다. 타 BFS 알고리즘 문제와 달리, 다음 경로가 '게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 이동'한다는 점만 주의하면 된다. 문제 풀이 방식은 다음과 같다. - 주어진 board 에서 시작지점과 도착지점을 찾는다. - BFS 알고리즘 구현하되, 이때 이동하는 방향에 따라 미끄러져 이동했을 때 도달할 수 있는 다음 위치를 반환하는 함수를 구현한다. 전체 소스 코드 function solution(board) { const Y = board.length, X = board[0]..