문제BOJ 2343번 기타 레슨https://www.acmicpc.net/problem/2343 문제풀이시간복잡도 고려하기N의 최댓값이 100,000이므로 O(NlgN)으로 풀어야 한다. 구현 아이디어제약 조건1. 정렬되어 있지 않은 벡터를 순서대로 더해야 한다.2. M개를 모두 사용해야 한다.3. 모든 블루레이의 크기가 동일해야 한다.???이분 탐색을 4일째 풀고 있지만 이번에는 아이디어가 좀처럼 떠오르지 않았다.단순히 강의가 들어있는 크기가 N인 벡터를 이분탐색하면 정렬되어 있지 않기 때문에 답이 나오지 않는다.일단 STL을 활용하여 쓸 수는 없으므로 직접 이분탐색을 구현해야 하고 이분탐색을 할 대상은 강의의 길이를 저장한 벡터가 아니라는 것은 알아냈다.강의 길이의 합을 이분탐색하기이분탐색 시작점 ..
문제BOJ 11663번 선분 위의 점https://www.acmicpc.net/problem/11663 문제풀이시간복잡도 고려하기N의 최댓값이 100000이므로 O(NlgN)의 풀이로 풀어야 한다. O(N^2)의 풀이인 배열탐색으로는 시간초과가 발생한다. 따라서 이분탐색을 활용해서 풀어야 한다. 구현 아이디어주어진 조건 1. 크기가 N인 탐색할 배열 또는 벡터2. 탐색 범위 (선분 시작점, 선분 끝점)3. 범위 내 조건을 만족하는 개수를 구해야 한다.STL 활용binary_search() 함수는 벡터 안에 값이 있는지 없는지만 알려주므로 딱히 도움이 되지 않는다.lower_bound() 함수는 벡터에서 찾고자 하는 값보다 작지 않은 첫 번째 요소를 가리키는 iterator를 반환한다.upper_boun..
문제미들러 문제https://www.acmicpc.net/problem/1654 학습 키워드이분탐색 직접 구현하기문제 풀이 및 해결 방법처음에는 이분탐색으로 풀지 않고 빠르게 풀어보았다.#include#includeusing namespace std;int main() { ios::sync_with_stdio(0); cin.tie(0); // 가지고 있는 랜선의 개수 K // 필요한 랜선의 개수 N int K, N; cin >> K >> N; vector V; int sum = 0; for (int i = 0; i > a; V.push_back(a); sum += a; } int maximum = sum / N; while (maximum--) { int cnt = 0; for (int i = 0..
