명왕성의 공전기록

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을 반환하는 연산이기 때문에, ..

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