재원블로그 재원블로그

이 문제는 구현이 매우 어려운 문제였다. 처음에는 매 반복문마다 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..

이 문제는 bfs를 이용한 문제이다. 최단 경로로 움직였을 때 1번 노드에서 가장 먼 노드의 개수를 구하는 문제로, bfs를 실행한 뒤 visited 배열에서 구하면 되는 간단한 문제이다. #include #include #include #include #include using namespace std; #define MAX 20000 vector edges[MAX + 1]; int visited[MAX + 1]; void bfs(int start) { queue q; visited[start] = 1; q.push(start); while (!q.empty()) { int present = q.front(); q.pop(); for (int i = 0; i < edges[present].size();..

이 문제는 전형적인 시뮬레이션 문제이다. 문제에서 주어진 그대로 수행하면 정답이 나오지만, 여기서 핵심은 시간 제한이 C++ 기준 0.3초라는 것이다. 처음에는 우선순위 큐를 이용해서 문제를 풀었지만, 시간 초과가 나왔다. 이는 우선순위 큐를 이용하면 우선순위 큐를 모두 비웠다가 다시 채우는 것을 N * N번 반복해야 하기 때문이다. 봄에만 나무를 이용한 연산이 필요하기 때문에 봄에만 sort 연산을 해주었더니 정답이 나왔다. #include #include #include using namespace std; #define MAX 10 int n, m, k; int arr[MAX + 1][MAX + 1]; vector land; vector trees[MAX + 1][MAX + 1]; int dy[] ..

이 문제는 완전 탐색 문제임을 판단하는 것이 중요하다. 가로와 세로의 길이가 각각 최대 500000이기 때문에, 이차원 배열을 만들 수 없다. 하지만 별똥별의 개수가 최대 100개이므로 나올 수 있는 좌표의 최대 가짓수는 100 * 100 = 10000 이고, 트램펄린을 설정한 뒤 이 안에 들어있지 않은 별똥별의 개수를 세는 것 또한 100번이 들기 때문에 1000000 번의 연산이면 가능하다. k를 이용한 완전 탐색을 수행해야한다는 것까지는 생각해냈지만, 좌표의 모든 가짓수로 트램펄린을 좌상단으로 설정하는 것은 생각하지 못해 아쉬운 문제였다. 또한 트램펄린의 모서리까지도 튕겨낸다는 것은 endY가 startY + l이 됨을 의미하는 것도 생각하지 못했다. #include #include #include..

이 문제는 문자열에서 슬라이딩 윈도우를 사용해서 푸는 문제이다. 사실 부분 문자열의 길이를 판단하는데 슬라이딩 윈도우가 사용되는 것이지 이 문제의 핵심은 완전 탐색이 가능하다는 것을 판단하는 것 같다. 이 문제에서 게임의 수가 T번이고 최대 100번이다. 문자열의 최대 길이는 10000이고, 알파벳의 개수는 26개이다. 이를 모두 곱하면 26000000번이므로 1억번보다 작아 완전 탐색이 가능하다. 알파벳 하나마다 인덱스를 각각 저장하고, 인덱스들의 차이를 통해 부분 문자열의 길이를 도출해낸다. 이 때 슬라이딩 윈도우 기법이 사용되지만 이는 굳이 이 문제가 슬라이딩 윈도우 문제라는 것을 몰라도 자연스럽게 사용하게 된다. #include #include #include #include using names..

이 문제는 완전 탐색을 이용해서 풀 수 있는 시뮬레이션 문제이다. 구현이 상당히 복잡하기 때문에, 기능에 따라 함수를 나누어 구현하는 것이 쉽게 구현할 수 있는 방법이다. cctv의 수도 매우 적고, 전체 맵도 크지 않기 때문에 완전 탐색으로 풀 수 있다. #include #include #include #include using namespace std; #define MAX 8 #define UP 0 #define RIGHT 1 #define DOWN 2 #define LEFT 3 int n, m; int matrix[MAX + 1][MAX + 1]; vector cctv1 = { {UP}, {RIGHT}, {DOWN}, {LEFT} }; vector cctv2 = { {LEFT, RIGHT}, {U..

이 문제는 다이나믹 프로그래밍으로 푸는 문제이다. 처음에는 (1,1) 부터 (m,n) 까지 가는 최단경로라는 말만 보고 bfs를 떠올려 풀었지만, 이 문제는 최단경로의 개수를 묻는 문제였다. 핵심은 오른쪽과 아래로만 갈 수 없다는 것인데, 이는 (m,n)까지 도달만 하면 무조건 최단경로가 되는 것이다. (1,1)에서 (m,n)으로 가는데 오른쪽과 아래밖에 못간다면 결국 오른쪽으로 m번, 아래로 n번 가야 최단경로이기 때문이다. 이 문제에서 주의할 점은 y좌표와 x좌표가 반대로 되어있다는 것이다. #include #include #include #include using namespace std; int matrix[101][101]; int dp[101][101]; int dy[] = {0, 1}; in..