구름을 채우다

문제 보기 이 문제는 브루트 포스 문제이다. 모든 경우의 수를 따져서 문제에 조건에 해당하는 최적의 결과를 찾아야 하는 게 목적이다. 모든 경우의 수를 따질 대상은 기준점이 되는 (x, y)와 d1, d2이다. (81~84번째 줄) 그리고 각 경우가 유효한 경우인지는 다음과 같이 문제에 명시되어 있으므로 이를 적용해서 필터링한다. (85번째 줄) 맨 처음 문제를 풀 때 다음과 같은 로직으로 문제를 해결하려고 했다. 5번 선거구의 경계를 구한다. 5번 선거구에 포함된 인구를 구한다. 1, 2, 3, 4번 선거구에 포함된 인구를 구한다. 인구가 가장 많은 선거구와 가장 적은 선거구의 차이가 최소가 되는 경우를 찾는다. 그런데 2번 과정에서 5번 선거구에 포함된 인구를 구할 방법이 떠오르지 않았다. 문제를 계..

문제 보기 이 문제는 DFS, BFS 문제이다. (DFS로는 안 풀어도 된다.) 연구소 내의 모든 바이러스 중에서 m개의 바이러스를 선택하는 과정을 DFS로 풀면 DFS 문제가 되겠지만, 나는 itertools 모듈의 combinations 함수를 사용하였다. 문제를 푼 로직은 다음과 같다. 입력으로부터 연구소 내의 빈 방의 개수와 바이러스의 위치를 저장한다. (9~17번째 줄) 모든 바이러스 중에서 m개의 바이러스를 선택하는 모든 경우의 수를 구한다. (20~21번째 줄) 2번에서 구한 m개의 바이러스를 큐에 삽입한다. (22~26번째 줄) 3번에서 큐에 삽입한 m개의 바이러스를 BFS를 통해 확산시킨다. (확산될 수 있는 경우의 수는 빈 방일 경우와 비활성 바이러스일 경우 확산될 수 있다. 빈 방의 ..

문제 보기 이 문제는 시뮬레이션 문제이다. 처음에 문제를 읽자마자 든 생각은 두 가지였다. 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번째 ..

문제 보기 이 문제는 스택/큐 문제이다. 문제를 푼 로직은 다음과 같다. 모든 탑은 왼쪽으로 레이저 신호를 발사하므로, 각 탑에 대해서 왼쪽에 위치한 모든 탑에 대해 탐색을 진행한다. (4~7번째 줄) 만약 현재 탑에서 왼쪽에 위치한 탑들 중에 높이가 높은 탑이 있다면, 그 탑의 위치를 기록한다. (8~11번째 줄) 만약 왼쪽에 위치한 탑들 중에 높이가 높은 탑이 없다면 0을 기록한다. (12~14번째 줄) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def solution(heights): answer = [] for i, height in enumerate(heights): found = False # for all front towers from the nearest tow..

문제 보기 이 문제는 스택/큐 문제이다. 문제를 읽다보면 처음에 중요도가 더 높은 문서를 인쇄해야한다고 해서, 우선순위 큐를 생각했었지만, 입력값의 범위가 100보다 작다고 명시되어 있어서 그냥 n^2의 복잡도로 문제를 풀었다. 문제를 푼 로직은 다음과 같다. 빠른 삽입과 제거를 위해 주어진 대기목록의 list형 변수를 deque로 변환한다. (7~10번째 줄) 대기 목록의 가장 앞에 있는 문서를 꺼내고, 대기 목록 중에 우선순위가 더 높은 문서가 있는지 확인한다. (13~21번째 줄) 만약 대기 목록 중, 우선순위가 더 높은 문서가 있다면 대기 목록의 맨 뒤에 현재 문서를 추가한다. (17~21번째 줄) 만약 문서가 추가되었다면, 1번으로 되돌아간다. (23~25번째 줄) 만약 문서가 출력되었다면, 횟..