명왕성의 공전기록

https://www.acmicpc.net/problem/2578 문제는 데이터로 빙고판에 써져 있는 수와 사회자가 부르는 수가 주어질 때, 사회자가 몇 번째 수를 부를 때 빙고가 3개 이상이 되는지 묻는다. 문제 풀이 방식 문제는 단순하게 접근했다. 먼저 빙고판에 적혀 있는 숫자들의 좌표를 저장하는 테이블을 만들고, 해당 숫자가 불렸는지 확인할 2차원 배열을 만들었다. (기본값은 false) 이후 사회자가 숫자를 부를 때마다, 테이블에 저장되어 있는 해당 숫자의 좌표에 맞게 2차원 배열의 해당 좌표 위치를 true로 수정했다. 그리고 이때마다 빙고가 3개 이상인지 검증하여 빙고가 3개 이상일 경우 정답을 출력토록 했다. 전체 소스 코드 const fs = require("fs"); const input..

https://www.acmicpc.net/problem/20364 문제 해결 방식 각 정점의 부모는 정점 번호 // 2 (2로 나눈 뒤 소숫점 버림)이라는 규칙을 가지고 있기 때문에, 해당 정점에서 위로 올라가는 식으로 로직을 구현했다. 이때, 만약 방문하는 정점이 누군가가 이미 위치한 땅이라면 해당 땅 번호를 리턴하고, 최정점 루트인 1에 도달할 때까지 누군가 선점한 땅을 마주치지 않는다면, 해당 정점을 기록하고 0을 리턴하도록 했다. 전체 소스 코드 import sys data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r') input_data = data_temp.read().splitlines() def solution..

https://www.acmicpc.net/problem/10844 문제는 문제에서 제시된 것처럼 모든 자리의 차이가 1인 계단수의 갯수를 출력하는 문제다. 문제 풀이 방식 1 ~ 8까지의 수는 각각 2개의 수 (예를 들어 1의 경우 0과 2가 다음에 올 수 있는 계단수)를 가진다고 할 때, 0과 9는 각각 1과 8밖에 계단수를 갖지 못한다는 점으로 점화식을 수립하여 로직을 구현했다. 단 1의 자리 수의 경우는 먼저 0이 올 수 없으므로 이 점만 유의하면 된다. import sys data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r') input_data = data_temp.read().splitlines() def solut..

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