[C++/코테] 이진탐색 - 개념, 백준 예제

기본 문제는 STL sort, binary_search등을 사용해서 쉽게 해결할 수 있지만, 응용이 되면 어려운 주제.

이분탐색

• 오름차순 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법
• 선형탐색이 $O(N)$에 동작한다면, 이분탐색은 $O(logN)$에 동작한다.

기본 연습문제

백준 1920: 수 찾기: https://www.acmicpc.net/problem/1920

✔️ 배열 속 원소 찾

✔️ 정렬 $O(NlogN)$ +  이분탐색 $O(MlogN)$ 에 풀이가 가능하다.

✔️ st, mid (=${st+en}\over{2}$), en 인덱스 변수를 활용한다.

1920번: 수 찾기

1920번 해답

#include <bits/stdc++.h>
using namespace std;

int a[100005];
int n;

int binarysearch(int target)
{
    int st = 0;
    int en = n - 1;

    while (st <= en)
    {
        int mid = (st + en) / 2;
        if (a[mid] < target)
            st = mid + 1;
        else if (a[mid] > target)
            en = mid - 1;
        else
            return 1;
    }
    return 0;
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);

    int m;
    cin >> m;

    while (m--)
    {
        int t;
        cin >> t;
        cout << binarysearch(t) << '\n';
    }
}

 

백준 10816 숫자 카드2: https://www.acmicpc.net/problem/10816

✔️ 배열 속 원소 등장 횟수 찾기

✔️ STL binary_search 함수는 단순히 등장 여부만을 알려준다. → 해당 응용 문제에 사용 x

✔️ 삽입할 수가 주어졌을 때, 오름차순이 지켜지며 삽입 가능한 첫(가장 왼쪽) 위치와 끝(가장 오른쪽) 위치의 차이가 곧 등장 횟수이다.

10816번: 숫자 카드 2

⭐ STL에 lower_bound, upper_bound 함수가 정의되어있다. 

주의사항

• 이분탐색을 하고자 한다면 주어진 배열은 정렬되어 있어야 한다.
• 무한 루프에 빠지지 않게 mid 값을 정해야 한다.
  • 구간을 균등하게 나누어 주어야 한다. st와 en이 1차이 날 때를 주의 깊게 보면 힌트가 된다.

응용 연습문제

백준 18870 좌표 압축: https://www.acmicpc.net/problem/18870

✔️ 좌표 압충, 중복 제거

✔️ 좌표 압축은 입력 값의 범위가 $1~10^9$ 로 큰데, 배열 인덱스로 사용하고 싶을 때 활용할 수 있다.

18870번: 좌표 압축

⭐ 정렬된 배열에 대해 중복 제거해주는 함수가 STL에 내장되어 있다. - unique와 erase 활용

 

백준 2295 세 수의 합: https://www.acmicpc.net/problem/2295

✔️ 뺄셈은 곧 덧셈으로 바꾸어 풀 수 있다.

2295번: 세 수의 합

Parametric Search

• 조건을 만족하는 최소/최댓값을 구하는 문제(최적화 문제)를 결정 문제로 변환해 이분 탐색을 수행하는 방법
• 문제의 분류가 parametric search인 것을 알아차리는 것부터 어렵다. 상황에 따라 포기해야 할 때는 포기하는 게 좋음..!

백준 1654 랜선 자르기 https://www.acmicpc.net/problem/1654

✔️ 대표적인 parametric search 유형 문제

1654번: 랜선 자르기

• 위 예제 문제처럼, 이분탐색을 수행할 변수로 함수를 그렸을 때, 감소/증가함수여야 parametric search로 풀 수 있다.

---

출처: https://blog.encrypted.gg/985

[실전 알고리즘] 0x13강 - 이분탐색