백준
-
[백준] 1062번 가르침 (by Python)Programming/Algorithm 2021. 3. 24. 17:13
문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 브루트 포스 방식으로 푸는 비트마스킹 문제이다. 처음에는 비트마스킹 방식이 익숙하지 않아서 set으로 시도해봤으나 시간 초과의 벽에 막혀 비트마스킹 방법으로 풀게 되었다. import sys from itertools import combinations input = sys.stdin.readline def convert(x): return ord(x) - ord('a') def..
-
[백준] 18404번 현명한 나이트 (by Python)Programming/Algorithm 2021. 3. 14. 15:33
문제 https://www.acmicpc.net/problem/18404 18404번: 현명한 나이트 첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. ( www.acmicpc.net 풀이 움직이는 방식이 일반적인 상하좌우가 아니라 체스의 나이트가 움직이는 방식이라는 점에서 차별화되는 BFS 문제이다. 이에 맞추어 step 리스트를 다르게 바꾸어주었다. 또한, 목적지가 하나가 아님에 따라 하나를 찾을 때마다 체크하고 다 찾은 경우에는 while loop을 탈출하도록 코드를 짜주었다. from collections import deque..
-
[백준] 18310번 안테나 (by Python)Programming/Algorithm 2021. 3. 14. 15:28
문제 https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 풀이 무척 쉬워보이고, 코드 또한 4줄로 매우 간단하게 풀 수 있는 문제이지만 개인적으로 해답을 떠올렸음에도 확신하지 못해 많이 애먹은 문제이다. 결론적으로 답은 주어진 숫자들을 오름차순으로 정렬한 후의 가운뎃값이다. 어떻게 이 결론이 성립하는지 예시를 통해 알아보도록 하자. 오름차순으로 정렬된 숫자 5개 (a, b, c, d, e)가 있고 a, b / b, c / c, d / d, e 의 거리를 각각 x_1, x..
-
[백준] 3665번 최종 순위 (by Python)Programming/Algorithm 2021. 3. 14. 02:25
문제 www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 풀이 위상 정렬(Topology Sort)를 사용하는 문제이다. 주어진 올해 순위를 순위가 낮은 팀이 높은 팀을 가리키는 유향 그래프로 나타내었다. 원래는 위상 정렬에 쓰이는 그래프는 인접 리스트로 구현하였는데, 이번에는 방향성이 유동적이므로 이를 잘 다루기 위해 인접 행렬로 구현했다. 바뀐 순위들에 대해서 edge의 방향을 바꾸어주고 이에 대해 위상 정렬을 시행해주면 된다. 다만 주어지는 정보에 ..
-
[백준] 2887번 행성 터널 (by Python)Programming/Algorithm 2021. 3. 13. 23:36
문제 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 문제를 보고 사이클을 생성하지 않는 범위 내에서 비용이 적은 순으로 edge를 (v - 1)개까지 선택하는 크루스칼 알고리즘이라는 걸 알 수 있다. 나는 처음에 min(|xA-xB|, |yA-yB|, |zA-zB|) 라고 제시된 각 edge의 비용을 모든 A와 B에 대해 계산하여 시간 초과를 마주하게 되었다. 그리고 좀 더 고민해본 결과 모든 좌표들의 x..
-
[백준] 6064번 카잉 달력 (by Python)Programming/Algorithm 2021. 3. 7. 20:33
문제 https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 풀이 from math import gcd import sys input = sys.stdin.readline t = int(input()) for _ in range(t): m, n, x, y = map(int, input().split()) if n > m: m, n = n, m x, y = y, x k = x y = 0 if n == y else y end = (m * n) // gcd(m..
-
[백준] 1248번 맞춰봐 (by Python)Programming/Algorithm 2021. 3. 7. 20:24
문제 https://www.acmicpc.net/problem/1248 1248번: 맞춰봐 첫째 줄에 수열의 크기 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 N(N+1)/2 길이의 문자열이 주어진다. 처음 N개의 문자는 부호 배열의 첫 번째 줄에 해당하고, 다음 N-1개의 문 www.acmicpc.net 풀이 def backtrack(k, stack): temp = k candidates = range(-10, 11) for i in range(k + 1): now = a[temp] if now == '+': candidates = [c for c in candidates if (sum(stack[i:k]) + c) > 0] elif now == '-': candidates = ..
-
[백준] 1525번 퍼즐 (by Python)Programming/Algorithm 2021. 3. 5. 17:52
문제 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 풀이 from collections import deque s = '' goal = '123456780' for _ in range(3): s += ''.join(input().split()) visited = {s: True} adj = [[1, 3], [0, 2, 4], [1, 5], [0, 4, 6], [1, 3, 5, 7], [2, 4, 8], [3, 7], [4, 6, 8], [5, 7]] ans = -1 time = 0 q = deque() q.append(..