[중급 알고리즘] 이분 탐색

이분 탐색

💚 1790 수 이어 쓰기2

#include <iostream>

using namespace std;
// 1부터 n까지의 수 길이 구하기
long long calc(int n) {
    long long ans = 0;
    for(int start = 1, len = 1;start <= n; start *= 10, len++) {
        // 현재 자릿수의 마지막 수
        // start: 1 end: 9
        // start: 10 ebd: 99
        int end = start * 10 - 1;
        // 만약 해당 자릿수보다
        if(end > n) {
            end = n;
        }
        ans += (long long)(end - start + 1) * len;
    }

    return ans;
}
int main() {
    int n;
    long long k;
    cin >> n >> k;

    if(calc(n) < k) {
        cout << -1 << endl;
        return 0;
    }

    // n의 범위(left ~ right)
    int left = 1;
    int right = n;
    int ans = 0;

    while(left <= right) {
        int mid = (left + right) / 2;
        long long len = calc(mid);
        if(len < k) {
            left = mid + 1;
        }
        else {
            // k까지의 길이에 맞추는 것이 아니라
            // k번째 수를 포함할 수 있는 수를 구하는 것
            ans = mid;
            right = mid - 1;
        }
    }

    // 탐색 완료된 n을 string으로
    string s = to_string(ans);

    // 전체 길이
    long long l = calc(ans);
    // 문자열을 뒤에서부터 접근한다고 생각하면 편하다.
    // l: 1~ ans까지의 전체 길이
    // k: 최종적으로 접근하고자 하는 인덱스
    // l - k : 뒤에서부터 k번째 수에 접근하기 위해 빼야하는 수
    // 인덱스는 0부터 시작이기 때문에 1도 빼야함
    cout << s[s.length() - (l - k) - 1] << '\n';
    return 0;

}

 

💚2110 공유기 설치

최소값의 최대값, 최대값의 최소값을 구하라는 문제는 대부분 이분 탐색으로 풀 수 있다.

가장 인접한 두 공유기 사이의 거리를 미리 정해둔다. 이걸 유지하면서 공유기를 설치할 수 있는지 확인한다.

 

가장 인접한 두 공유기 사이의 거리를 k로 결정했을 때 공유기를 D개 설치할 수 있고

C <= D라면 공유기를 C개 설치할 수 있는 것과 같다.

가장 인접한 두 공유기 사이의 거리가 k가 되게 유지하면서 D - C개를 제거하면 되기 때문이다.

 

💚1939 중량 제한

 

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
// 인접 리스트
vector<pair<int,int>> a[10001];
// DFS를 위한 방문 여부 확인
bool c[10001];
int n, m;
int st, ed;
bool go(int node, int limit) {
    if(c[node]) {
        return false;
    }
    c[node] = true;
    if(node == ed) {
        return true;
    }
    for(auto &p : a[node]) {
        int next = p.first;
        int cost = p.second;
        if(cost >= limit) {
            // true인 경우에만 return
            if(go(next, limit)) {
                return true;
            }
        }
    }

    return false;
}
int main() {
    cin >> n >> m;
    while(m--) {
        int x, y, z;
        cin >> x >> y >> z;
        a[x].push_back({y, z});
        a[y].push_back({x, z});
    }

    cin >> st >> ed;
    int left = 1;
    int right = 1000000000;
    int ans = 0;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        memset(c, false, sizeof(c));
        if(go(st, mid)) {
            ans = mid;
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    cout << ans << '\n';
    return 0;
}

💚 2022 사다리

실수에서의 이분탐색

그래서 이전처럼 left = mid + 1, right = mid - 1 불가능

대신 각각 left = mid, right = mid로 변경

그러면 전체적으로 이분 탐색을 이어나가는 while(left <= right) 사용 불가능

대신 for(int k = 0;k < 10000;k++), while(abs(right - left) > 1e-6) 중 하나로 사용

abs(right - left) <= 1e-6 → 소수점 6째자리까지는 동일하다는 의미. 문제에서는 소수점 셋째자리까지라고 명시되어있으나 6째자리까지 동일성 여부를 검토한다고 해서 문제되는 건 없기 때문

 

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    double x, y, c;

    while(scanf("%lf %lf %lf", &x, &y, &c) == 3) {
        double left = 0;
        double right = min(x, y);
        for(int k = 0;k < 10000;k++) {
            double mid = (left + right) / 2.0;
            double d = mid;
            double h1 = sqrt(x * x - d * d);
            double h2 = sqrt(y * y - d * d);
            double h = (h1 * h2) / (h1 + h2);
            // 실수에서의 이분 탐색
            if(h > c) {
                left = mid;
            }
            else {
                right = mid;
            }
        }
        printf("%.3lf\n", left);
    }
    return 0;
}

삼분 탐색(Ternery Search)

- 최소값 또는 최대값이 하나인 함수(Unimodal function) 최소/최대값을 찾는 방법

- 이분 탐색과 비슷하지만 삼등분을 한다.

 

💚11664 선분과 점

- 3차원 좌표 평면 위에 선분 하나와 점 하나가 있을 때

- 선분과 점 사이의 거리의 최소값을 구하는 문제

 

방법 1) 선분의 방정식

방법 2) 삼분 탐색

선분과 점 사이의 거리는 가까워졌다가 멀어진다.

즉 삼분 탐색을 이용해 최소값을 구할 수 있다.

 

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;


double dist(double x1, double y1, double z1, double x2, double y2, double z2) {
    return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + (z2 - z1) * (z2 - z1));
}

int main() {
    double x1, y1, z1, x2, y2, z2, x3, y3, z3;
    cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2 >> x3 >> y3 >> z3;
    double dx = x2 - x1;
    double dy = y2 - y1;
    double dz = z2 - z1;
    // 비율로 범위를 맞춘다.
    double left = 0.0;
    double right = 1.0;

    double m = 0;
    while(true) {
        // 오차 범위 10^(-9)
        if(abs(right - left) < 1e-9) {
            m = (left + right) / 2;
            break;
        }
        // 비율
        double m1 = left + (right - left) / 3;
        double m2 = right - (right - left) / 3;

        double m1x = x1 + m1 * dx;
        double m1y = y1 + m1 * dy;
        double m1z = z1 + m1 * dz;
        double m2x = x1 + m2 * dx;
        double m2y = y1 + m2 * dy;
        double m2z = z1 + m2 * dz;

        double d1 = dist(m1x, m1y, m1z, x3, y3, z3);
        double d2 = dist(m2x, m2y, m2z, x3, y3, z3);

        if(d1 > d2) {
            left = m1;
        }
        else {
            right = m2;
        }
    }

    double x0 = x1 + m * dx;
    double y0 = y1 + m * dy;
    double z0 = z1 + m * dz;
    double ans = dist(x0, y0, z0, x3, y3, z3);

    // fixed: 소수점 고정
    // setprecision: 10자리까지 표현
    cout << fixed << setprecision(10) << ans << '\n';
    return 0;

}