브루트포스
-
[백준] 17070번 파이프 옮기기 1 (by Python)Programming/Algorithm 2021. 4. 8. 22:52
문제 www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 처음에는 직관적으로 생각나는 대로 다음과 같이 BFS로 풀었다. import sys from collections import deque input = sys.stdin.readline n = int(input()) arr = [list(map(int, input().split())) for _ in range(n)] q = deque() q.append([(0, 0), (0..
-
[백준] 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 = ..
-
[백준] 14889번 스타트와 링크 (by Python)Programming/Algorithm 2021. 3. 2. 17:42
문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 첫 번째 풀이 처음 생각하게 된 풀이는 브루트 포스 방식입니다. itertools의 combination을 이용해 가능한 조합들을 모두 구하고 그에 따른 각 팀의 능력차를 구하는 방법인데, 여기서 (1, 2, 3, 4) / (5, 6, 7, 8)로 팀이 나뉘었을 때와 (5, 6, 7, 8) / (1, 2, 3, 4)로 팀이 나뉘었을 때를 별도의 경우로 보면 시간복잡도가 더 커지므로 이를 해소하기 위해 우리 팀에는..
-
[백준] 14500번 테트로미노 (by Python)Programming/Algorithm 2021. 1. 26. 12:07
문제 문제를 읽으면 바로 모든 경우의 수를 시도해보는 브루트 포스 방식으로 풀어야 함을 알 수 있다. 그렇지만 고민이 되는 부분은 어떻게? 인 것 같다. 어떻게 회전도, 뒤집기도 가능한 테트로미노의 모양을 모두 테스트해볼 수 있을까? 더 나은 방법이 있을 거란 생각이 들었지만 일단 내가 시도해본 방법은 다음과 같다. 첫 번째 풀이 n, m = map(int, input().split()) array = [] answer = 0 shapes = [[(0, 0), (0, 1), (1, 0), (1, 1)], [(0, 0), (0, 1), (0, 2), (0, 3)], [(0, 0), (1, 0), (2, 0), (3, 0)], [(0, 0), (1, 0), (1, 1), (2, 1)], [(0, 0), (1..