Binary Search & Parametric Search

코딩 중급

Binary Search & Parametric Search

태장고 21302 2021. 12. 17. 18:47

이분 탐색은 원하는 값을 찾을 때, 완전탐색보다 더 빠르게 찾을 수 있는 알고리즘입니다.

일반적인 탐색보다는 나중에 매개 변수 탐색에 더 많이 사용되지만, 기본적인 탐색도 알아두면 좋습니다.

먼저 정렬을 해 주는 것이 중요합니다. 그 이유는 중앙값을 기준으로 값을 찾아 나갈 것인데, 정확한 기준이 없다면 중앙값을 어떻게 바꿔 나가야 하는지를 모르기 때문입니다.

그 다음! 양끝 지점을 잡고, 그 중앙값에 따라 판별을 합니다. 이 판별은 두가지 경우로 나뉘게 됩니다.

1. 찾는 값이 중앙값보다 큰 경우 - 작은 지점을 중앙값으로 갱신합니다.

2. 찾는 값이 중앙값보다 작은 경우 - 큰 지점을 중앙값으로 갱신합니다.

이렇게 판별하는 이유는 중앙에 있는 값보다 작다면? 굳이 더 큰 수들을 볼 필요가 없기 때문입니다. 큰 경우에도 마찬가지로 중앙값보다 작은 수는 볼 필요가 없게 되기 때문입니다.

이런 과정을 반복하면서 답을 찾으면 됩니다.

예를 들어,

4 1 5 2 3 중에서 2를 찾으려 한다면, 우선 정렬을 한 다음에 탐색을 진행합니다.

정렬의 이유를 설명하자면, 중앙값이 5인 상태에서는 원하는 값이 더 작은지, 큰지를 판별할 수 없기 때문입니다.

hi = 5, lo = 1로 설정하고 탐색을 진행합니다.

정렬을 한 다음에 중앙에는 3이 존재하게 됩니다. 3보다 큰 수에는 절대로 2가 존재할 수 없으므로 hi를 중앙인덱스로 교체시킵니다. 그럼 현재 lo = 1, hi = 3이 되게 됩니다.

그런 다음 한번 더 탐색을 진행합니다. 이 때 중앙에는 2가 존재하게 되는데 우리가 찾던 수이므로 탐색을 멈춥니다.

구현은 다음과 같이 할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

/*
ID : litterhy1
LANG : C++
*/
#include <iostream>
#include <algorithm>
using namespace std;
 
int a[100010];
 
int main()
{
    int n; cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
 
    sort(a+1, a+n+1);
 
    int m; cin >> m;
    while(m--) {
        int t; cin >> t;
 
        int lo = 1, hi = n, flag = 0;
        while(lo <= hi) {
            int mid = (lo+hi)/2;
            if(a[mid] == t) {
                flag = 1;
                break;
            }
 
            if(a[mid] < t) {
                lo = mid+1;
            } else {
                hi = mid-1;
            }
        }
 
        cout << flag << "\n";
    }
 
    return 0;
}
Colored by Color Scripter

cs

이제 이걸 이용해서 매개 변수 탐색을 해 볼 건데,

처음하면 상당히 어렵습니다. 그래도! 몇번 짜다보면 이해할 수 있으니 포기하진 마세요~!

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그

www.acmicpc.net

-- 매개 변수 탐색(parametric search)으로 풀 수 있는 예시용 문제입니다.

매개 변수 탐색은 원하는 값이 나올 때까지 수를 몇개 넣어보고 조건에 맞는 것을 출력하는 방법입니다. 구현 방법은 이분탐색과 크게 다르지 않습니다.

위 문제에서 최적화된 값을 찾기 위해,

제일 큰 값과 제일 작은 값을 설정하고 중앙을 이분탐색을 하면서 최적해를 찾아갑니다.

lo = 0, hi = 10^18 ( 범위 계산하기 귀찮으니 그냥 엄청 큰 값을 때려 넣음. )

그런 다음에 중앙값으로 배열의 모든 값을 나누면서 만들어진 랜선의 수가 m일 때 lo를 출력하면 됩니다.

그럼 조건을 만족하는 최소 해를 구할 수 있습니다.

구현은 다음과 같이 할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

/*
ID = litterhy1
LANG = C++
*/
#include <iostream>
#include <algorithm>
using namespace std;
 
typedef long long int INT;
 
int a[1000010];
 
int main()
{
    int n, m; cin >> n >> m;
    for(int i=0; i<n; i++) cin >> a[i];
 
    sort(a, a+n);
 
    INT lo = 0, hi = 1e18;
    while(lo+1 < hi) {
        INT mid = (lo+hi)/2;
 
        INT sum = 0;
        for(int i=0; i<n; i++)
            sum += a[i]/mid;
 
        if(sum >= m) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
 
    cout << lo << "\n";
 
    return 0;
}
Colored by Color Scripter

cs

티스토리

Binary Search & Parametric Search

Binary Search & Parametric Search

추천 문제