본문 바로가기

⭐ Problem_Solving/백준30

[백준] 17471 게리맨더링 (Python/파이썬) https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 1. 부분집합 / 조합을 통해서 두 선거구를 구한 다음, 해당 선거구 내의 인구수와 구역수를 계산해서 모든 구역이 포함되었을 경우에만 정답을 갱신해주면 된다. 2. 조합을 구할 때 어차피 조합에 포함되지 못한 구역들이 다른 선거구에 포함되기 때문에 N//2까지만 조합을 구해도 된다. 3. 그러나 N까지 모든 조합을 구해도 별 문제 없이 시간 내에 통과 된다. from collections import deque fro.. 2022. 10. 14.

[백준] 16236 아기상어 (Python/파이썬) https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 구현 문제이다. 나같은 경우는 처음에 최대 O(N^6)의 코드로 pypy(1076ms)로 통과 (python 시간초과)하고 이후에 jh05013님의 풀이를 참고하여 훨씬 빠른 풀이(python: 288ms)로 다시 풀었는데 두 가지 모두 소개해보겠다. 가장 중요한 것은 상어가 다음 먹이를 찾아가는 과정을 구현하는 것인데, 여기서 '가장 거리가 가까우며, 거리가 같을 경우 왼쪽 상단에 있는 .. 2022. 10. 13.

[백준] 12100 2048 (Easy) (Python/파이썬) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 1. N이 20 이하이고 시행이 5번으로 고정되어 있어서 백트래킹을 이용한 완전탐색으로 문제를 풀 수 있다. 2. 블럭의 병합 / 이동 2가지를 상하좌우 4방향으로 구현해야되는데 나는 한 방향에 대해서만 구현하고 나머지는 배열을 회전 시켜서 적용하는 법을 이용했다. (참고: https://bluuubery.tistory.com/48?category=584396) 3. .. 2022. 10. 11.

[백준] 18405 경쟁적 전염 (Python/파이썬) https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 1. 토마토랑 비슷하게 처음에 바이러스의 좌표를 큐에 저장해두고 bfs를 돌리면된다. 2. 단 이 문제에서는 낮은 번호의 바이러스부터 전염된다는 특성이 있으므로 bfs 돌리기 직전에 큐를 한번 정렬해줘야 한다. from collections import deque import sys, os, io, atexit input = lambda: sys.stdin.readl.. 2022. 10. 10.

[백준] 17142 연구소 3 (Python/파이썬) https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 1. 연구소 2랑 매우 유사하나 비활성 바이러스의 처리가 생각보다 까다롭다 2. 활성바이러스와 만나면 활성 상태로 변하니 '1'의 성질을 가지면서, 동시에 확산 시간에는 영향을 미치지 않으므로 '0'의 성질을 가지게 된다. 3. 여러가지 방법이 있겠지만 나 같은 경우는 비활성 -> 활성 바이러스의 좌표를 저장하면서 탐색하다가 마지막에 0으로 초기화해줌으로써 확산 시간 계산에 영향을 안 미치도록 했다. fr.. 2022. 10. 7.

[백준] 1766 문제집 (Python/파이썬) https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 1. 우선순위큐로 위상정렬을 수행하면 되는 문제이다. 2. 문제의 조건을 읽어보면 비교적 명확하다. - 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. -> 위상정렬 - 가능하면 쉬운 문제부터 풀어야 한다. -> 우선순위 큐 3. 위상정렬 공부하면서 푼 문제였는데 위상정렬임을 알고 풀어서 그런지 몰라도 난이도에 비해서.. 2022. 10. 6.

이전 1 2 3 4 5 다음

티스토리툴바