개발 일지

문제 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 만큼의 평평한 땅이 확보되어야 한다. ..

문제 14503번: 로봇 청소기 (acmicpc.net) 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 1 재귀함수를 이용한 기본적인 구현문제이다. DFS도, BFS도 아니고 구현 항목을 따라 작성하면 된다. 재밌는 문제라 따로 기록해둔다. import sys input = sys.stdin.readline n,m = map(int,input().split()) r,c,d = map(int,input().split()) board = [] for _ in range(n): board.append(lis..

문제 14499번: 주사위 굴리기 (acmicpc.net) 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 풀이 1 주사위만 구현할 수 있으면 되는 문제이다. 주어진 전개도가 힌트가 되는데, 전개도에서 가로줄, 세로줄을 각각 deque로 놓고 rotate한다고 생각하면 주사위 굴리기가 쉽게 구현된다. 다른것보다 전개도를 이용해 주사위를 구현하는것이 가장 핵심이 됐던 문제라고 생각한다. from collections import deque n,m,..

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