명왕성의 공전기록

https://www.acmicpc.net/problem/4803 문제는 각각의 테스트케이스가 존재할 때, 해당 테스트에 대해 트리를 헤아린 뒤 그 갯수에 따라 텍스트를 반환하는 문제다. 다만, 사이클이 존재하는 경우 그 경우는 헤아리지 않고 반환함을 주의해야 한다. 문제 풀이 방식 근래 들어 가장 오래 붙잡고 있던 문제였다. 사이클과 트리에서 힌트를 얻어, Find-Union 알고리즘으로 접근하고 사이클을 이루는 정점은 따로 빼주며 진행하는 데까지는 어렵지 않았으나, 마지막 사이클에 포함되지 않은 정점과 사이클에 포함된 정점을 계산하는 과정에서 많이 헤맸다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platfor..

https://www.acmicpc.net/problem/1590 해당 문제는 N개의 버스, 버스터미널에 도착하는 시간 T, 그리고 각각의 버스의 시작 시간, 간격, 대수가 주어진다고 할 때, 가장 빨리 갈 수 있는 버스를 타기 위해 기다려야 하는 시간을 출력하는 문제다. 문제 해결 방식 이분탐색 문제로 구성되어 있었지만, 완전탐색으로 가능할 것 같아 완전탐색으로 해결했다. 버스 스케쥴을 하나씩 순회하는 과정에서 가장 늦는 버스 시간이 버스 터미널 도착시간보다 이를 경우, 패스하는 과정을 넣어 시간복잡도를 단축시켰다. const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입..

https://www.acmicpc.net/problem/1038 해당 문제는 문제에서 말하는 감소하는 수를 구한 뒤, N번째 감소하는 수를 출력하는 문제다. 문제 해결 방식 먼저 '감소하는 수'를 담을 배열을 구현한 뒤, 재귀함수를 만들어 '감소하는 수'를 담도록 했다. 해당 재귀함수는 아래와 같은데, 가장 끝에 있는 수를 뽑은 뒤 이보다 작은 수만 순회하여 다시 재귀함수를 동작시키는 방식으로 구현했다. 이때 문제에서 얘기하는 '감소하는 수'의 최댓값은 9876543210 이므로, 이를 이를 탈출 조건으로 지정하였다. def act (n) : if n > 9876543210 : return storage.append(n) limit = int(str(n)[-1]) for i in range(limit)..

https://www.acmicpc.net/problem/1717 해당 문제는 집합의 갯수 N과 연산의 갯수 M, 그리고 연산이 주어진다. 이때, 맨 앞 정수가 0인 경우 두집합을 합치고, 1인 경우는 같은 집합에 있는지 확인한다고 할 때, 1로 시작하는 입력에 대해 원소 a,b가 같은 집합에 포함되어 있으면 'YES' 그렇지 않다면 'NO'를 반환하는 문제다. 문제 해결 방식 집합이 각자 자기 자신을 가지고 시작하고, 집합을 합치거나 공통 루트를 찾는다는 점에서, 이전에 크루스칼 알고리즘에서 학습했던 find-union 알고리즘을 떠올려 적용시켰다. 두 집합을 합치는 연산에는 union을, 같은 집합에 포함되어 있는지 확인하는 연산에서는 find를 활용하였다. 전체 소스 코드 import sys dat..

https://www.acmicpc.net/problem/7569 해당 문제는 X,Y,Z의 길이와 토마토의 정보가 주어진다. 이때 정수 1은 익은 토마토, 0은 익지 않은 토마토, -1 은 토마토가 들어있지 않은 칸이라고 하고, 익은 토마토는 상, 하, 좌, 우, 앞, 뒤에 익지 않은 토마토를 하루 후에 익게 만든다고 할 때 전체 토마토가 다 익기까지 얼마나 걸리는지 구하는 문제다. 문제 해결 방식 익은 토마토가 상하좌우 뿐만 아니라 앞뒤로도 이동하며 다른 토마토를 익게 하기 때문에, 3차원 배열로 문제를 해결했다. import sys data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r') input_data = data_tem..

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