명왕성의 공전기록

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

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