초고교급 희망

개요 이분탐색의 개념자체는 쉽다. 심지어 stl에 이미 함수가 있어서 직접 구현할 필요조차 없다. 하지만 조금만 꼬아서 내도 문제 난이도가 저세상으로 간다. 그러니 코딩 테스트에서 킬러 문항으로 자주 출제되는 이분탐색 응용 문제 공략에 대해 알아보자! 이분탐색이란? 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법 시간 복잡도는 O(logN)이다. C++ STL의 이분탐색 시간 복잡도 STL에 있는 이분탐색 함수도 O(logN)이다. 헤더 파일 에 std::binary_search가 있다. 이분탐색을 하기 위해선 정렬이 필수인데 std::sort 또한 에 있다. binary_search template bool binary_search (ForwardItera..

찾고자하는 숫자가 얼마나 많이 있는지 구하는 문제였다. C++ STL에 있는 lower_bound와 upper_bound를 사용해도 좋지만 직접 구현하여도 좋다. 하지만 실제 시험에서는 제한 시간이 모자라거나, 긴장해서 실수할 수도 있기 때문에 STL을 쓰는 것이 더 좋을 것 같다. #include #include using namespace std; int n, m; int a[500001]; int lower_idx(int target, int n) { int st = 0; int ed = n; while (st < ed) { int mid = (st + ed) / 2; if (a[mid] < target) { st = mid + 1; mid = (st + ed) / 2; } else if (a[mi..

이분탐색을 이용한 문제였다. 이분탐색을 직접 구현해주어도 좋지만, STL에 있는 binary_search를 이용하여 빠르게 풀어주었다. 실제 코딩테스트에서는 시간이 부족한 경우가 많기 때문에 STL을 활용할 수 있다면 최대한 도움을 받고, 다음 문제를 풀러가는 것이 좋은 것 같다. 그리고 이분탐색 하기 전에 데이터 정렬하는 것 잊지 말기 #include #include #include using namespace std; int main() { int n, m; vector v; scanf("%d", &n); for (int i = 0; i < n; i++) { int temp; scanf("%d", &temp); v.push_back(temp); } sort(v.begin(), v.end()); sca..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱..