겜돌이의 개발일지

문제 백준 17471 게리맨더링 C++ 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 N까지의 노드를 0과 1로 양분합니다. 0과 1을 양분할 수 있는 모든 경우의 수에 대해 실행합니다. (조합 이용) 0과 1로 양분할 수 있게 영역이 결정되면, 각 영역을 서로 0은 0끼리, 1은 1끼리 연결할 수 있는지 확인힙니다. 연결이 가능하다면, 각각의 합을 구한 후 차를 구하고, 최솟값과 비교하여 갱신합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ..

문제 백준 2668 숫자고르기 C++ 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 풀이 각각의 정점에서 dfs를 실행하면서, 다른 루프와 겹치는지 검사합니다. 겹치지 않았다면 cnt를 늘려주고 check 표시를 합니다. 이후 check된 노드들을 표시합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 4..

문제 백준 14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 8x8의 작은 배열이기 때문에 가능한 모든 경우의 수에 대해 벽을 만들어 주는 브루트포스 방법을 사용합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 ..

문제 백준 2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이 일반적인 dfs, bfs 문제입니다. 저는 bfs로 풀었습니다. 입력을 받고, 사각형이 있는 위치를 1, 없는 위치를 0으로 초기화해줍니다. bfs를 실행하면서 개수와 영역의 넓이를 구합니다. 영역은 vector에 push 해준 뒤, 오름차순으로 정렬하여 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3..

문제 백준 2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 일반적인 dfs 문제입니다. 1번 노드부터 dfs를 돌며 cnt를 증가시켜줍니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include using namespace std; bool graph[101][101]; bool visited[101]; int n, m; int cnt;..

문제 백준 22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 풀이 전형적인 bfs, dfs 문제입니다. 투약 전과 투약 후의 상태를 입력받습니다. 루프를 돌면서, 전과 후의 상태가 다르면 그 지점부터 bfs를 해줍니다. bfs 이후에도 전과 후가 다르다면, 백신이 아니므로 NO를 출력합니다. 같다면 YES를 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2..

문제 백준 15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 풀이 리프 노드는 자식이 없으므로 서브 트리의 정점 개수는 자기 자신 1개입니다. 따라서 dp 배열을 1로 초기화해줍니다. 루트 노드부터 dfs를 실행하고, 서브 트리의 탐색이 모두 끝났다면 부모에게 자신의 서브 트리 값을 더해줍니다. 부모가 -1인 경우는 루트 노드이므로 더하지 않습니다. 예제를 보겠습니다. 숫자는 해당 정점에서의 서브 트리의 정점 개수이고, 괄호 안은 방문 순서..

문제 백준 1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 전형적인 트리 - dfs 문제입니다. 부모가 없는 노드(입력이 -1)를 루트 노드라고 하고, 루트 노드부터 dfs를 진행합니다. 이 때 제거하는 노드 처리가 중요한데, 루트 노드를 제거하였을 때는 0을 바로 출력해줍니다. 그 이외일 때는 제거한 노드를 기억하여, dfs를 실행할 때 방문하지 않습니다. 리프 노드는 자식이 없는 노드이므로 vector의 사이즈를 확인하여, 0이면 cnt를 ++해줍니다. 또한 제거된 노드 하나만을 자식으..

문제 백준 14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 처음에 모든 블록을 하드 코딩하려다가 뭔가 잘못된 것을 깨닫고 풀이를 참조했습니다. ㅓ, ㅏ , ㅜ, ㅗ 모양을 제외한 테트로미노는 시작 지점을 깊이가 0이라고 했을 때, 깊이가 3인 dfs로 표현할 수 있습니다. ㅓ, ㅏ , ㅜ, ㅗ 모양은 하드 코딩(elseshape)으로 따로 점검해줍니다. map을 돌면서 해당 지점에서 만들 수 있는 테트로미노의 최댓값을 저장하고, maxsum을 넘는다면 maxsum을 바꿔줍니다. 모든 map을 다..