개발 일지

문제 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다. 파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다. (r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다. 아..

문제 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼쪽 위에 있는 칸의 좌표는 (1, 1)이고, 가장 오른쪽 아래에 있는 칸의 좌표는 (N, M)이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 각 면에는 1보다 크거나 같고, 6보다 작거나 같은 정수가 하나씩 있다. 주사위 한 면의 크기와 지도 한 칸의 크기는 같고, 주사위의 전개도는 아래와 같다. 2 4 1 3 5 6 주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (1, 1) 이다. 지도의 각 칸에도 정수가 하나씩 있다...

문제 19238번: 스타트 택시 (acmicpc.net) 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 1 문제에는 명시되어 있지 않지만, 각 손님의 출발지점은 다르지만 도착지점은 같을 수 있다. 처음에는 각 손님에 대해서 거리를 구해 heapq에 넣었지만, 시간초과가 발생한다. 택시의 위치부터 보드 전체를 탐색하며 남아있는 손님을 탐색하면 시간초과가 발생하지 않는다. 여러 제한 조건들을 유의해서 풀이해야하는 문제이다. from collections import d..

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

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

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

문제 설명 다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다. 지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다. 만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다. 단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없습니다. 즉, 위 그림처럼 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없습니다. 다음 그림과 같이 지형이 2개 이상으로 분리된 경우도 없습니다. 한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없습니다. 지형을 나타내는 직사각형이 담긴 2차원 배..

문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로..

문제 설명 로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다. 로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이..