Doby's Lab

이번 문제도 분할 정복이다. 다만 이번 문제는 2차원 배열을 사용하지 못한다. 32769 x 32769 사이즈의 배열을 선언해야 했어서 이는 엄청 크기 때문에 선언하지 못한다. 그래서 배열 없이 접근했다. '0행의 0열 0부터 시작' 같은 키워드는 이번 문제에서 유독 헷갈렸었기 때문에 행과 열은 1부터 시작하고 1부터 시작하게 하여 마지막 결과 값에 -1을 해주었다. 분할 정복 함수에서 각 사분면에 해당하는 조건들을 달고, 함수의 재귀를 거치면서 입력한 행렬과 함수의 도출 행렬이 같다면 함수를 종료하고, 해당하는 결과 값에 -1을 해준 뒤에 출력하고 함수를 종료시켰다. #include #include #include using namespace std; // 배열 사이즈가 너무 커진다. >> 꼭 배열을 ..

이번 문제는 첫 공식적인(?) 분할 정복 문제다. 의외로 간단하게 풀었었다. '다만 생각을 조금만 더 해볼 걸'이라는 아쉬움이 있었다. '설마 하나하나 다 검사하겠어'라는 생각에 한 번이라도 구현했으면 시간 아꼈을 텐데 포인트 이번 분할 정복의 포인트는 문제에서 얻을 수 있었다. n이 2의 제곱수로 주어지고, 색종이들 또한 2의 제곱수 형태로 존재하기 때문에 N / 2로 분할해나가면서 리커시브 콜을 하면 됐었다. 맨 위에서 말한 '설마 하나하나 다 검사하겠어'라는 생각을 구현하면 된다. 소스 코드 #include #include using namespace std; int n; int map[129][129] = { 0, }; int white = 0; // 0 int blue = 0; // 1 void..

입력값을 넣을 때마다 즉각적으로 정렬을 시키면 되는 문제가 아닐까를 생각했지만 정렬의 시간 복잡도 O(NlogN), 연산의 최대 개수가 1,000,000이므로 이는 시간 초과를 발생시킨다. 즉, 이번 문제에서는 우선순위 큐(priority queue)의 사용을 유도한다. 큐의 특성상 pop(D)를 할 때는 앞에서 밖에 할 수 없기 때문에 두 개의 우선순위 큐를 선언해주었다. 오름차순과 내림차순. 두 개의 큐를 선언하여 풀었던 코드는 다음과 같다. #include #include #include #include #define ll long long using namespace std; int main() { int T; cin >> T; for (int i = 0; i < T; i++) { int n; c..

이번 문제는 꽤나 어려웠다. 어려웠던 포인트들을 정리해보면 1. DFS로 풀어야 할지 BFS로 풀어야 할지를 아직 헷갈린다. 2. DFS로 풀어야 할 땐 동작원리를 알고 있어도 어떠한 논리로 접근해야 하는지 모르겠다. 이번 문제는 BFS로 첫 시도를 했었다. 높이가 낮아지다가 다시 높아지는 시점을 두고 이를 경계선이라고 생각하며 구역을 나누어 각 구역을 산봉우리로 취급하려 했었다. 하지만, 이를 표현하는 데에 있어서 산 중턱에서 BFS가 돼버리면 구하려는 구역 이상의 수가 도출되기 때문에 다음 코드로는 답을 도출해낼 수 없었다. 그래서, flag 변수나 min값을 도입해 봤지만 풀리지 않았다. #include #include #include using namespace std; int n, m; int ..

이번 문제에서 크게 어려웠던 점은 없었으나 각 문제에 대한 포인트를 항상 블로그에 담아두려 하기 때문에 가져왔다. 문제에서 헷갈릴 수 있는 건 visited의 리셋이었다. 비의 높이에 따라 bfs를 해주며 건물의 개수를 cnt하며 배열에 따로 담았었다. 하지만, cnt를 담은 배열을 디버깅해보니 처음을 제외하고는 전부 0이었다. 이 부분에서 visited를 초기화시키지 않았구나라는 것을 알고 reset 함수를 작성하고, 비에 높이에 따라 건물 cnt가 끝날 때마다 reset 함수를 콜 해주었다. [코드] #include #include #include #include using namespace std; int map[101][101] = { 0, }; bool visited[101][101] = { 0..

이번 문제는 당연하게 나머지 정리(MOD의 연산)를 이용해 풀 수 있을 거라 생각했다. 왜냐하면 거듭제곱을 할수록 수는 기하급수적으로 엄청 커질 것이기 때문에 즉각적으로 이를 처리할 수 있는 나머지 정리를 사용하는 것이 필수적이라 생각했다. 하지만, 거듭제곱의 연산 또한 2,147,483,647 이하의 수가 주어지기 때문에 시간 초과를 발생시킬 것이라 확신했다. 어떠한 솔루션이 떠오르지 않았고, 이 문제는 '분할 정복을 이용한 거듭제곱' 이란 키워드로 분류되어있었기 때문에 분할 정복에 대해 알아보기로 했다. 이번 문제에서 사용된 나머지 정리 연산 규칙성 (A * B) mod N = (A mod N * B mod N) mod N 가정: 어떠한 값을 A라 두고, 나누는 수가 N이라고 했을 때 A mod N은..

이번 문제는 BFS로 풀려고 했다. [당시 썼던 BFS 코드] void bfs(int row, int col) { queue q; q.push(make_pair(row, col)); while (!q.empty()) { int y = q.front().first; int x = q.front().second; q.pop(); for (int i = 0; i = 1 && dy = 1 && dx > 앞 길에 'A'가 있는데 1, 1에서 출발한 길에선 아직 'A'가 나오지 않아서 가야 하지만 다른 길에서 이미 'A'가 나와서 가지 못하는 것으로 판단하는 것을 말한다. [DFS를 사용한 이유] ..

이번 문제는 이분 탐색이라는 전제가 없었다면 풀 수 없었을 것이다. 이분 탐색이라는 전제가 있어도 논리에 접근하기 까다로운 문제였다. 걸리는 시간을 여러 값으로 추정하며 이분 탐색으로 도달하는 문제다. 논리에 접근했던 방법 처음엔 최소 시간이 걸리는 검색대에 사람들이 몰리게 해야겠다는 생각이 들었다. >> 검색대의 시간들을 배열에 담아 정렬시켰다. 그래서 걸리는 시간(mid)이 주어지면 그 시간 안에 최소 시간 검색대에 몇 명의 사람이 올 수 있는지 카운트해주었다. >> sum을 선언하고 sum이 mid가 될 때까지 걸리는 시간을 더해준 후에 mid가 되면 다음 시간 검색대에서 같은 과정을 반복해주었다. for (int i = 0; i < times.size(); i++) { ll sum = 0; whi..