0과 1의 쉼터

풀이 N개의 정점에 대해 컴포넌트의 밀도가 높은, 하나로 연결된 정점을 간선으로 나눈 수치가 최대인 컴퓨터들의 목록을 출력해주면 되는 문제다. 연결만 되어있다면 동일한 컴포넌트로 볼 수 있으니 양방향그래프로 초기설정을 해주자. 이제 모든 정점에 대해 하나의 컴포넌트에 속하는 컴퓨터들의 목록을 저장해 반환해주는 bfs를 실행하자. 방문하지 않은 정점들에 대해 연결된 모든 정점을 set인 path에 추가해주는 방법으로 중복을 제거했다. 하나의 컴포넌트에 속한 컴퓨터를 모두 찾았다면, 해당 컴퓨터와 연결된 컴퓨터가 컴포넌트에 존재하는 만큼 간선의 개수를 계산하자. 반환받은 컴포넌트 내 컴퓨터 목록과 밀도를 이용해 문제에서 주어진 조건대로 알맞는 컴포넌트로 갱신 후 탐색이 모두 종료되었을 때 조건에 부합하는 컴..

풀이 N개의 섬에 대해 양방향으로 연결된 그룹의 개수를 구하는 문제다. 입력시에는 단방향으로만 입력받아야 한다. 1 ~ N 번 노드에 대해 방문하지 않은 노드에대해 bfs를 해주면 된다. 정점 u부터 시작해 연결 가능한 모든 정점을 확인하며, 양방향인 경우에만 방문표시와 함께 다음 탐색대상으로 포함시키면된다. 더 이상 탐색할 수 있는 정점이 없다면 bfs를 종료하며 1을 반환해 그룹의 개수를 증가시키면 된다. 출처 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io

풀이 N개의 과일에 대해 1원당 포만감이 많은 과일을 최대한 K만큼 구할 때 최대 포만감을 구하는 문제다. 입력형식은 과열의 가격 P와 포만감 C로 주어지며, 1원당 포만감은 C / P로 구할 수 있다. 정렬을 위해 1원당 포만감을 첫 번째 요소로 두고, 최대 몇번 먹을 수 있는지 P를 두 번째 요소로 저장해주자. C / P 가 높은 과일을 우선적으로 구매하는 것이 이득이기 때문에, DESC 정렬을 해준 후 탐색을 진행하자. 만약 남은 K가 P 이상이라면(한 과일을 전부 구매할 수 있다면) 원래 과일 한 개의 포만감 만큼 계산해주면 된다. 남은 K가 부족해 한 개의 과일을 전부 구매하지 못한다면, K개의 조각(fruit_slice)만 구매해주자. 위 과정을 거쳐 K가 0이라면 탐색을 중단하고 그렇지 않다..

풀이 입력받은 양방향 그래프에 대해 정점 K부터 시작해 연결된 정점 중 번호가 작은 정점을 우선적으로 방문하는 문제다. 이미 방문한 정점을 다시 방문해서는 안되며, self-loop는 존재하지 않는다. 번호가 작은 정점을 우선적으로 방문하므로 미리 정렬해주자. dfs를 loop로 구현했다. 정점K부터 시작해 방문한 모든 정점을 방문표시해주며, 현재 정점과 연결된 반대 정점 중 방문하지 않은 정점에 대해 탐색하는 방법이다. 만약 더 이상 다른 정점으로 방문이 불가능한 경우 loop를 빠져나오며, 지금까지 방문한 정점의 갯수와 마지막으로 방문한 정점의 번호를 출력하면 된다. 출처 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io

풀이 이전에 풀었던 문제의 응용버전이다. [구름톤 챌린지] 12일차 - 발전기 풀이 집에 전력을 공급하기 위해서는 그 집에 발전기를 설치하거나, 해당 집 주변에 전력이 공급되고 있는 집이 있어야 한다. 즉, 상하좌우로 붙어있는 집의 그룹이 몇 개인지 구하는 문제이다. kyr-db.tistory.com 이전에는 단순히 집이 있는지 아닌지에 따라 그리고 인접했는지 아닌지에 따라 그룹화 해주었다. 이번에는 집의 유형(house_type)과 인접여부에 따라 그룹화를 진행해주면 된다. 동일 유형의 집이고 인접방향일 때마다 다음 탐색 대상에 넣어주면서 그룹에 속할 수 있는 집의 갯수를 세주어야 한다. 탐색이 끝난 후 만약 그룹에 속한 집의 갯수가 K개 이상이라면 "단지"가 될 수 있다. 각 집의 유형별 존재하는 단..

풀이 A와 B는 서로 배수가 아니지만, A < B이므로 B가 최대한 많은 갯수부터 시작해 점차 A의 갯수를 늘리는 방법으로 통증 수치가 0이 되는 비율을 찾으면 된다. N을 A로 나누었을 때 까지의 몫까지의 수에 대해서만 탐색을 하면 충분하다. 만약, 위 두 조건문에 해당되지 않았다면, A와 B의 비율을 어떻게 하든 절대 통증 수치를 0으로 만들 수 없으므로 -1을 출력하자. 출처 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io

풀이 goorm 과 player의 시작좌표를 입력받고 형식으로 어떤 방향으로 몇칸 움직여야 하는지 적혀있는 보드가 주어진다. 먼저 방향과 이동할 칸의 수를 분리해주자. 칸을 이동하며 기존에 방문한 칸이 나오거나 모든 칸을 전부 탐색할 때 까지 탐색을 진행해야 한다. 만약 탐색 중 이미 방문한 칸이 나왔다면 게임이 끝났으니 탐색을 멈추고, 모든 점수를 합해서 반환하면 된다. 이제 goorm과 player의 점수를 알 수 있으니 출력형식에 맞추어 정답을 출력하자. 출처 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io

풀이 K개의 폭탄에 대해 폭탄을 떨어트린 장소 (x, y)와 인접한 장소에 대해 아래와 같이 값을 증가시키면 된다. '#'이 아니고, '@' 인 경우 2만큼 증가시킨다. '#'이 아니고, '@' 가 아닌경우 1만큼 증가시킨다. 폭탄의 위치가 0 ~ N - 1이 아닌, 1 ~ N이므로 점수를 기록할 보드를1칸씩 넓게 선언해주자. 점수를 기록한 보드에서 최댓값을 찾아 출력해주면 된다. 출처 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io

풀이 14, 7, 1 만큼 감소시키는 아이템을 사용해 N을 0으로 만들기 위해 최소 몇개를 사용해야 하는지 계산하는 문제다. 주어진 아이템의 통증 감소 수치가 서로 배수이기 때문에 무조건 큰 수를 최대한 빼는 greedy 기초 문제다. 반복문을 사용할 필요없이 배수의 몫만큼 최소 갯수를 계산해주면 빠른시간 내 풀이할 수 있다. 출처 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io

풀이 구름을 주위로 빈 공간이 몇개있는지 세는 방법으로 풀이했다. 게임판의 정보를 입력받을 때, 구름의 좌표를 저장하는 리스트를 만들어주자. 저장한 구름의 좌표를 순회하며, 주위에 구름이 아닌 경우 깃발을 하나씩 꽂아준다( -1씩 감소시킨다) 그렇다면, 이제 구름을 주위로 빈 공간에 대해 깃발을 전부 꽂았을 것이고, -board[x][y] 가 K와 동일한 경우만 찾으면 된다. 출처 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io