개발 일지

문제 15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 사다리 조작 문제와 동일한 조합 문제이다. 치킨집을 최대 M개 까지 남길 수 있고, M개 이하의 가능한 조합을 짜보면서 최소가 되는 도시 치킨 거리를 갱신한다. 치킨집은 최대 13개, 가정집은 최대 2N개 까지만 존재할 수 있으므로 따로 좌표를 리스트에 넣어놓고 1차원 리스트에 대해 조합을 짜도 된다. N,M = map(int,input().split()) board = [[0]*(..

문제 23290번: 마법사 상어와 복제 (acmicpc.net) 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 풀이 물고기의 이동 제한 조건은 상어의 존재, 보드 경계 그리고 냄새이다. 냄새는 생성되는 턴에 한번, 그리고 그로부터 두턴 더 남아있기 때문에 총 세번의 반복문을 돌고나면 0이된다는 점에 주의하자. 상어는 최적의 이동경로를 먼저 탐색한 뒤 그 경로를 따라 이동한다. 경로 탐색은 이동경로에 있는 물고기 숫자의 합과 이동경로 자체에 의해 결정되는데, 이는 heapq를 ..

문제 17142번: 연구소 3 (acmicpc.net) 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 풀이 1 이 문제는 언뜻 보면 지금껏 풀어온 탐색문제와 크게 다를것이 없어보이지만, 함정(?)이 숨겨져있어 주의가 필요하다. 문제를 자세히 읽어보며 어떻게 다른지 잘 파악해야 시간낭비없이 제대로된 설계로 문제를 풀이할 수 있다. 문제에서 원하는 상황은 "모든 빈 칸"에 바이러스가 퍼지는 상황이다. 따라서 바이러스 전염 구현이 끝나면 board를 탐색하며 '빈 칸'이 남아있는지 확인할 필요가 있는데, 답이 되는 '최소 ..

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

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

문제 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(..

문제 14889번: 스타트와 링크 (acmicpc.net) 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 1 itertools 모듈을 쓰지 않고 푸는데 의의가 있는 문제이다. 모든 선수들은 두 그룹으로 나뉘는데, 첫번째 선수를 포함한 그룹과 그렇지않은 그룹이다. 선수를 n/2 만큼 모으면, get_point 메서드를 통해 점수를 계산하고 두 팀의 점수차를 구한다. import sys input = sys.stdin.readline n = int(input()) s = [] for _ in range(n): s.append(l..

문제 14500번: 테트로미노 (acmicpc.net) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 1 언뜻 보면 흔한 DFS 문제같지만... 사실 아니다! 테트로미노 중 오른쪽 하단에 보이는 모양은 흔히 쓰는 '한 칸 씩 전진하는 DFS'로 만들수 없기 때문이다. 따라서 총 세가지 방법 정도를 생각할 수 있고, 두 가지 방법을 이용해 풀이했다. DFS DFS로 만들 수 없는 모양을 제외한 모든 모양을 DFS로 만들어 탐색하고, 문제의 'ㅏ' 모양에 대해서만 90도 씩 회전하며 탐색한다. 2700ms의..

문제 12100번: 2048 (Easy) (acmicpc.net) 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 1 슬라이드를 최대 5번 해서 얻을 수 있는 가장 큰 블록을 출력해야 하는 문제이다. 가장 큰 값 찾기 가장 먼저 알아차려야 하는 것은, 슬라이드를 한 후의 가장 크기가 큰 블록은 이전 상태의 가장 크기가 큰 블록보다 같거나 크다는 것이다. 따라서 슬라이드를 5번까지 한 4^5 = 1024개의 보드들의 숫자들을 전부 탐색하며 최대값을 찾아내면 되고, 그 연산량은 1..

문제 설명 개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다. 대기실은 5개이며, 각 대기실은 5x5 크기입니다. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다. 예를 들어, 위 그림처럼 자리 사이에 파티션이 존재한다면 맨해튼 거리가 2여도 거리두기를 지킨 것입니다. 위 그림처럼 파티션을 사이에 두고 앉은 경우도 거리두기를 지킨 것입니다. 위 그림처럼 자리 사이가 맨해튼 거리 2이고 사이에 빈 테이블이 있는 경우는 거리두기를..