명왕성의 공전기록

https://www.acmicpc.net/problem/20040 해당 문제는 첫줄에는 점의 갯수 n과 연결된 선분의 갯수 m, 그리고 다음 줄부터 게임의 진행 상황이 주어진다. 게임의 진행 상황은 a점, b점이 연결되었음을 말하며, 만약 사이클이 완성된 경우 완성된 진행상황의 순번을 출력, 사이클이 완성되지 않은 경우 0을 출력하면 된다. 문제 풀이 방식 사이클에 힌트를 얻어 최소 스패닝 트리 문제에서 사용하던 find-union 알고리즘을 활용했다. 게임 진행 상황에 따라 a점과 b점을 병합(union)하되, 병합하기 전 각각의 a,b가 같은 루트 노드를 가지고 있을 경우(find) 현재 진행 순번을 출력하고 마무리하는 방식으로 구현했다. 전체 소스 코드 const fs = require("fs")..

https://www.acmicpc.net/problem/23757 문제에서는 선물의 갯수가 담긴 상자, 아이들이 원하는 선물의 양을 담은 배열이 주어진다. 아이들이 현재 선물이 가장 많이 담겨 있는 상자에서 각자 원하는 만큼 선물을 가져갈 때 모두 각자 원하는 선물을 가져갈 수 있다면 1, 그렇지 않다면 0을 출력하는 문제다. 문제 풀이 방식 현재 가장 많은 선물이 담겨 있는 상자를 효율적으로 찾기 위해서는 힙의 구현이 필요했다. python에서는 내장 모듈에서 불러와 사용할 수 있으나, 기본적으로는 최소 힙만 제공하기 때문에, heap에 데이터를 음수로 넣어줌으로써 최대 힙으로의 역할을 가능하게끔 했다. 이후, 힙에 있는 가장 많은 선물을 가지고 있는 상자와 아이가 원하는 선물의 양과 비교한 뒤, 만..

https://www.acmicpc.net/problem/18511 문제 설명 주어진 집합으로 n보다 작으며 가장 큰 수를 구하는 문제다. 문제 풀이 방식 재귀를 활용하여 만들 수 있는 모든 경우를 구한 뒤 출력하는 방식으로 구현했다. import sys data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r') input_data = data_temp.read().splitlines() def solution (data) : arr = [list(map(int, v.split())) for v in data] [T,N],numbers = arr storage = [] def recursive (n) : if n > T : retu..

https://www.acmicpc.net/problem/1303 문제는 가로 세로 크기인 n, m과 각 병사들의 옷 색상이 주어진다. 이때, 뭉쳐있는(상하좌우가 연결된) 병사들의 전투력은 n^2 라고 했을 때 각 팀의 전투력의 총합을 출력하면 된다. 문제 해결 방식 해당 문제에서는 DFS 알고리즘이나 BFS 알고리즘이나 큰 차이가 없을 것 같아 BFS 알고리즘으로 구현했다. 일반적인 BFS 알고리즘에 옷 색상을 인자로 던져주며, 같은 색 옷을 찾은 뒤 뭉쳐 있는 병사들의 수를 구하고 이를 제곱하여 리턴하는 방식으로 구현했다. 전체 소스 코드 import sys data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r') input_..

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