명왕성의 공전기록

https://www.acmicpc.net/problem/2023 해당 문제는 각 자리수가 모두 소수이며 길이가 N인 숫자를 모두 출력하는 문제다. 문제 풀이 방식 소수를 판정하는 함수를 만들어두고, 다음 만들 수 있는 수가 소수인 경우만 DFS 알고리즘에 인자로 던져주는 방식으로 로직을 완성했다. import sys data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r') input_data = data_temp.read().splitlines() def solution (data) : K = int(data[0]) result = [] def isPrime (n) : if n

https://www.acmicpc.net/problem/5430 해당 문제는 테스트케이스에 대해, 맨앞 요소를 제거하거나 전체를 뒤집는 명령, 전체 수의 갯수, 배열이 주어진다고 할 때, 해당 명령에 따른 결과를 산출하는 문제다. 문제 해결 방식 배열과 같은 자료구조에서 맨 앞이나 맨 뒷 요소를 제거하는 것에 적합한 deque 자료구조로 문제해결에 접근했다. 다만, 'R'의 경우 배열을 뒤집어야 하는데, 이를 직접 소스 코드 내에서 구현하는 것은 시간복잡도 측면에서 불리하기 때문에, 뒤집힌 횟수를 기록하여 뒤집힌 횟수가 홀수인 경우는 맨 뒷 요소를 제거하고 짝수인 경우는 맨 앞 요소를 제거하는 방식으로 로직을 구현했다. import sys data_temp = sys.stdin if sys.platfo..

https://www.acmicpc.net/problem/1926 해당 문제에서는 '그림'의 크기와 그림에 대한 데이터가 주어진다. 이때 '1'이 색칠된 부분이라고 할 때, 색칠된 그림의 갯수와 가장 넓은 크기를 출력하는 문제다. 문제 풀이 방식 연결된 그림의 크기를 구해야 하기 때문에 DFS 알고리즘을 활용하여 접근하되, 그림에 대한 번호와, 각 번호에 따른 크기를 추가하는 로직만 추가하면 풀이가 쉬운 편이었다. (그림이 하나도 없는 경우에는 0을 출력하는 것만 주의하면 된다.) 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toS..

https://www.acmicpc.net/problem/1213 해당 문제는 좌우 대칭이 같은 문자열을 출력하는 펠린드롬 문제다. 문제 해결 방식 먼저 테이블에 각각의 알파벳의 갯수를 담은 뒤, 홀수의 수를 가진 알파벳이 두 개 이상이라면 펠린드롬을 만들 수 없기 때문에 실패 메세지를 출력했다. 만약 알파벳이 홀수인 경우가 없거나 하나만 존재한다면 펠린드롬을 만들 수 있는 경우이므로 먼저 정렬을 취한 뒤 앞 문자열을 생성하고 이를 반전시켜 문제를 풀이할 수 있었다. const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() ...

https://www.acmicpc.net/problem/17836 해당 문제는 좌표 (1,1)에서 좌표 (n,m)까지 이동하는 문제다. 이때 1로 이루어진 벽은 이동할 수 없다. 여기까지는 일반적인 미로찾기 문제와 비슷하나, 해당 문제에는 '검'이라는 존재가 등장하는데, 이 '검'을 획득한 경우 벽을 모두 부술 수 있다는 특징이 있다. 문제 풀이 방식 결국은 최단 거리를 구하는 것이 목표이므로, 내가 원하는 좌표까지의 수행 시간을 반환하는 BFS 알고리즘을 구현한 뒤 해당 로직으로 하여금 검을 획득한 뒤 목표 좌표까지의 거리와 검을 거치지 않고 목표 좌표까지의 거리를 비교하는 방식으로 답을 구했다. 이때 '검'은 벽을 무시하기 때문에, 검을 획득한 뒤 목표 좌표까지의 거리는 검까지의 거리 + 검의 좌표..

https://www.acmicpc.net/problem/3584 해당 문제는 테스트케이스마다 트리를 이루는 n개의 정점과 이를 이루는 간선, 그리고 정점 두 개의 번호가 주어질 때, 해당 두 정점의 최소 조상을 구하는 문제다. 문제 해결 방식 먼저 주어진 테스트케이스에 따라 tree를 구현한 뒤, 특정 노드에서부터 부모 노드를 찾아 기록한 뒤 기록한 내용은 뒤집어 반환하는 DFS 알고리즘을 구현했다. 이는 최정상 노드부터 자기 자신 노드에까지 도달하기 위해 거쳐온 노드들을 포함한 기록이기도 하다. 문제에서 요구하는 두 노드를 해당 알고리즘을 거치게 한 뒤 얻은 거쳐온 노드들의 기록 배열을 활용하여 비교하는 방식으로 문제를 해결했다. import sys data_temp = sys.stdin if sys..

https://www.acmicpc.net/problem/1967 해당 문제는 트리의 지름을 구하는 문제로, 노드와 노드 사이의 가장 긴 거리를 출력하는 문제다. 문제 해결 방식 트리로 이루어진 문제이기 때문에 너비우선탐색 알고리즘인 BFS 알고리즘으로 최정점인 노드 1에서의 가장 거리가 먼 노드를 찾은 뒤, 그 노드로부터 가장 먼 노드 사이의 거리를 구하는 방식으로 정답을 구했다. const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() .split("\n"); function solution(data) { const n =..

https://www.acmicpc.net/problem/1253 해당 문제는 원소의 갯수와 원소가 주어질 때, 두 가지 원소의 합이 배열 내 원소 중 하나와 일치하는 경우가 몇 가지인지 출력하는 문제다. 최대로 등장할 수 있는 원소의 갯수가 2천 개이기 때문에, 이분탐색으로 접근했다. 문제 풀이 방식은 다음과 같다. 문제에서 주어진 수가 정렬되어 있다는 얘기가 없으므로 이분탐색을 위해 오름차순으로 정렬했다. 이후 배열 내 원소 중 하나인 n을 미리 선택한 뒤, 이분탐색으로 두 가지 수를 합쳤을 경우 n을 만족하는지를 파악하는 방식으로 로직을 구현했다. const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux"..