개발 일지

문제 17144번: 미세먼지 안녕! (acmicpc.net) 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 1 유형이 구현 그 자체인 문제이다. 핵심은 올바르게 지시사항을 구현하는것이다...! 코드가 길어지며 잘못 인덱싱하는 부분은 없는지 신경쓰며 코드를 작성하면 쉽게 해결 가능한 문제이다. from collections import deque # 북 서 남 동 dRow = [-1,0,1,0] dCol = [0,-1,0,1] R,C,T = map(int,input().split()) purifier =..

문제 15685번: 드래곤 커브 (acmicpc.net) 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 풀이 1 역시나 문제를 제대로 읽지 않고 풀어 굉장히 많은 시간을 허비했다. 제한조건에 보면 0 ≤ x, y ≤ 100 으로 주어지는데, 내 마음대로 0 ≤ x, y < 100 로 풀면서 "맞왜틀?" 하고 있었다. 이것 외에도 끝점을 기준으로 90도 돌린다는 의미를 방향벡터를 그저 시계방향으로 90도 꺾는다는 것으로 접근해서 틀리기도 했다. 아무튼 끝점에서 이전의 점들의 방향벡터를..

문제 15684번: 사다리 조작 (acmicpc.net) 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이 1 최대 3개 만큼 사다리를 놓아보며, 모든 i 번째 사다리의 도착지점이 i 인 경우 중 사다리를 가장 적게 놓는 경우를 찾아야 한다. 사다리를 타고 내려가는 상황을 이차원 리스트로 구현해야겠다는 판단을 떠올리는게 핵심이며, 이후엔 백트래킹으로 사다리를 놓아보면서 정해진 개수만큼 사다리를 다 놓으면 원하는 결과가 나오는지 확인하는 전형적인 부르트포스 혹은 탐색 문제가 된다. 이번 문제에선 다음과 같은..

문제 16235번: 나무 재테크 (acmicpc.net) 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 풀이 1 이 문제에서는 두가지의 교훈을 얻을 수 있다. "아기 상어" 문제에서 얻은 교훈과 마찬가지로, 일단 탐색은 모든 경우를 탐색하며 조건문으로 거르는 방식을 시도해본뒤, 시간 초과가 나면 그 다음에 미리 풀을 좁혀놓고 탐색하는 방법을 시도하자는 것이다. 즉, 일단 볼것도없이 행-열 탐색을 싹다 해버려야지, 미리 좌표를 뽑아놓고 반복문을 돌리지 말자는 것이다! 이 문제의 경우, 한 곳에 ..

문제 15683번: 감시 (acmicpc.net) 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 1 각 감시카메라를 네 방향으로 돌려보며 전체 보드에서 빈 칸의 개수가 최소가 되게하는 경우를 찾는 전형적인 백트래킹, DFS 문제이다. 큰 구조는 미리 구해놓은 감시카메라 좌표를 백트래킹 하며, 네 방향씩 돌려보는 것이다. 카메라의 방향이 90도 돌아가는 것은 0,1,2,3을 각각 북,동,남,서라고 했을 때 1씩 더해주기만 하면 된다. 이때 감시카메라가 감시하는 영역은 서로 겹칠 수 있으므로, 백..

진행 방향을 꺾어주는것이 포인트인 문제이다. 반대로 돌아가는 경우, 왼쪽으로 꺾는 경우, 오른쪽으로 꺾는 경우가 존재하며, 각 블록은 들어오는 방향에따라 꺾이는 방향이 달라진다. 이를 코드 상단에 보이는 것과 같이 딕셔너리로 표현 가능하며, 핀볼이 이동하는 것은 재귀 함수로도 구현이 가능하나, depth error가 발생하기 때문에 반복문으로 나타내야 한다. 간단하지만 상당히 재밌는 문제라고 생각한다. # 북 서 남 동 dRow = [-1,0,1,0] dCol = [0,-1,0,1] # 북 서 남 동 # 0:back 1:right 2:left blocks = { 1 : [0,1,2,0], 2 : [1,2,0,0], 3 : [2,0,0,1], 4 : [0,0,1,2], 5 : [0,0,0,0] } def ..

문제 14891번: 톱니바퀴 (acmicpc.net) 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 풀이 1 문제를 잘 읽어보면, 회전을 하기전에 먼저 인접 톱니들이 받는 영향을 고려해야함을 알 수 있다. 따라서 이 문제는 재귀함수로 접근하면 쉽게 풀린다는 점을 알 수 있다. 또한, 톱니를 회전하는 것은 deque 를 이용하면 매우 쉽게 구현 가능하다. from collections import deque sawtooth = [] for _ in range(4): sawtooth.append(deque(..

문제 17143번: 낚시왕 (acmicpc.net) 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 풀이 1 첫 번째 문제를 모두 읽고, 큰 틀을 먼저 잡는다. 구조적인 틀은 조건을 그대로 구현하면 된다. 낚시왕이 오른쪽으로 한 칸 이동한다. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다. 상어가 이동한다. 낚시꾼이 땅에서 가장 가까운 상어를 잡는것을 구현하는 가장 직관적인 접근은, 평소처럼 board를 만들어 열->행 ..

문제 16236번: 아기 상어 (acmicpc.net) 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 1 총 두가지 방법으로 시도했다. 첫 번째는 미리 먹잇감들의 좌표들을 집합안에 넣어놓고 아기상어가 잡아먹을 때 마다 해당 좌표를 집합에서 제거하는 방식이고, 두 번째는 매번 남아 있는 먹잇감을 전부 탐색하는 방식이다. 결과 부터 말하자면 두 번째 방식이 훨씬 적은 실행속도를 보여줬는데, 그 이유는 보드 위에 빈칸(0) 이 압도적으로 많지 않은 이상 미리 집합안에 좌표를 넣어놓나 매번 탐색하나 탐색..

문제 14890번: 경사로 (acmicpc.net) 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 1 조건들을 잘 검토하고, 이를 구현해야하는 문제이다. 구현 문제에서는 조건을 잘 정리할 필요가 있다는 점을 명심해야한다. 높이가 1보다 크게 차이나면 경사로를 놓을 수 없으므로, 지나갈 수 없다. 현재 탐색중인 곳을 기준으로, 높이가 이전보다 1만큼 크다면 이전에는 길이 l 만큼의 평평한 땅이 확보되어 있어야한다. 현재 탐색중인 곳을 기준으로, 높이가 이전보다 1만큼 작다면 이후로 길이 l 만큼의 평평한 땅이 확보되어야 한다. ..