개발 일지

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

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

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

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

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

문제 13460번: 구슬 탈출 2 (acmicpc.net) 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 1 다음 문제와 상당히 유사하다는 것을 알 수 있다. 블록 이동하기 (lv3) (tistory.com) 블록 이동하기 (lv3) 문제 설명 로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x forteqook.t..

문제 3190번: 뱀 (acmicpc.net) 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 1 뱀의 머리가 벽 또는 자신의 몸에 닿으면 프로그램이 종료되어야 하므로, deque에 뱀이 차지하고 있는 좌표들을 넣는것이 핵심이다. 또한 보드의 크기가 최대 100까지로 제한되어 있는 것에 착안하여 뱀을 1초 씩 이동시키며 주어진 조건을 확인 하는 완전탐색의 방법이 유효하다는 것을 알 수 있다. 처음에 입력된 방향 변환 정보를 모두 사용하고, 이후로는 방향 전환이 없으므로 바라보고 있는 방향으로 직진하여 벽 또는 ..