이분 탐색

[실2] 2512 - 예산

#include #include #include #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ using namespace std; int main() { FAST_IO(); int n, m; cin >> n; vector v(n); for (int i = 0; i > v[i]; sort(v.begin(), v.end()); cin >> m; int s = 0, e = v[n - 1]; int res = 0; while (s = sum) { res = mid; s = mid + 1; } else e = mid - 1; } cout

[실2] 1654 - 랜선 자르기

#include #include #include using namespace std; #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion vector v; int main() { FAST_IO(); long k, n; cin >> k >> n; v.resize(k); for (int i = 0; i > v[i]; sort(v.begin(), v.end()); long l = 1, r = v[k - 1]; long res = 0; while (l = n) { res = mid; l = mid + ..

[실2] 2805 - 나무 자르기

#include #include #include using namespace std; #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion vector v; int main() { FAST_IO(); long n, m; cin >> n >> m; v.resize(n); for (int i = 0; i > v[i]; sort(v.begin(), v.end()); long l = 0, r = v[n - 1]; long res = 0; while (l mid) sum += v[i] - mid; } if..

[골4] 2110 - 공유기 설치

#include #include #include using namespace std; vector v; int main() { int n, c; cin >> n >> c; v.resize(n); for (int i = 0; i > v[i]; sort(v.begin(), v.end()); int l = 1, r = v[n - 1]; int res = 0; while (l

[C++] 이분 탐색 (Binary Search)

이분 탐색(Binary search)이란? - 정렬된 리스트(배열)에서 원하는 값(target)의 존재 여부(존재 위치)를 찾는 알고리즘. - 반드시 리스트(배열)를 정렬해서 사용해야 한다는 단점이 있다. - 탐색할 때마다 검사 범위가 절반으로 줄어든다. - 재귀적인 방법, 반복문, STL를 이용하여 이분 탐색(Binary Search)을 실행할 수 있다. - Time Complexity : O(log N) 변수 설명 1. int low & int high 검사 범위의 시작점, 끝점의 인덱스를 가리키기 위한 변수. left는 시작점을, right를 끝점의 인덱스를 가리킨다. // nums에 수들이 들어가있다고 가정 vector nums; int low = 0; // 초기 세팅: 제일 앞 인덱스 int h..