재원블로그 재원블로그

이 문제는 브루트포스와 백트래킹을 이용하는 구현 문제이다. 이 문제가 브루트포스 문제인것까지 생각했지만, 구현에서 막혔다. 어려운 구현 문제일수록 구현을 최대한 쉽게 하려는 노력이 필요한 것 같다. #include #include using namespace std; bool connected[100][100]; // n : 세로줄, m : 가로줄 개수, h : 가로 위치의 개수 int n, m, h; int answer = INT32_MAX; bool isCorrect() { for (int i = 1; i > m >> h; for (int i = 0; i > a >> b; connected[b][a] = true; } func(1, 0); if (ans..

이 문제는 시뮬레이션 문제로 주어진 순서에 맞춰 구현하면 되지만, 구현이 매우 어렵다. 이 문제에서 가장 어려운 부분은 상어가 움직이는 것인데, 한 상어가 움직인 후 바로 맵에 저장하면 다음 상어가 움직임에서 잘못된 결과가 나오게 된다. 그러므로 모든 상어의 다음 좌표를 따로 저장해둔 뒤, 그 배열을 순회하면서 상어를 맵에 올려놓는 방식으로 구현하면 정답이 나오게 된다. 맵의 경우 구조체로 상어를 만든 뒤, 그 구조체의 2차원 배열로 구현했다. #include #include using namespace std; #define MAX 100 #define UP 1 #define DOWN 2 #define RIGHT 3 #define LEFT 4 typedef struct _shark { int y; in..

이 문제는 시뮬레이션 문제로 주어진 요구사항을 그대로 구현하면 시간 초과 없이 해결할 수 있는 문제이다. 톱니바퀴를 돌리는 구현에 있어서 덱을 사용하여 문제를 해결했다. #include #include #include #include using namespace std; deque gear[4]; #define CLOCK 1 #define COUNTERCLOCK -1 #define N 0 #define S 1 int leftSide(int gearNum) { int temp1 = gear[gearNum].back(); gear[gearNum].pop_back(); int temp2 = gear[gearNum].back(); gear[gearNum].push_back(temp1); return temp2;..

이 문제는 완전 탐색으로 푸는 시뮬레이션 문제이다. 이 문제를 처음 접했을 때는 막막했는데, 한 단계씩 천천히 구현해보니 꽤 쉬운 문제였다. 상하좌우로 움직였을 때 로직을 생각해내는 것이 핵심인데, 나는 이를 큐를 이용해서 구현했다. 또한 전역 배열로 board를 구현하지 않고 이차원 벡터를 매개변수로 주고, 바뀐 벡터를 리턴하는 방식으로 하여 더 쉽게 구현할 수 있었다. #include #include #include #include using namespace std; #define MAX 20 int n; int answer = -1; vector up(vector& board) { vector result(n, vector(n, 0)); for (int x = 0; x < n; x++) { que..

이 문제는 덱을 이용한 시뮬레이션 문제이다. 덱을 이용하여 뱀을 표현하는 생각을 하는 것이 핵심이다. 처음에는 매 초마다 덱을 순회하여 보드에 표시했다가 초가 끝나면 다시 지우는 방식을 생각했으나, 사과의 유무에 상관없이 덱의 front에 추가 하면 되고, 사과가 없으면 덱의 back 부분을 pop 해주면 굳이 썼다 지웠다 할 필요가 없었다. 어려운 구현 문제는 단계를 나눠서 차근차근 풀어나가야 해결할 수 있는 것 같다. #include #include #include using namespace std; #define MAX 100 #define RIGHT 1 #define LEFT 2 #define UP 3 #define DOWN 4 int n, k, l; int board[MAX][MAX]; deq..

이 문제는 시뮬레이션 문제로 주어진 순서에 따라 그대로 구현하면 된다. 한 가지 주의할 점은 미세먼지가 동시에 확산되기 때문에 확산되기 전의 미세먼지 양을 미리 알아두고 그 상태로 확산을 진행해야 정확한 값이 나온다는 것이다. #include #include #include #include using namespace std; #define MAX 50 typedef struct _node { int y; int x; int d; } node; int room[MAX + 1][MAX + 1]; int r, c, t; int dy[] = { -1, 0, 1, 0 }; int dx[] = { 0, -1, 0, 1 }; vector cleaner; bool inRange(int y, int x) { if (1..

이 문제는 구현이 매우 어려운 문제였다. 처음에는 매 반복문마다 row와 column을 체크하는 방식으로 구현했지만, column에 대한 연산 C를 수행할 때 구현이 매우 복잡했고, 정답도 나오지 않았다. 그래서 row와 column을 따로 저장하고 배열 자체는 100 * 100 인 것으로 구현했더니 정답이 나왔다. 유의할 점은 매 연산마다 arr를 초기화해주지 않으면 정답이 나오지 않게 된다는 것이다. #include #include #include #include using namespace std; int r, c, k; int rowSize = 3, columnSize = 3; bool compare(pair &a, pair &b) { if (a.second == b.second) { return..

이 문제는 DFS를 이용해서 푸는 문제이다. 처음에는 BFS를 이용한 풀이를 시도하였으나, 구현이 복잡하고 큐에 추가적인 정보가 많이 들어가야 했다. 그래서 DFS와 백트래킹을 이용하는게 더 쉬울것 같아서 DFS로 문제를 풀었다. 이 문제에서 핵심은 visited 배열이 알파벳에 대한 visited로 만들어내는게 핵심이다. 처음에는 dfs의 매개변수로 알파벳의 방문 여부를 던져주는 방식으로 하였으나, 이는 시간 초과가 발생했다. 알파벳에 대한 visited를 이용하면 알파벳 26개가 모두 채워지면 당연히 dfs가 더 이상 진전할 수 없으므로 시간 초과가 발생하지 않는다. #include #include #include #include using namespace std; #define MAX 20 int..