재원블로그 재원블로그

이 문제는 시뮬레이션 문제이다. 이 문제에서 핵심은 연쇄적으로 발생하는 기사들의 움직임을 구현하는 것이다. 나는 이걸 구현하기 위해 재귀를 사용했다.어떤 기사가 어떤 방향으로 움직여야할 때, 방패까지 포함한 자신의 경계를 구하고, 그 경계에서 다음 위치를 확인한 뒤 만약 다른 기사가 있어면 그 기사에 대해 재귀적으로 호출하는 방식으로 구현했다. 실제로 움직임을 구현할 때 주의해야할 점이 있는데, 우선 이미 움직인 기사를 또 움직이면 안된다. 내 코드의 경우 move 함수 안에서 candidate를 뽑아 진행하는데, 중복이 가능하여 처음에 오답이 나왔었다.또한 움직인 기사들 말고도 안 움직인 기사들도 다음 벡터에 남아야 한다. 너무 당연한 로직인데 항상 실수하는 부분인 것 같다.#include #inclu..

이 문제는 BFS, 시뮬레이션 문제이다. 이 문제에서 핵심은 부분 배열 회전, bfs 구현이다. 부분 배열 회전의 경우 이중 벡터와 함께 큐를 사용해서 구현했다. 좌표를 정확히 구현할 수도 있지만, 실제 코딩 테스트에서는 정확하고 빠르게 구현할 수 있는 직관적인게 좋다고 느꼈다. 보통 삼성 문제의 1번 문항은 구현력 위주고, 메모리나 성능에 대해서는 크게 걱정 안해도 되었기 때문에 이렇게 구현하는 게 나았다. 유물을 획득하는 것에 있어서는 bfs가 자신이 탐색한 위치들의 벡터를 리턴하도록 하여 구현했다. bfs 결과에 따라서 삭제할지 말지를 결정해야 하기 때문에 이를 리턴함으로써 사이즈가 3보다 작으면 삭제하지 않도록 했다. 침착하게 풀면 생각보다 쉽게 풀 수 있었다.#include #include #i..

이 문제는 구현 문제이다. 나는 이 문제를 읽고 크게 두 파트로 나뉜다고 생각했다. 골렘이 이동하는 파트, 정령이 이동하는 파트 두 개로 분리하여 문제를 풀었다. Golem이라는 구조체를 정의하여 골렘을 나타냈다. 골렘의 한 가운데 좌표를 저장하고, 출구 위치를 저장하는 식으로 구현했다. 골렘 이동을 구현하는 것은 사실 단순하다. 그림에 나와있는 대로 상대 좌표를 검사하고, 모두 비어있으면서 격자를 벗어나지 않으면 이동시키면 된다. 문제는 정령을 이동시키는 것인데, 여기서는 DFS(재귀), BFS 모두 가능하다. 그런데 한 가지 유의할 점은 두 방식 모두에서 반드시 이미 타고 간 골렘은 다시 탐색하지 않아야 한다는 것이다. 처음에 재귀로 문제를 풀었다가 이 부분을 놓치고 BFS로 바꿔 문제를 해결했는데,..

이 문제는 주어진 요구사항을 그대로 구현하면 바로 정답이 나오는 문제이다. 문제에서는 (1, 1) ~ (N, N)으로 좌표를 설정하지만, 나눗셈 연산을 간단하게 하기 위해 (0, 0) ~ (N - 1, N - 1)을 사용했다.  구름의 칸 여부를 위한 cloud 배열과 바구니를 표현하는 bucket 배열 두 개를 사용해서 문제를 풀었다. 보통 이런 시뮬레이션 문제는 전역 배열로 표현하기보다는 이중 벡터로 표현한 다음에 어떤 연산을 수행하고 벡터를 통째로 바꾸는게 정확도도 높고 구현도 편했다. 여기서도 cloud 벡터에 대해서 전체를 갈아버리는 방식으로 구현했다.#include #include #include using namespace std;#define LEFT 0#define UPLEFT 1#def..

이 문제는 구현, 시뮬레이션 문제이다. 문제의 요구사항 자체는 단순했으나 문제 자체가 약간 이해하기 어려웠다. 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가 나오게 된다. 모든 바이러스가 활성화된 바이러..