명왕성의 공전기록

https://www.acmicpc.net/problem/14217 자바스크립트로 풀이한 정답자가 없어서 포스팅하게 된 문제다. 여타 BFS 알고리즘 같이 루트 노드와 각 노드 사이의 최단 거리를 출력하는 문제지만, 다른 점이 있다면 간선을 추가 | 삭제를 할 수 있어야 문제 해결이 가능하다. 문제 해결 방식 BFS 알고리즘에 대한 내용은 많이 다뤘기 때문에, 간선을 추가 | 삭제하는 부분만 언급한다. 입력값을 활용하여 상단의 로직으로 트리형 자료 구조를 만들었다고 했을 때, 이차원 배열로 트리 구조가 형성되게 된다. 이때, 간선을 삭제하는 경우에 있어, splice 메서드를 사용할지 filter 를 사용할지 고민을 했더랬다. 둘다, 시간 복잡도가 O(n)으로 동일하지만, splice의 경우 삭제할 원소..

https://www.acmicpc.net/problem/25416 문제 해결 방식 BFS 알고리즘을 활용하여 문제를 해결했다. 주어진 보드와 같은 크기의 이차원 배열을 만들어, 방문 처리를 함으로써 시간 복잡도를 줄이려 했다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() .split("\n"); function solution(data) { const matrix = data.map((el) => el.split(" ").map(Number)); const [y, x] = matrix.pop();..

https://www.acmicpc.net/problem/1021 문제를 읽자마자, 자료구조 덱을 활용한 문제라는 것을 파악했고, 내게 떠오른 언어는 다양한 자료 구조를 모듈로 불러와 사용할 수 있는 파이썬이었다. 근래의 포스팅 대부분이 자바스크립트로 작성된 포스팅이라는 것을 핑계로 이번 포스팅은 파이썬으로 작성한다. 문제 풀이 방식 앞서 얘기한 바와 같이 해당 문제는 자료구조 덱으로 구현이 가능하다. 여기서 중요한 점은 연산의 최소횟수를 구해야 한다는 점인데, 이는 해당 덱에서 가지고 있는 원소의 양의 중앙값, 구하고자 하는 원소의 인덱스값을 비교하여 2번 연산을 할 것인지 3번 연산을 할 것인지 결정할 수 있도록 했다. 전체 소스 코드 import sys data_temp = sys.stdin if..

백준에서 벌써 200일 연속 알고리즘을 풀었다. 시간이 지남에 따라, 문제 푸는 양이 줄어듦은 사실이나 해결하는 문제의 질 자체는 높아져 그리 나쁘지 않다 생각한다. 오늘 걷지 않으면 내일 뛰어야 한다는 마음 가짐으로, 처음 목표했던 연속 1년 문제 풀이를 위해 노력해야지.

https://school.programmers.co.kr/learn/courses/30/lessons/77486 문제 지문이 굉장히 긴 편이기에, 문제의 일부만 대체 후 설명한다. 문제는, 각 판매원의 이름을 담은 배열 enroll, 각 판매원을 다단계 조직에 참여시킨 다른 판매원의 이름을 담은 배열 referral, 판매량 집계 데이터의 판매원 이름을 나열한 배열 seller, 판매량 집계 데이터의 판매 수량을 나열한 배열 amount가 매개변수로 주어진다. 여기서 중요한 규칙이 있는데, 만약 판매자가 a금액 만큼 판매한 경우, 해당 금액의 10%를 자신을 다단계에 참여시킨 판매원에게 지급하며 남은 90%의 금액을 자신이 갖게 된다. (이때, 10%의 금액을 받은 판매원 역시 해당 금액의 10%를 자..

https://www.acmicpc.net/problem/6550 문제는 a,b 두 문자열이 주어졌을 때, b에서 몇 개의 문자를 제거한 뒤 순서를 바꾸지 않고 합쳤을 경우, a가 b의 부분 문자열이 되는지 출력하는 문제다. 문제 풀이 방식 a,b 문자열이 존재할 때, 두 개의 포인터를 두어 새로운 문자열을 만든 뒤, 해당 문자열이 짧은 문자열인 a와 일치하는지 확인한 뒤 결과를 리턴하도록 했다. const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() .split("\n"); function solution(data) { c..

https://www.acmicpc.net/problem/1308 자바스크립트로 해결된 포스팅이 없어 포스팅하게 됨. 문제 풀이 방식 시작 날짜의 총 날짜와, 끝 날짜의 총 날짜를 깡으로 구해서 그 차이를 출력하는 방식으로 접근하였다. 문제에서 말하는 윤년 기준을 적용하는 방식이 은근히 까다로웠던 문제. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() .split("\n"); function solution(data) { const [[sy, sm, sd], [ey, em, ed]] = data.map..

https://www.acmicpc.net/problem/2891 문제 해결 방식 각 팀마다 보유한 카약의 갯수를 먼저 저장해두었다. 이후 상황에 따라 최선의 선택을 하는 탐욕법으로 접근하였는데, 기초 논리는 다음과 같다. 만약 자신의 보유한 카약의 갯수가 2로 부족한 팀에게 배를 줄 수 있으며 이웃된 팀 모두 배가 필요하다면, 자신의 앞번호부터 배를 주는 방식으로 선택했다. 이와 같은 방법을 통해, 문제에서 제시된 '다른 팀에서 받은 카약을 다른 팀에 빌려줄 수 없다'를 만족할 뿐더러, 출발하지 못하는 팀 역시 최소화할 수 있다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? ..