재원블로그 재원블로그

이 문제는 구현, 시뮬레이션 문제이다. 문제의 요구사항 자체는 단순했으나 문제 자체가 약간 이해하기 어려웠다. N번 칸에 도착하면 무조건 로봇이 빠지고, 로봇과 상관없이 벨트는 N + 1 ~ 2N까지 밑으로 움직인다는 것을 이해하는데 시간이 좀 걸렸다. 내구도를 나타내는 A 배열과 robot의 존재 여부를 나타내는 robots 배열 두개를 만들어 간단하게 구현할 수 있었다.#include #include using namespace std;int N, K;vector A;vector robots;bool isEnd() { int cnt = 0; for (int i = 0; i = K) { return true; } return false;}void rotate() { vector next(2 * N);..

이 문제는 구현, 시뮬레이션 문제이다.  핵심은 토네이도가 돌아가는 위치를 찾아내는 로직을 구현하기, 토네이도가 이동했을 때 위치별로 모래 비율을 맞춰 분배하기이다.토네이도가 돌아가는 위치의 경우 한 방향을 잡았을 때 이동하는 만큼을 counts로 미리 계산하고, 해당 count의 루프가 끝나면 방향을 바꾸는 방식으로 구현했다.이동하는 카운트를 계산하는 것은 간단한데, 만약 N = 3일 경우 1, 1, 2, 2, 2이고, N = 5일 경우 1, 1, 2, 2, 3, 3, 4, 4, 4가 된다. 따라서 1 ~ N - 1까지는 2번씩 넣어주고, 마지막 N - 1을 한번 더 넣어주면 된다. 모래 비율의 경우 방향에 따라 dy, dx를 직접 하드코딩해서 넣었다. 이 때 주의할 점이 있는데, 빠져나갈 모래의 양을..

이 문제는 백트래킹을 이용해서 풀었다. 문제에서 주어지는 배열이 4 x 4이기 때문에 백트래킹으로 충분히 가능하다. 물고기 위치 정보를 저장할 때 -1을 해서 저장하는 것만 잊지 않으면 한번에 풀 수 있다.#include #include #include #include using namespace std;#define UP 0#define UPLEFT 1#define LEFT 2#define DOWNLEFT 3#define DOWN 4#define DOWNRIGHT 5#define RIGHT 6#define UPRIGHT 7#define SIZE 4#define FISH_MAX 16#define EMPTY 0#define SHARK -1bool inRange(int y, int x) { return..

이 문제는 백트래킹과 bfs를 이용해서 풀었다. 시간 제한이 0.25초이므로, C++ 기준 1초에 약 1억번의 연산을 가정했을 때 2,500만의 연산으로 문제를 풀어야 한다. 연구소의 크기는 가장 크게 잡았을 때 50 * 50이고, 최대 바이러스의 수 10개 중 가장 많은 경우의 수를 뽑는 조합인 10C5 = 252이므로 252 * 50 * 50 = 약 630,000 정도의 연산이 소요된다.따라서 백트래킹을 통해 활성화할 바이러스를 선택하고, 해당 바이러스로 bfs를 돌려 문제를 풀 수 있다. 여기서 한 가지 주의할 점은 bfs가 끝나고 걸린 시간을 셀 때 연구소 기준 2인 곳은 생략해야 한다는 점이다. 그렇지 않으면 첫번째 예제와 두번째 예제에서 답이 5가 나오게 된다. 모든 바이러스가 활성화된 바이러..

이 문제는 bfs와 유니온 파인드를 이용해서 풀었다. 이 문제를 요구사항 그대로 각 벽마다 bfs를 각각 수행하면 시간 초과가 나게 된다.따라서 반대로 빈칸을 bfs를 통해 덩어리의 개수를 미리 계산하고, 다음 루프에서 벽을 만나면 상하좌우로 더해주는 방식으로 사용했다. 여기서 문제는 같은 덩어리를 상하좌우 탐색에서 중복 계산할 수 있다는 점이다. 이를 없애기 위해 유니온 파인드로 한 덩어리를 그룹화하였고, 상하좌우를 탐색할 때 이미 탐색한 그룹이면 카운트하지 않게 구현했다.#include #include #include #include #include using namespace std;#define MAX 1000int N, M;int dy[] = { -1, 0, 1, 0 };int dx[] = { ..

이 문제는 유니온 파인드, 배낭 문제 알고리즘을 이용해서 풀었다. 한 아이의 사탕을 뺏으면 친구들의 사탕도 모조리 뺏는다는 조건을 보고 유니온 파인드를 떠올렸다.친구 그룹을 형성하여 총 사탕 수와 총 인원 수를 각각 candy, groupCount에 저장했다. 또한 각 그룹을 선택할지 말지에 대한 배낭 문제와 동일하다는 생각이 들어 배낭 문제의 알고리즘을 그대로 사용했다.이 때 주의할 점은 dp[i - 1]에 대한 비교가 계속되므로 i = 0일 때 i = -1인 지점을 찾게 되어 오류가 발생할 수 있다.따라서 i = 1부터 시작하도록 만들어 문제를 해결했다.#include #include #include #include using namespace std;#define MAX 30000vector> fr..

이 문제는 유니온 파인드를 이용해서 풀었다. 처음에는 dfs를 이용해서 그룹 수를 찾으면 되겠다고 생각했지만, 이는 정확한 정보를 주지 못한다.D L L LD UR R U와 같은 경우 만약 (0, 0)부터 탐색을 돌 경우 왼쪽 원에만 visited가 true가 되고 맨 오른쪽 L는 적용되지 않는다. 따라서 그룹이 2개가 나오게 된다. 그러나 전체가 그룹 하나로 이루어져야 정답이 된다. 따라서 이 같은 경우를 없애기 위해 유니온 파인드로 그룹화를 했다. 각 좌표에 대해 번호를 매기고, 이 번호를 토대로 그룹화를 하여 쉽게 문제를 풀 수 있었다. 주의할 점은 safe zone의 개수를 구할 때 set를 사용하면 시간 초과가 난다는 점이다. 단순히 for문 두개로 푸니 정답이 나왔다.#include #in..

이 문제는 최소 스패닝 트리를 이용한 문제이다. 최소 스패닝 트리는 모든 정점을 연결한 최소의 가중치의 부분 그래프를 의미한다.문제에서는 마을을 두 개의 분리된 마을로 분할해야 하고, 마을에는 집이 하나 이상 있어야 한다는 요구사항이 있다. 최소 스패닝 트리가 모든 정점을 연결한 최소 가중치의 부분 그래프라면, 크루스칼 알고리즘을 통해 MST를 만들 때 마지막으로 merge된 간선을 빼준다면 두 개의 부분 트리가 만들어 질 것이라고 예상하고 문제를 풀었고 정답을 맞출 수 있었다.#include #include #include using namespace std;#define MAX 100000struct Edge { int a; int b; int cost;};vector edges;int N, M;in..