coding- w00se

https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 해당 문제는 너비 우선 탐색(bfs)으로 해결하는 문제입니다. 칸 마다 가장 가까운 상어와의 거리를 안전거리라 하며, 이 문제의 목표는 안전거리의 최댓값을 구하는 것입니다. 문제를 해결하기 위한 접근 방법은 두 가지가 있습니다. 방법 1) 빈 칸 마다 너비 우선 탐색을 통해 안전거리를 계산한 후 안전거리의 최댓값을 구한다. 방법 2) 상어의 위치에서 너비 우선 탐색을 ..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 전체 코드 제출 언어: PyPy3 시간: 1216ms from collections import deque import sys def bfs(adj_list): global adj_mat, type_arr que = deque([(v, 1) for v in adj_list]) while que: cv, ct = que.popleft() type_arr[cv] = ct adj_list ..

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 해당 문제는 구현 문제입니다. 문제의 목표는 규칙에 따라 학생 들의 자리를 배치하고, 학생의 만족도 총합을 계산하는 것입니다. 자리를 배치하는 규칙에 따르면 빈 자리 중 우선순위가 높은 자리는 아래의 순서로 결정됩니다. 주위에 좋아하는 학생 수 가 많음 > 주위에 빈 자리가 많음 > 행의 번호가 작음 > 열을 변호가 작음 따라서 빈 자리를 찾고, 위 우선순위대로 정렬한 후 가장 우선순위..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 해당 문제는 구현 문제입니다. 문제의 목표는 주어진 CCTV를 적절히 회전시켜서 사무실의 사각지대의 최소 크기를 구하는 것입니다. CCTV의 종류는 총 5가지로, 각 종류마다 한 번에 감시 할 수 있는 방향이 다릅니다 CCTV의 종류 마다 감시할 수 있는 방향을 정의하는 방법이 해당 문제에서 중요한 포인트인 거 같습니다. 저는 아래 처럼 정의를 했습니다. dx, dy = (0, 1, 0..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 해당 문제는 구현 문제입니다. 문제의 목표는 k번 회전한 후 각 톱니바퀴의 12시 방향에 있는 극에 따라 점수를 계산하고 점수의 합을 구하는 것입니다. 톱니바퀴가 회전하는 경우는 두 가지로 나뉩니다. 1. 톱니바퀴를 직접 회전시킨다. - 각 회차마다 회전시키는 톱니바퀴가 여기에 해당됩니다. 2. 옆 톱니바퀴에 의해서 회전된다. - 인접한 톱니바퀴가 회전을 한다면 인접 부분의 극을 비교하여 회..

https://www.acmicpc.net/problem/2374 2374번: 같은 수로 만들기 n(1 ≤ n ≤ 1,000)개의 자연수 A[1], A[2], A[3], …, A[n]이 있다. 이 자연수에 Add(i)라는 연산을 하면, A[i]가 1만큼 증가한다. 이때, A[i]만 증가하는 것이 아니고, A[i]의 좌우로 인접한 같은 수의 그룹이 한 www.acmicpc.net 해당 문제는 그리디 알고리즘으로 해결하는 문제입니다. 문제에는 특별한 Add 연산이 소개되며, 이 문제의 목표는 주어진 모든 수를 같게 만들기 위한 최소한의 Add 연산 회수를 구하는 것입니다. Add(i) 연산은 i번째 수와 주변 같은 숫자를 가지는 그룹의 수들을 모두 1씩 증가시키는 연산입니다. Add 연산을 최소로 하여 모든..

https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 해당 문제는 그래프 문제입니다. 문제의 목표는 주어진 모두 승객들을 목적지까지 이동시킨 후 남아 있는 연료를 구하는 것입니다. 단, 택시가 이동하는 중 연료가 바닥이 나거나 승객을 목적지까지 이동시킬 수 없다면 -1을 출력합니다. 이 문제는 두 가지 중요한 조건이 있다고 생각합니다. 조건 1. 다음에 태울 승객을 정할 때는 최단 거리에 있는 승객을 태운다. ..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 해당 문제의 분류는 구현입니다. 이 문제를 두 가지 종류의 해결하는 방법이 있는 거 같습니다. 1) 모든 테트로미노 경우의 수를 구하고 칸마다 대입해보기 2) 이동 거리를 4 칸으로 제한하고 탐색을 진행하기 저는 위 방법 중 2번 방법으로 시도했습니다. 제 코드는 아래와 같습니다. 해당 코드는 Python3로 제출 시 시간 초과가 발생하여 PyPy3로 제출했습니다. 전체 코드 import sys ..

https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 해당 문제는 구현문제입니다. 주사위를 굴려서 각 회차마다 주사위의 윗 면에 쓰인 수를 출력하는 게 이 문제의 목적입니다. 이 문제의 핵심은 주사위의 상태를 저장하는 방법을 구현하는 것이라 생각합니다. 저는 3 X 3 배열에 주사위의 상태를 1 X 6 배열에 각 면에 수를 저장하는 방법을 택했습니다. 주사위의 상태를 저장하는 방법은 ..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 해당 문제는 문제의 설명대로 1) 미세먼지를 확산시킨다. 2) 공기 청정기를 작동시킨다. 이 두 가지를 구현하는 문제이다. 저는 이 문제를 Python3로 제출할 때 시간 초과가 났습니다. 제 코드에 비효율적인 부분이 있는 거 같습니다. 하지만 구현 문제인 만큼 정확성을 확인하고 싶었고 아래의 글을 참고한 후 PyPy3로 제출을 했습니다. https://www.acmicpc.net/board/v..