https://www.acmicpc.net/problem/1654이분탐색을 응용하는 문제이다.N의 개수와 맞는 최대 길이를 구해야 하는데, 가능한 범위 (1 ~ 랜선 최대 길이)에서 확인해가면서 값을 찾아야 한다.#include #include using namespace std;vector list;int N;int calculate(unsigned int start, unsigned int end, int ans){ if (start > end) return ans; unsigned int len = (start + end) / 2; int count = 0; for (int i = 0; i = N) return calculate(len + 1, end, ans > len ? ans : len);..

https://www.acmicpc.net/problem/10816주어지는 수의 범위가 굉장히 크기 때문에, 시간초과에 유의해서 풀어야 한다.#include #include #include using namespace std;int main(){ cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); int N, M; vector list; vector input; cin >> N; for (int i = 0; i > temp; list.push_back(temp); } sort(list.begin(), list.end()); cin >> M; for (int i = 0; i > temp; input.push_back(temp); } for (int i = ..

https://www.acmicpc.net/problem/2164설명만 봐도 queue를 사용해서 풀 수 있는 간단한 문제라는 것을 알 수 있다.#include #include using namespace std;int main(){ queue que; int N; cin >> N; for (int i = 1; i

https://www.acmicpc.net/problem/1764시간초과를 잘 처리해야 하는 문제이다.#include #include using namespace std;int main(){ cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); int N, M; set list; set ans; cin >> N >> M; for (int i = 0; i > temp; list.insert(temp); } for (int i = 0; i > temp; auto check = list.find(temp); if (check != list.end()) ans.insert(temp); } cout 시간초과를 방지하기 위해 tie와 sync_with_std..

https://www.acmicpc.net/problem/1920첫번째로 주어진 N개의 정수 사이에, M개로 주어진 정수들이 포함되어 있는지 확인하는 문제이다.이분 탐색으로 해결하지 않으면 시간 초과에 걸릴 가능성이 높기 때문에 정렬 후 이분탐색으로 구현하였다.#include #include #include using namespace std;vector list;vector input;int findValue(int value, int v1, int v2){ if (v1 > v2) return 0; int mid = (v1 + v2) / 2; if (value == list.at(mid)) return 1; else if (value > list.at(mid)) return findValue(va..

https://www.acmicpc.net/problem/11866solved.ac Class 2 에센셜에 포함되어 있는 구현 문제이다.#include #include using namespace std;int main(){ int list[1001] = { 0, }; int N, K; cin >> N >> K; int idx = K; vector ans; for (int i = 1; i = N) break; else { int move = 0; while (move N) idx = 1; else idx += 1; if (list[idx] != 0) move++; } } } cout \n"; return 0;}while문 안에 while문이 또 있어 ..

https://www.acmicpc.net/problem/7562문제에서 주어진 내용에 있는 '최소 몇 번' 이라는 문구를 보고 BFS로 풀었다.#include #include #include using namespace std;vector> answer;vector> visited;int dx[8] = { -2, -1, 1, 2, -2, -1, 1, 2 };int dy[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };void bfs(int X, int Y, int I){ queue> que; visited[Y].at(X) = true; que.push(make_pair(Y, X)); while (!que.empty()) { int currentY = que.front().first; ..

https://www.acmicpc.net/problem/1697이전글에 풀었던 미로 탐색에서 사용하였던 방법을 응용하면 되는 문제이다.#include #include #include using namespace std;vector list;vector visited;vector answer;void bfs(int start){ int size = list.size(); queue que; que.push(start); visited[start] = true; while (!que.empty()) { int current = que.front(); que.pop(); if (current - 1 >= 0) { if (!visited[current - 1]) { que.push(curr..

https://www.acmicpc.net/problem/2178최소 칸 수를 확인하기 위해서 DFS보다는 BFS로 푸는 것이 좋다고 하여, BFS로 풀어보았다.#include #include #include #include using namespace std;vector maze;vector> visited;vector> answer;int N, M;int dx[4] = { -1, 0, 1, 0 };int dy[4] = { 0, 1, 0, -1 };void bfs(){ queue> que; int x, y = 0; visited[0].at(0) = true; answer[0].at(0) = 1; que.push(make_pair(0, 0)); while (!que.empty()) { y = que.f..

https://www.acmicpc.net/problem/1012이 전에 풀었던 단지번호붙이기와 비슷한 유형의 그래프 탐색 문제이다.DFS로 구현하였다.#include #include #include using namespace std;vector> list;vector> visited;vector answer;int dx[4] = { -1, 0, 1, 0 };int dy[4] = { 0, 1, 0, -1 };int M, N;void dfs(int x, int y){ for (int i = 0; i = 0 && nextX = 0 && nextY > M >> N >> K; list = vector>(N, vector(M, 0)); visited = vector>(N, vector(M, false)); fo..