[이진 탐색 알고리즘] 문제풀이 전략

---

이진 탐색이란 찾으려는 데이터를 시작점과 끝점 사이의 중간점과 비교해서 원하는 데이터를 찾는 알고리즘이다

 

이 탐색 방법은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다

 

한 번 확인할 때마다 데이터가 반으로 줄어든다는 점에서 연산 횟수는 log(2)N에 비례하고 이는 O(logN)이다 

 

이진 탐색은 재귀를 사용하는 방법과 반복문을 사용하는 방법이 있다

 

다음은 두 방법을 구현한 것이다

---

#include<bits/stdc++.h>
using namespace std;
int recur_binary_search(int st, int en, int val);
int iter_binary_search(int st, int en, int val);
int arr[10] = {0,11,15,25,41,56,99,101,324,400};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << recur_binary_search(0, 9, 99);
    cout << iter_binary_search(0, 9, 99);
    return 0;
}

int recur_binary_search(int st, int en, int val) {
    if (st > en) return -1;
    int mid = (st + en) / 2;
    if (arr[mid] == val) return mid;
    else if (arr[mid] < val)  recur_binary_search(mid+1, en, val);
    else recur_binary_search(st,mid-1, val);
}

int iter_binary_search(int st, int en, int val) {
    int mid = (st + en) / 2;
    int start = st;
    int end = en;
    while (true) {
        if (start > end) return -1;
        mid = (start + end) / 2;
        if (arr[mid] == val) return mid;
        else if (arr[mid] < val) {
            start = mid + 1;
            continue;
        }
        else {
            end = mid - 1;
            continue;
        }
    }
}

---

트리 자료구조 중 가장 간단한 형태가 이진 탐색 트리 (Binary Search Tree)이다

 

이진 탐색 트리란 이진 탐색이 동작하도록 고안된, 효율적인 탐색이 가능한 자료구조이다

 

이진 탐색 트리는 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 라는 특징을 갖는다

 

다음 예제를 통해 이진 탐색을 연습해 보자

---

문제 : 가게는 N종류의 부품을 가지고 있다. M종류의 부품을 사려고 할 때 부품이 존재하는지 확인하라

 

입력 조건

• 첫째 줄에 정수 N이 주어진다 (1<=N<=1000000)
• 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다 이는 1보다 크고 1000000이하이다
• 셋째 줄에는 정수 M이 주어진다 (1<=M<=100000)
• 넷째 줄에는 공백으로 구분하여 M개의 정수가 주언진다, 이는 1보다 크도 1000000이하이다

출력 조건

• 첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes를, 없으면 no를 출력한다

입력 예시

5
8 3 7 9 2
3
5 7 9

출력 예시

no yes yes

#include<bits/stdc++.h>
using namespace std;
int n, m;
int narr[1000000];
int marr[1000000];
int binary_search(int st, int en, int val);
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0;i < n;i++)cin >> narr[i];
    sort(narr, narr + n);
    cin >> m;
    for (int i = 0;i < m;i++) {
        cin >> marr[i];
        if (binary_search(0, n, marr[i]) < 0) cout << "no ";
        else cout << "yes ";
    }
    return 0;
}

int binary_search(int st, int en, int val) {
    if (st > en) return -1;
    int mid = (st + en) / 2;
    if (narr[mid] == val) return mid;
    else if (narr[mid] > mid) binary_search(mid + 1, en, val);
    else binary_search(st, en - 1, val);
}

---

문제 풀이 방식에 이진 탐색을 구현하는 방식 이외의 다른 방식이 존재한다

 

STL에 정의된 컨테이너들 중 연관 컨테이너들은 기본적으로 균형 이진 트리 구조인데 이것을 이용하는 것이다

 

STL set 컨테이너의 멤버 함수 find()는 이진 탐색 방식을 사용하므로 다음과 같은 풀이도 가능하다

---

#include<bits/stdc++.h>
#include<set>
using namespace std;
int n, m;
set<int> ns;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0;i < n;i++) {
        int tmp;
        cin >> tmp;
        ns.insert(tmp);
    }
    cin >> m;
    for (int i = 0;i < m;i++) {
        int tmp;
        cin >> tmp;
        if (ns.count(tmp)) cout << "yes ";
        else cout << "no ";
    }
    return 0;
}

---

문제 : 떡집의 절단기는 그 높이가 일정하지 않다. 요청한 떡의 총 길이가 M일 때 절단기 높이의 최댓값은?

• 손님은 잘린 떡의 합을 가져가고 그 값 M을 요청한다
• 떡은 총 N개 존재한다

입력 조건

• 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다 (1<=N<=1000000, 2<=M<=2000000000)
• 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이다 (0<=M<=1000000000)

출력 조건

• 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다

입력 예시

4 6
19 15 10 17

출력 예시

15

---

주어진 범위 내에서 조건을 만족하는 가장 큰 값을 찾는 문제로 이는 대표적인 파라메트릭 서치 문제이다

 

코딩 테스트에서 대부분의 파라메트릭 서치 문제는 이진 탐색으로 해결할 수 있다

 

가장 먼저 해야 할 것은 계속적으로 범위를 좁혀 갈 변수를 설정하는 것이다

 

이 문제에서는 절단기의 길이가 이에 해당한다

 

그 다음으로는 값을 비교할 변수를 설정해야 한다

 

이 문제에서는 잘린 떡 길이의 합이 이에 해당한다

 

이를 종합하여 문제를 해결하면 다음과 같다

---

#include<bits/stdc++.h>
#include<set>
using namespace std;
int n, m; 
int ans;
int cutter;
int maxval;
int maxindex;
int arr[1000001];
int binary_search(int st, int en, int val);
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0;i < n;i++) {
        cin >> arr[i];
        if (maxval < arr[i]) {
            maxval = arr[i];
            maxindex = i;
        }
    }
    cout<< binary_search(0,maxval,m);
    return 0;
}
int binary_search(int st, int en, int val) {
    if (st > en) return en;
    int mid = (st + en) / 2;
    int ans = 0;
    for (int i = 0;i <= n;i++) {
        if (arr[i] > mid) ans += (arr[i] - mid);
    }
    if (ans == val) return mid;
    else if (ans > val) binary_search(mid+1, en, val);
    else binary_search(st, mid-1, val);
}

---