Machineboy空

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제요약 조건에 따라 인구 이동이 일어나는 횟수 난이도 Gold 4 풀이 포인트 DFS, connected componet 문제임을 파악하기 REVIEW 우선, 2차원 좌표를 1차원으로 묶어서 생각하는 법을 생각하다가 어후 너무 복잡해져서 풀이를 관두었다.. 정말 간단하게 생각하면 된다. 기존 DFS을 돌릴 때 육지라면 ( a[ny][nx] ==1 ) 이면 이동했던 것을 문제의 조..

https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 문제요약 최단거리가 가장 먼 육지의 두 곳에 보물심기 난이도 Gold 5 풀이 포인트 BFS를 실행하면, 한 칸씩 움직일 때마다 최단거리가 갱신됨 즉, 도착 지점 과 출발지점 쌍이 계속 나오기 때문에 2쌍을 뽑아서 돌릴 필요가 없다. BFS void bfs(int y, int x) { memset(visited, 0, sizeof(visited)); visited[y][x] = 1; queue q;..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제요약 트리 구조에서 한 노드를 지웠을 때 리프노드의 개수를 구하라. 난이도 Gold 5 //내 코드 #include using namespace std; int n, a[52], k, ret; vector adj[52]; bool b[52]; void cut(int node) { b[node] = false; for (int s : adj[node]) { cut(s); } } int ma..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제요약 가장 효율적인 치킨 집의 개수와, 치킨 집까지의 최소 거리의 합 난이도 Gold 5 풀이 포인트 조합 void combi(int start, vector v) { if (v.size() == m) { chickenList.push_back(v); return; } for (int i = start + 1; i < chicken.size(); i++) { v.push..

1.1.1 Hashing Introduction this algorithm's often computer science's favorite algorithm, because you're going to find the results of hashing, it's going to give us a fantastic run time for certain operations. Mathematically, we define hashing as a keyspace(table) that we want to transform into a number of different values. So, everything inside of our keyspace is going to be every possible key t..

완전탐색은 모든 경우의 수를 탐색하는 것이고, 백트래킹은 완전 탐색을 기반으로 하되, 불필요한 연산을 좀 줄이는 것. 경우의 수는 순열과 조합 + 로직으로 풀린다. 이를 재귀 또는 반복문으로 구현할 수 있다. 원상복구 타이밍 잘 처리하기! 상태값이 그 다음 경우의 수에 영향미치지 않게 처리해주는 것 완전 탐색 (brute force, exhaustive key search) 모든 경우의 수를 탐색하는 알고리즘 순열or 조합 + 로직 보통 1억 미만까지는 컴퓨터를 믿고 넘겨라. 예제) https://machineboy0.tistory.com/183 14502 : 연구소 - DFS, deep copy https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바..

https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 문제요약 공기와 접촉한 치즈의 표면이 녹아내릴 때, 모두 녹는 데 걸리는 시간과 녹기 1시간 전의 크기. 난이도 Gold 4 풀이 포인트 어떤 것을 중심으로 dfs를 돌릴지 잘 생각해야함. REVIEW 내가 하고 싶었던 건, 이동 방향에 우선순위를 두어 치즈 덩이(연결요소)의 시작점으로부터 반 시계방향 (아래,오른쪽,위, 왼쪽으로) 탐색하며 가장자리를 칠해가는 방식이었다. 풀이가 복잡해지는데 느낀 순간 오답이겠거니..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제요약 3개의 벽을 세워 바이러스가 퍼지지 않는 안전영역의 최대 크기 구하기 난이도 Gold 4 풀이 포인트 단계 꼼꼼히 if (nx >= 0 && nx = 0 && ny =n || ny =m || b[nx][ny] > 0) continue; /..