구름을 채우다

문제 보기 이 문제는 시뮬레이션 문제이다. 처음에 문제를 읽자마자 든 생각은 두 가지였다. collections 모듈의 Counter 자료구조를 사용해야겠다. 행과 열에 대한 연산이 있으므로, 열에 대한 연산은 A 행렬을 transpose 시켜야겠다. 이 두 가지 생각을 잘 구현하니 AC를 받았다. 문제를 푼 로직은 다음과 같다. 행렬 A를 초기 상태의 3 * 3 행렬로 초기화한다. (5~9번째 줄) R연산) A의 각 행마다 (숫자, 숫자가 나타난 횟수)의 리스트를 생성하고, 그 리스트에 대해 (숫자가 나타난 횟수, 숫자) 순으로 오름차순으로 정렬한다. (17번째 줄) R연산) 정렬된 0이 아닌 숫자들을 해당하는 A의 행에 새롭게 대입시킨다. (19~24번째 줄) R연산을 통해 바뀐 열의 최대 길이를 갱..

문제 보기 이 문제는 시뮬레이션 문제이다. 생각보다 쉬워보였는데 문제를 해결하는데 하루 2시간씩 총 3일이 걸렸다. (정말 바보같았다.) 처음에는 객체지향적으로 상어 클래스를 만들고 상어들의 배열을 만들어서 선형적인 시간복잡도로 문제를 해결하려고 했지만, 딱히 그럴 필요가 없을 것 같아서 그냥 2차원 배열의 각 원소들에게 상어의 정보를 할당하였다. 문제를 푼 로직은 다음과 같다. 2차원 배열에 상어에 대한 정보를 저장한다. (30~33번째 줄) 어부를 이동시킨다. (38~39번째 줄) 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다. (40~45번째 줄) 상어가 이동한다. (각 상어가 이동할 때마다 이동한 상어의 정보를 새로운 2차원 ..

문제 보기 이 문제는 시뮬레이션 문제이다. 처음에 문제를 훑고 나서 BFS 문제라고 생각했지만, 자세하게 문제를 읽어보니 나무 재테크와 비슷한 문제였다. 문제를 풀 때 주의할 점은 먼지를 확산시킬 때, 먼지를 확산시킬 칸들의 정보를 저장해두었다가, 모든 칸의 먼지의 양을 줄이고 나서 확산시켜야 한다. (이는 나무 재테크 문제에서처럼 똑같이 적용되는데, 각 칸을 순회할 때 먼지를 확산시켜 먼지의 양을 주변 칸에 더해버리면 다음 칸에서 확산시킬 먼지의 양에 영향을 끼친다.) 문제를 푼 로직은 다음과 같다. 공기청정기의 위치를 찾는다. (8~12번째 줄) 각 칸에서 미세먼지를 확산시킬 인접한 칸들을 찾고, 그만큼 현재 칸의 미세먼지의 양을 줄인다. 동시에 인접한 칸들의 위치를 큐에 저장한다. (18~32번째 ..

문제 보기이 문제는 백준에 알고리즘 분류가 따로 되어있지 않지만 나는 BFS로 푼 문제이다.상어가 먹을 물고기를 찾기 위해서 BFS를 사용하였고, 상어가 어디로 이동할 지 결정하는 방법은 다음과 같다.먹을 물고기를 정하기 위해서 나는 우선순위 큐(Priority Queue)를 사용했다.문제를 풀기 위한 로직은 다음과 같다. 1. 현재의 상어위치로부터 BFS를 시작한다. (17~20번째 줄)2. BFS를 진행하면서, 상어가 지나갈 수 있으면 현재까지의 거리, 행과 열을 큐에 넣고, 먹을 수 있는 물고기가 있으면 우선순위 큐에 우선순위를 현재까지의 거리, 행, 열 순으로 삽입한다. (30~36번째 줄)3-1. 우선순위 큐가 비어있으면(=먹을 수 없는 물고기가 없으면) 종료한다. (38~40번째 줄)3-2. ..

문제 보기백준에 이 문제는 따로 알고리즘 분류가 없지만, 나는 BFS로 푼 문제이다. 두 나라의 인구가 이동하는 조건은 다음과 같다.위에 해당하는 단계들이 1번의 인구이동이다.여기서 실수할 수 있는 부분이 있다.나는 문제를 풀 때, 한 개의 연합국에서 인구이동이 끝날 때 1번의 인구이동이라고 카운트를 세었지만, 정답은 주어진 맵에서 가능한 모든 연합국들의 인구이동이 끝나는 것이 1번의 인구이동이었다.따라서 문제를 해결하기 위한 로직은 다음과 같다. 1. 주어진 맵의 각 위치마다 BFS를 진행한다. 이 때, 한 번의 인구이동동안 연합국에 해당하는지 확인하기 위한 집합 변수(unions)를 둔다. (11번째 줄)2. 연합국이 아닌 모든 나라들에 대해서 BFS를 진행한다. (12~33번째 줄)3. 한 번의 B..

문제 보기이 문제는 시뮬레이션 문제이다.처음에 이 문제에서 요구하는 바가 무엇인지 이해를 하지 못했다.. 그러나 문제를 이해하고 나니 구현은 매우 쉬웠다.드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있다. 1. 시작 점2. 시작 방향3. 세대 (Generation) 다음 세대로 넘어갈 때마다 변화하는 드래곤 커브는 문제의 설명을 보면 이해할 수 있다.드래곤 커브의 진행방향은 다음과 같이 정의되어 있다.드래곤 커브의 방향을 살펴보면 다음과 같은 규칙이 있다.0세대: 01세대: 01 -------------- 0 12세대: 0121 ----------- 01 213세대: 01212321 ------ 0121 2321 위의 규칙을 보면, 다음 세대의 드래곤 커브는 현재 세대의 드래곤 커브에서 거꾸로 ..

문제 보기이 문제는 브루트 포스 문제이다. n의 범위가 50이하이고, 선택해야하는 치킨집의 갯수가 13이하이므로, 브루트포스임을 유추할 수 있다.나는 처음에 문제를 제대로 이해하지 못해서 BFS 문제라고 생각했다. 하지만 모든 경우의 수를 따져봐야 하기때문에, 브루트포스임을 나중에 깨달았다.문제에서 주어지는 정의는 다음과 같다. 치킨거리: 집과 가장 가까운 치킨집까지의 거리도시의 치킨거리: 모든 집의 치킨거리의 합 최대 M개의 치킨집을 고르고, 최솟값이 되는 도시의 치킨거리를 구해야한다.따라서 주어진 모든 치킨집에서 m개를 선택하는 조합(Combination)을 사용해야한다.문제를 해결하기 위한 로직은 다음과 같다. 1. 주어진 치킨집에서 M개의 치킨집을 선택할 수 있는 모든 경우의 수를 조사한다. (조..

문제 보기이 문제는 브루트 포스 문제이다.완전탐색을 위해서 DFS를 재귀적으로 구현하였다.문제를 풀기위한 로직은 다음과 같다. 사다리를 놓을 수 있는 경우의 수 0, 1, 2, 3에 대하여, 그 갯수만큼 사다리를 놓을 때의 모든 경우의 수를 순서대로 탐색한다. (44~46번째 줄)만약 answer의 값이 변경되었다면(= sys.maxsize가 아닐 때), 필요한 사다리의 갯수를 찾았다고 간주하고 정답을 출력한다. (47~51번째 줄)사다리를 놓을 수 있는 모든 위치를 탐색하면서, 사다리를 놓을 모든 경우의 수를 DFS로 탐색한다. (32~41번째 줄)DFS를 재귀적으로 실행하면서 정해놓은 갯수만큼 사다리를 놓았다면, 사다리 게임을 시작하고, i번째 사다리에서 시작해서 i번째 사다리에서 모두 끝나는지 검사..

문제 보기이 문제는 브루트 포스 문제이다. 다음과 같은 감시카메라로 감시를 할 때, 주어진 맵에서 최소의 사각지대를 구해야한다.감시카메라의 종류는 다음과 같다.각 종류의 감시카메라가 90도마다 회전할 때의 최소 사각지대를 구해야한다.다음 그림을 보면 이해할 수 있다.위 그림을 설명하자면, CCTV 리스트에 있는 모든 카메라들에 대해서 4번씩 회전시키고, solution()함수를 재귀적으로 실행시킨다. 이때의 매개변수는 현재 CCTV 리스트와 그 index이다. 1. 리스트 내의 index가 0인 1번 CCTV의 모든 회전에 대해서 재귀적으로 탐색을 한다. (그림에서는 1번 CCTV를 4번 회전시킨다.)2. 1번 CCTV의 각 회전에 대해서 리스트 내의 index가 1인 2번 CCTV의 모든 회전에 대해서..

문제 보기이 문제는 시뮬레이션 문제이다.톱니바퀴의 초기상태와 회전 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구해야한다. 나는 이 문제를 보자마자 나는 비트마스크를 써야겠다고 생각했다.톱니의 상태를 2진수로 만들고, 이를 시계방향, 반시계방향으로 회전시키는 함수를 만들었다. (10~25번째 줄)12시 방향의 비트를 MSB로 두었고, MSB 바로 왼쪽의 비트를 LSB로 두었다. 10101111 -> 01011111 각 명령마다 톱니바퀴를 선택하고 돌릴 때, solution 함수를 통해 톱니바퀴를 양쪽으로 탐색한다.비트마스크를 사용해서 문제를 풀 때, 여기서 주의해야할 점이 있다. 1. 오른쪽으로 탐색할 때오른쪽 톱니바퀴를 회전시킬지 결정할 때, 오른쪽 톱니바퀴의 2번째 비트와, 왼쪽 톱니바퀴의 6번째 비..