너와 나의 스토리

문제: https://www.acmicpc.net/problem/8983 문제 풀이: 어떤 동물을 잡을 수 있는지 알기 위해 모든 사대와 거리를 계산하면 총 수행 시간은 O(n*m)으로 시간 초과가 난다. binary search 알고리즘을 이용하면 시간을 줄일 수 있다! 1. 사대의 위치를 입력받고 정렬한다. 2. 동물의 위치를 입력받는다. 3. 그 동물과 가장 가까운 곳에 위치한 사대의 위치를 binary search를 이용하여 찾는다. lower_bound를 찾은 다음 [해당 index]와 [index-1] 중 동물과 가까운 곳을 뽑아 거리를 계산한다. 아래 소스코드에는 lower_bound를 구현하였으나, index = lower_bound(vector.begin(), vector.end(), 동..

문제: https://programmers.co.kr/learn/courses/30/lessons/64062 문제 풀이: 건널 수 있는 "니니지 친구들"의 수를 binary search를 이용하여 구한다. binary search로 건널 사람의 수를 먼저 정한 후, 징검다리를 스캔하면서 (현재 징검다리 수 - 건넌 사람 수)가 0 미만인 연속된 징검다리의 수가 k개 이상이면 건널 사람 수를 줄이는 식으로 구현하면 된다. * 마지막 사람이 지난 후, 징검다리 숫자가 줄어드는 것이기 때문에, 지금 막 0이 된 경우는 건널 수 있는 것으로 판단한다. 소스 코드: int solution(vector stones, int k) { int answer = 0; int l = 0,r=200000000; while (..

문제: https://www.acmicpc.net/problem/1654 문제 풀이: binary search 알고리즘을 이용하여 가능한 최대 길이를 찾는다. 소스 코드: 더보기 #include #include #include using namespace std; typedef long long ll; ll k, n,arr[10002]; ll sum; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> k >> n; for (int i = 0; i >arr[i]; ll l = 1, r = pow(2,31)-1; ll res = 0; while (l > 1; sum = 0; for (int ..

문제: https://www.acmicpc.net/problem/15790 문제 풀이: 활의 길이를 기준으로 이분 탐색 (mid=활의 길이) 어떤 홈을 기준으로 시작해서 다음 홈까지의 길이가 mid 이상이면 그 곳을 절단하고, 또, 그 곳부터 길이가 mid 이상인 홈을 만나면 절단. 3겹으로 만든다고 하면, 맨 처음에 시작 점은 이미 골라져 있으므로 2개를 더 찾아 자르고, 마지막 점에서 처음 절단한 곳까지의 길이 또한 mid 이상이면 활의 길이는 mid로 만들 수 있다 주의할 점은, 시작하는 점이 항상 맨 처음 홈이 아닐 수도 있으므로 모든 홈을 처음 홈으로 설정하고 작업 해준다. * 헤헷 남들은 8~40ms 걸리는데 난 104ms나 걸리넹 ㅎㅎ 소스 코드: int n, m, k; vector v; b..

문제: https://www.acmicpc.net/problem/15732 문제 풀이: 1. A,B,C 입력 받음 수형이는 A번 상자부터 B번 상자까지 C개 간격으로 도토리를 하나씩 더 넣는 규칙을 만들었다 -> vector v에 넣는다 // {{처음 상자,끝 상자}, 간격} 2. 이분 탐색 현재 위치(mid)까지의 도토리 개수를 구하고 도토리 개수보다 많은지 적은지 비교 int l = 0, r = 1000000; while (l > 1; int t = 0; for (int i = 0; i k) break; else if (v[i].first.first > mid) continue; if (v[i].first...