본문 바로가기
728x90

브루트포스

[백준알고리즘] 1080번: 행렬 -Python [백준알고리즘] 1080번: 행렬 -Python https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 코드가 조금 지저분해보이기는 하지만 그리디 알고리즘을 사용했다. 반복문을 사용하지 않고 재귀를 통해서 문제를 해결했다. DFS방식의 재귀 깊이 때문에 런타임에러가 발생했었고, 모든 경우에 대해서 3x3을 변환시키고, 다시 원상태로도 진행을 하는 2가지 방법을 적용했었기 때문에 시간 초과가 발생했었다. 시간 초과가 발생한 경우에 대해서 더 설명을 하자면, 현재 위치.. 더보기
[백준알고리즘] 15686번: 치킨 배달 -Python [백준알고리즘] 15686번: 치킨 배달 -Python https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net 브루트 포스 방식으로 문제를 풀 수 있었다. 모든 집에서 최대 m개의 치킨집을.. 더보기
[백준알고리즘] 14889번: 스타트와 링크 -Python [백준알고리즘] 14889번: 스타트와 링크 -Python 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 브루트 포스방식으로 문제를 풀었다. N//2명의 인원씩 A, B팀으로 나누어주었다. 이때 모든 팀원 배치를 하기 위해서 itertools의 combinations를 사용했다. 구한 팀 배치마다 각 팀원들의 모든 팀 능력치를 합해주기 위해서 이중 for문을 돌렸다. from sys import maxsize from itertools import combinat.. 더보기
[백준알고리즘] 14502번: 연구소 -Python [백준알고리즘] 14502번: 연구소 -Python https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 20200423 아래에 PyPy3로만 통과한 코드를 추가했다. PyPy로만 통과가 됐지.. 더보기
[백준알고리즘] 14501번: 퇴사 -Python [백준알고리즘] 14501번: 퇴사 -Python https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 퇴사하기 전까지 가장 많은 돈을 벌 수 있도록 해야 한다. 며칠에 걸리는 상담인지에 따라 며칠간 상담을 추가로 할 수 없을 수도 있다. 나는 dp처럼 문제를 풀었다. 1일 차부터 순서대로 선택을 하면서 각 날짜의 일을 했을 때 최대로 벌 수 있는 금액을 유지한다. 그리고 이 최대로 벌 수 있는 금액에 다음에 할 수 있는 일 들의 금액을 더하면서 유지한다. 음... 코드를 보는 게 설명보다 쉬워 보인다... 배열로 비교를 해보도록 하자. 처음의 값은 다음과 같다. data = [(3, .. 더보기
[백준알고리즘] 1107번: 리모컨 -Python [백준알고리즘] 1107번: 리모컨 -Python https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다. www.acmicpc.net 브루트 포스로 해결해야 하는 건지 모르고 이상하게 풀었었다... 조건을 다 맞추려고 하다 보니 오류가 계속 발생하고 통과가 안 되는 반례가 계속 존재했다. 이 문제의 경우에는 MAX가 500000으로 depth도 얕기 때문에 recursion depth도 6으로 낮고, 0~9.. 더보기
[백준알고리즘] 7568번: 덩치 -Python [백준알고리즘] 7568번: 덩치 -Python https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x,y), (p,q)라고 할 때 x>p 그리고 y>q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56,177), (45,165) 라고 한다면 A의 덩치가 B보다 큰 www.acmicpc.net 시험 끝난 기념으로 오랜만에 알고리즘을 풀어야지~라고 생각하고 쉬운 브포부터 건드려봤다. 이번.. 더보기
728x90

티스토리툴바