본문 바로가기

알고리즘/구름톤 챌린지

 (20)
[구름톤 챌린지] 4주차 20일차 연결 요소 제거하기 문제 $N \times N$ 크기의 2차원 배열이 있다. 2차원 배열의 $i$행 $j$열에 해당하는 칸은 $(i, j)$로 나타낸다. 처음에 이 배열의 각 칸에는 알파벳 대문자 또는 . 문자가 하나 적혀 있다. 상하좌우로 인접한 두 칸에 같은 문자가 적혀있는 경우, 두 칸은 연결되어 있다고 한다. 서로 연결된 칸들의 집합을 연결 요소라고 하고, 연결 요소의 크기는 그 연결 요소에 포함된 칸들의 개수와 같다. 구름이는 아래 작업을 $Q$번 수행하려고 한다. $(y_i, x_i)$ 칸을 고른 뒤, 그 칸에 알파벳 대문자 $d_i$를 쓴다. 구름이가 고른 칸은 . 문자가 적힌 칸임이 보장된다. 배열에 존재하는 모든 연결 요소의 크기를 계산한다. 만약 크기가 $K$ 이상인 연결 요소가 존재한다면, 그 연결 요소..
[구름톤 챌린지] 4주차 19일차 대체 경로 문제 플레이어는 $1$번부터 $N$번까지의 번호가 붙은 $N$개의 도시와 $M$개의 도로가 있는 나라에 살고 있다. 각 도로는 서로 다른 두 도시를 양방향으로 연결하고 있고, 주어진 도로만을 이용해 임의의 두 도시 사이를 이동하는 것이 가능하다. 플레이어는 차를 타고 $S$번 도시에서 $E$번 도시로 이동하려고 한다. 플레이어가 두 도시 사이를 이동할 때는 항상 가장 작은 수의 도시를 거치는 경로를 따라 이동한다. 예를 들어 아래 그림과 같이 도시와 도로가 주어지고, 플레이어가 1번 도시에서 4번 도시로 이동하려고 할 때는 항상 1 → 3 → 4의 경로를 따라 이동한다. 이 경우에는 출발 도시와 도착 도시를 포함해 총 세 개의 도시를 거쳐 이동할 수 있다. 1 → 5 → 2 → 4의 경로로 이동하는 것은..
[구름톤 챌린지] 4주차 18일차 중첩 점 문제 한 변의 길이가 $N$인 정사각형이 있다. 플레이어는 이 정사각형 위에 $M$개의 반직선을 그린 뒤, 두 반직선이 교차하는 점의 수를 세려고 한다. 플레이어가 반직선을 그리는 과정은 아래와 같다. 반직선을 그리기 시작할 칸 $(y, x)$를 정한다. $(y, x)$는 주어진 정사각형을 $1 \times 1$ 크기의 정사각형으로 나눴을 때, $y$번째 행의 $x$번째 열에 해당하는 칸이다. 반직선을 그릴 방향 $d$를 정한다. 방향은 상하좌우 중 하나이며, 항상 정사각형 테두리의 가로 혹은 세로와 평행하다. 반직선을 그린다. 반직선은 항상 시작 칸의 테두리에서부터 시작하며, 같은 칸을 지나는 평행한 직선이 서로 만나지 않도록 그린다. 아래 그림은 길이가 $4$인 정사각형 위에 다음 세 개의 직선을 그..
[구름톤 챌린지] 4주차 17일차 통신망 분석 문제 이 세상에는 수많은 컴퓨터들이 통신망을 통해 서로 연결되어 정보를 교류하고 있다. 오늘 플레이어는 이 거대한 통신망 중 한 구역을 조사하고자 한다. 플레이어가 조사할 구역에는 $N$개의 컴퓨터가 있고, $M$개의 통신 회선이 있다. 각 컴퓨터는 $1$번부터 $N$번까지 번호가 붙어 있고, 통신 회선은 서로 다른 두 컴퓨터를 양방향으로 연결하고 있다. 컴퓨터들은 연결 여부에 따라 여러 개의 컴포넌트로 나뉜다. 어떤 두 컴퓨터가 통신 회선만을 이용해서 연결되어 있다면 두 컴퓨터는 같은 컴포넌트에 속한다. 플레이어는 여러 개의 컴포넌트 중, 가장 밀도가 높은 컴포넌트를 조사하려고 한다. 컴포넌트의 밀도는 그 컴포넌트에 포함된 통신 회선의 개수를 컴퓨터의 수로 나눈 값이다. 주어진 통신 구역을 분석해서, ..
[구름톤 챌린지] 4주차 16일차 연합 문제 바다 위에 $N$개의 섬이 있다. 섬은 $1$번부터 $N$번까지 차례대로 번호가 붙어 있다. 서로 다른 두 섬 사이를 연결하는 $M$개의 다리도 있다. 모든 다리는 단방향으로만 이동 가능하고, 어떤 두 섬 사이를 잇는 다리는 정방향 하나, 역방향 하나씩 해서 최대 두 개이다. 어느 날, 섬들 사이에 분쟁이 일어났다. 모든 섬들은 세력을 키우기 위해 다른 섬과 연합을 결성하려고 한다. 임의의 두 섬 $a$와 $b$에 대해, $a$번 섬에서 $b$번 섬으로 직접 이동할 수 있는 다리와 $b$번 섬에서 $a$번 섬으로 직접 이동할 수 있는 다리가 있으면, 두 섬은 연합을 결성한다. 이때, $a$와 $b$가 연합을 결성하고 $b$와 $c$가 연합을 결성했다면 $a$와 $c$ 역시 위 조건을 만족하지 않더라..
[구름톤 챌린지] 3주차 15일차 과일 구매 문제 과일을 사기 위해 마트를 간 플레이어는 큰 난관에 봉착했다. 왜냐하면 팔고 있는 과일이 너무 많아서, 어떤 과일을 사면 좋을지 결정하는 게 너무 어려웠기 때문이다. 현재 마트에서 팔고 있는 과일은 $N$종류가 한 개씩 있고, 각 과일의 가격은 $P_i$, 그리고 그 과일을 먹었을 때 플레이어가 얻을 수 있는 포만감은 $C_i$이다. 이 마트에서는 특이하게도 과일을 조각 단위로 구매하는 것이 가능하다. 가격이 $p$인 과일을 조각 단위로 구매하고자 할 경우, 플레이어는 이 과일을 $p$개의 조각으로 자른 뒤 그중 원하는 몇 개의 조각만을 구매할 수 있다. 이때 모든 조각의 가격은 $1$, 먹었을 때 얻을 수 있는 포만감은 $C_i/P_i$로 동일하다. 플레이어는 $K$만큼의 돈을 가지고 있다. 플레이..
[구름톤 챌린지] 3주차 14일차 작은 노드 문제 $N$개의 노드와 $M$개의 양방향 간선으로 이루어진 그래프가 있다. 이 그래프의 노드는 $1$번부터 $N$번까지 번호가 붙어 있다. 양끝 노드가 동일한 간선은 주어지지 않는다. 플레이어는 아래 규칙에 따라 그래프에서 이동하려고 한다. 플레이어는 처음에 $K$번 노드에 있다. 한 번 방문한 노드는 다시 방문할 수 없다. 시작 노드도 방문한 것으로 간주한다. 현재 노드와 간선으로 직접 연결된 다른 노드 중, 방문할 수 있으면서 번호가 가장 작은 노드로 이동한다. 플레이어가 더 이상 이동할 수 있는 노드가 없을 때, 방문한 서로 다른 노드의 개수와 마지막 노드 번호를 구해보자. 입력 첫째 줄에 노드의 개수 $N$, 간선의 개수 $M$, 시작 노드의 번호 $K$가 공백을 두고 주어진다. 다음 $M$개의 ..
[구름톤 챌린지] 3주차 13일차 발전기 (2) 문제 구름 심시티를 하고 있는 플레이어는 한 변의 길이가 $N$인 정사각형 모양의 마을 $M$을 만들고 있다. 마을의 모든 칸에는 건물이 하나씩 있고, $r$번째 행, $c$번째 열에 해당하는 칸에는 정수 $M_{r, c}$가 적혀 있다. $M_{r, c}$는 해당 칸에 있는 건물의 유형의 번호를 의미한다. 건물의 유형이 동일하면서, 서로 상하좌우 인접한 칸에 위치한 건물끼리는 서로 전력을 공유할 수 있다. 전력을 공유할 수 있는 관계에 속한 건물의 개수가 $K$개 이상이면 이를 단지라고 한다. 플레이어는 발전기를 설치해 각 단지에 전력을 공급하고자 한다. 하지만 비용 문제로 인해 단 하나의 발전기만 설치할 수 있다. 발전기는 특정 건물 유형 하나에 해당하는 모든 단지에 전력을 공급할 수 있다. 그래서 ..

티스토리툴바