풀스택챌린지

접근 사각형을 그리기위해 시작 위치를 기준으로 (1, -1), (1, 1), (-1, 1), (-1, -1)로 순서대로 이동하도록 구현하였다. DFS로 탐색을 진행하고 범위를 벗어나거나 이미 방문한 카페라면 return을 하고 그렇지 않을 때는 현재 방향을 그대로 이동하거나 방향을 증가시켜 이동한다. 방향을 증가시켜 이동할 때는 (-1, 1)로 이동하다가 (1, 1) 방향에 목적지가 있을 때 방향을 바꾼다. 또한 (1, -1)이거나 (1, 1)일 때는 현재 방향으로도 이동하고 다음 방향으로도 이동할 수 있도록 재귀호출한다. 구현 - 주어진 입력을 모두 받은 후에 - board를 탐색하면서 각 위치에서 dfs를 진행한다. N = int(input()) board = [list(map(int, input()..

접근 최대 높이를 찾고 2차원 맵을 탐색해서 최대 높이의 위치에서 DFS를 진행한다. 현재 위치에서 상하좌우 탐색을 진행하고 현재 위치보다 높이가 작은 위치로 이동한다. 만약 같거나 클 때는 K만큼 공사할 수 있는지 판단하여 이동한다. 구현 - 최대 높이를 찾아서 max_value에 저장한다. - 2차원 리스트인 board를 탐색해서 max_value가 나올 때마다 dfs를 진행한다. - dfs에는 현재 위치, 방문 여부, 길이, 공사의 여부를 전달한다. N, K = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] max_value = 0 for y in range(N): for x in range(..

접근 리스트를 원소로 갖는 2차원 리스트를 생성하여 미생물들의 개수와 방향을 넣었다. 이후에 미생물이 이동할 때 새로운 2차원 리스트에 이동한 미생물들을 대입하였다. 그리고 2개 이상의 미생물들이 모였을 때 합을 구하고 제일 많은 개수를 갖는 미생물의 방향을 구하여 업데이트하였다. 구현 - 다음은 미생물들이 이동하는 것을 구현한 함수이다. - 먼저 기존의 미생물들이 들어있는 board를 탐색하여 해당 미생물을 이동시킨다. - 이동시켰을 때 약품이 칠해져있는 곳일 때는 개수를 반으로 나누고 방향을 반대로 설정한다. - 미생물의 개수가 1 이상일 때 새로운 위치에 대입한다. - 모든 미생물들의 이동이 끝난 후에 2개 이상이 모여있는 곳은 미생물들을 하나씩 꺼내어 총합을 구한다. - 이때 개수가 가장 많은 미..

접근 약품을 투입할 수 있는 모든 조합을 확인했을 때 완전탐색으로 풀이가 가능하다고 생각하였다. 따라서 K가 2 이상일 때 약품을 투입하는 조합을 생성하여 해당 셀을 모두 0 또는 1로 바꾸어주었다. 그리고 모두 성능검사에 통과하는지 판단하는 함수로 전달하여 판단하였다. 이 문제는 계속 49개만 맞았다고 나왔는데 문제점을 파악하기 어려웠다. 계속 시도를 해보다가 뒤늦게 깨달았는데 나의 풀이에 문제가 있었다. 만약 3개의 막에 약품을 주입한다했을 때 해당 막의 셀들을 모두 0 또는 1로 바꾸어주었다. 하지만 이렇게하면 3개의 막 중에 2곳은 0 1곳은 1을 주입할 수도 있는 경우의 수를 놓치고 있었다. 따라서 이 부분을 해결한 후에 PASS를 받을 수 있었다. 구현 - 성능 검사에 통과할 수 있는지 판단하..

접근 두 명의 사용자가 이동을 할 때마다 주위에 충전할 수 있는 충전기를 모두 찾는다. 찾은 후에 성능을 기준으로 내림차순 정렬하여 두 명의 사용자가 최댓값이 되도록 충전기를 선택하도록 한다. 만약 같은 충전기 내에 두 명이 존재하면 배분을 해서 가져가야한다. 하지만 한 명이 다른 충전기 범위 내에도 존재하면 이 사용자는 다른 충전기를 선택하도록 해야한다. 구현 - 사용자 2명의 이동 경로를 move_info에 저장한다. - 충전기의 정보를 charge_info에 저장한다. - 이제 사용자들을 move_info에 기반하여 이동시키고 - 이동시킬 때마다 charge 함수로 위치를 보내서 최댓값으로 충전할 수 있는 양을 구한다. for tc in range(test_case): N = 10 M, A = ma..

접근 먼저 계단은 무조건 2개가 존재하고 사람의 수는 10명 이하이다. 따라서 완전탐색으로 풀 수 있었다. 최대 10명의 사람들이 1번 또는 2번 계단을 고르는 모든 경우의 수를 만들고 같은 계단을 고른 사람들 끼리 그룹을 만들어 해당 그룹의 사람들이 계단을 타고 모두 내려오는 시간을 구하는 함수를 만들었다. 이를 통해 1번과 2번 계단을 선택한 사람의 소요시간을 구하고 이 중 최댓값을 찾아 최종해와 최솟값 비교를 진행한다. 구현 - DFS를 통해 사람들의 1번 또는 2번 계단을 고르는 모든 경우의 수를 구한다. - 사람들이 모두 계단을 골랐으면 1번 계단을 고른 사람과 2번 계단을 고른 사람을 나누고 이를 solve함수에 전달한다. - solve 함수에서는 해당 사람들이 모두 내려왔을 때의 시간을 구하..

접근 먼저 가로와 세로를 탐색해서 활주로가 가능한지 알아보기 위해 각 열의 세로 정보들을 N행에 이어 붙였다. 이후 각 행마다 활주로 건설이 가능한지 검사를 한다. 먼저 이전 인덱스의 값과 현재 인덱스의 값이 같을 때는 continue를 진행한다. 이전 인덱스와 현재 인덱스의 + 1 값이 같을 때는 내리막이되는 경사로를 설치할 수 있는지 검사하고 설치할 수 없다면 활주로가 안되는 것으로 간주한다. 이전 인덱스의 - 1과 현재 인덱스의 값이 같을 때는 오르막이되는 경사로를 설치할 수 있는지 검사하고 설치할 수 없다면 활주로가 안되는 것으로 간주한다. 경사로를 설치할 때는 범위를 벗어나거나 겹쳐서 사용하면 안되기 때문에 각 인덱스에 경사로 설치유무를 체크하고 맵을 벗어나는지 체크하여 경사로를 설치하도록 한다..

접근 X시간 비활성화 상태 -> X시간동안 활성화 -> 죽음, 활성화 후 1시간 동안 번식을 한다고 한다. 이를 구현하기 위해 다음과같이 접근하였다. 만약 X = 2 라고 해보자. X에 2를 곱하면 4가 되고 4초 = 초기상태 3초 = 비활성화 2초 = 활성화 1초 = 활성화 및 번식 0초 = 죽음 위와 같이 X에 2를 곱하면 X - 1이 되는 시점에 번식이 이루어진다. 이렇게 비활성화 -> 활성 -> 번식을 구현하였다. 이제는 동시에 같은 곳에 번식을 하려고할 때 X가 큰 것이 오도록 해야한다. 이를 위해 X순으로 내림차순 정렬 후에 X가 큰 것부터 처리하도록 하였다. 이를 통해 먼저 처리가 되어있거나 이미 줄기세포가 있다면 continue가 진행되어 더 낮은 X는 같은 곳에 번식이 되지 못하도록 구현..

접근 두 명의 일꾼이 각각 가로로 연속으로 M개의 벌통을 선택한다. 이때 두 명의 일꾼이 선택한 벌통이 겹치면 안된다. => 이는 2차원 리스트의 완전탐색을 통해 두 명의 일꾼이 벌통을 선택하는 경우의 수를 구할 수 있을 것이다. 선택한 M개의 벌통 중에서 가중치가 가장 큰 것을 찾아야한다. 예를 들어 5, 5, 9 벌통을 선택했고 C가 10이라고 하자. 그렇다면 최대 수익을 위해 5, 5가 아닌 9를 선택해야한다. => itertools의 combinations를 활용하여 선택한 벌통 중에 최대수익을 찾는다. 구현 - 벌통을 2개 선택했을 때 최대수익을 구한다. - 두 명의 일꾼이 선택한 벌통(storage[0], storage[1])에서 combinations를 통해 최대수익을 구한다. - 이를 re..

첫 번째 접근 모든 위치에 대해 BFS를 진행하였다. BFS를 하면서 집의 개수를 카운트하였고 집의 개수 x M이 운영비용보다 같거나 클 때 최댓값 비교를 진행했다. PASS는 되었지만 시간이 오래 걸렸고 불필요한 곳까지 탐색한다는 것을 알았다. 첫 번째 구현 - K를 N+1 ~ 1까지 탐색하면서 모든 좌표에 대해 BFS를 진행한다. - BFS는 현재 위치를 기준으로 거리를 통해 방문표시를 한다. - 거리가 K이하일 때만 큐에 넣어 다음 위치를 탐색할 수 있도록 하였다. => 마름모 형태 - 이후 현재 위치가 집일 경우 집의 개수인 count를 증가시켰다. - BFS가 종료되고 count x M이 운영 비용보다 크거나 같을 때 최댓값 비교를 한다. from collections import deque d..