https://www.acmicpc.net/problem/2805간단하게 생각해서 맨 위에서부터 잘라나가면 정답을 찾을 수 있지 않을까? 지만N, M의 범위가 굉장히 크기 때문에 시간 초과가 발생할 것이다. 그렇기 때문에 이분 탐색을 활용해 문제를 풀어야 한다.#include #include #include using namespace std;int N, M;vector list;int solve(){ int answer = 0; int minValue = 0; int maxValue = list[N - 1]; while (minValue midValue) sum += list[i] - midValue; } if (sum > M) { minValue = midValue + 1; ans..

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/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/10815 브루트포스 방식으로 모든 숫자 카드들을 비교하면 시간 초과로 해결하지 못하는 문제이다. 시간 단축을 위해 이분 탐색을 활용해 숫자 카드들을 비교할 것이다. 이분탐색은 한 리스트에 있는 데이터들의 탐색 범위를 점점 좁혀나가면서 구분하는 방식이다. 시작 노드 및 끝노드 인덱스를 더한 뒤 2로 나누어 중간 인덱스를 구하고, 그 값과 원하는 타겟값을 비교해서 targer > list[mid]인 경우 시작 노드값을 올리고, 반대인 경우는 끝 노드의 값을 올려가면서 찾는다. 이 이분 탐색은 반복문(while)을 사용한 방법과 재귀를 사용한 방법, 두 가지가 존재하는데 필자는 재귀를 좋아하기 때문에 재귀 방식을 사용하였다. #include #incl..