초고교급 희망

개요 이분탐색의 개념자체는 쉽다. 심지어 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..