이분_탐색

[C++] 백준 2110번 공유기 설치

이분 탐색 문제. 시간 복잡도가 이게 되나? 생각되는 문제지만 이분 탐색 + 되는지 순차적으로 확인 해주면 풀리는 문제이다. 많이 틀렸었는데, 이유는 이분탐색 최소부분을 1부터 시작하지 않고 집의 번호들 중 가장 작은 부분부터 시작해서 틀렸다. 문제풀이 이분 탐색을 하면서 나오는 숫자들을 하나씩 가능한지 여부를 살펴보면 된다. 이분 탐색은 늘 그렇듯 front < tail일 때까지 고려해주면 된다. front는 1로 시작해야한다. 처음에 이 부분을 간과해서 집 번호 중 가장 작은 부분부터 시작해서 틀렸다. 만일 집이 3개가 있고 2개의 공유기를 설치한다고 해보자. 집의 번호가 각각 10000, 10001, 10002 이렇게 있다면 가장 멀리 공유기를 설치하는 법은 10000, 10002 이렇게 된다. 따..

[C++] 백준 1654번 랜선 자르기

이분 탐색 문제. 이분 탐색 문제이고 실버3 문제임에도 고려해줄 사항이 생각보다 많아서 반례를 한번 찾아보고 풀었다. 처음 문제를 봤을 때 처음에는 우선순위 큐로 만들어서 긴 랜선들을 자르는 식으로 구현해보려고 했다. 그런데 문제 아래에 힌트를 보면 이렇게 나와있었고, 결국 우선순위 큐를 이용하는 그리디 방식의 풀이는 틀렸다는 것을 알게됐다. 랜선 자르기 같은 문제를 예전에 풀었던 적이 있었는데, 이분 탐색으로 풀었던 기억이 있어서 이분탐색으로 시도했고, 몇번 구상해보니 확실히 이분탐색이라는 것을 알게됐다. 문제 풀이 문제가 이분탐색이라는 것을 알게되면 그 뒤로는 간단하다. 나같은 경우는 vector 배열에 담고, algorithm STL에 있는 sort 메서드를 사용해서 정렬해 준 후에 1 ~ [입력받..

[C++] 백준 1920번 수 찾기

이런 문제를 보면 바로 이분탐색부터 떠올려야 한다. big-O 표기법에 따르면 탐색 알고리즘에서 가장 시간소요가 적은 것이 O(NlogN)인데 쉽게 접근할 수 있는게 이분탐색이다. STL 제약이 없기 때문에 vector에 값들을 넣은 후 algorithm STL을 사용해서 sort와 binary_search 메서드를 사용했다. 이렇게 풀면 정말 가볍게 풀 수 있지만 이분 탐색 정도는 구현을 하라는 목적인 것 같았다. head와 tail (보통 left와 right로 표현하는 것 같다.) 그리고 mid를 정해놓고 남은 살펴볼 개수를 절반씩 줄여나가는 방식이다. 물론 STL을 사용할 수 있다면 그냥 algorithm STL을 사용해서 만들면 된다. (사실 STL 없이 sort하라고 하면 정말 답없을 것 같다..