이분탐색
정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신, 탐색 범위를 절반으로 줄여가며 찾는 탐색 방식.
이분탐색의 주의 사항
- 주어진 배열은 반드시 오름차순으로 정렬되어 있어야 한다.
- 무한 루프에 빠지지 않게 mid 값을 정해야 한다.
정렬된 배열에서 중복된 데이터를 제거할 땐 unique와 erase를 이용한다.
2개의 값들을 묶거나 어느 한쪽의 값을 이분탐색으로 찾아서 시간복잡도를 낮추는 아이디어는 이분탐색 관련 응용문제에서 핵심적으로 많이 나온다.
Parametric Search (매개 변수 탐색)
조건을 만족하는 최소/최댓값을 구하는 문제(최적화 문제)를 결정 문제로 변환해 이분탐색을 수행하는 방법
최적화 문제를 결정 문제로 바꿀 수 있는지 생각하고 그 결정 문제로 얻어낸 함수가 감소 혹은 증가함수인지를 따져봐야 한다.
문제에서 최소/최대 얘기가 있고 범위가 무지막지하게 크거나 시간 복잡도에서 값 하나를 로그로 떨어트리면 될 것 같을때 Parametric Search 풀이를 고민할 수 있다.
연습 문제
1920: 수 찾기
더보기
#include <iostream>
#include <algorithm>
int arr[100001];
int n, m;
int bsearch(int &t)
{
int st = 0;
int en = n - 1;
while (st <= en) {
int mid = (st + en) / 2;
if (arr[mid] > t) en = mid - 1;
else if (arr[mid] < t) st = mid + 1;
else return 1;
}
return 0;
}
using namespace std;
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> arr[i];
}
sort(arr, arr + n);
cin >> m;
while (m--)
{
int t;
cin >> t;
cout << bsearch(t) << '\n';
}
return 0;
}
10816: 숫자 카드 2
더보기
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
vector<int> cards;
int n, m, data;
cin >> n;
while (n--)
{
cin >> data;
cards.push_back(data);
}
sort(cards.begin(), cards.end());
cin >> m;
while (m--)
{
cin >> data;
cout << upper_bound(cards.begin(), cards.end(), data) - lower_bound(cards.begin(), cards.end(), data) << " ";
}
return 0;
}
lower_bound와 upper_bound의 결과를 pair로 반환해주는 equal_range라는 함수가 있다.
이 경우 second - first로 더 간단하게 표현할 수 있다.
18870: 좌표 압축
더보기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int arr[1000001];
vector<int> ans;
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> arr[i];
ans.push_back(arr[i]);
}
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
for (int i = 0; i < n; ++i)
{
cout << lower_bound(ans.begin(), ans.end(), arr[i]) - ans.begin() << ' ';
}
return 0;
}
2295: 세 수의 합
더보기
추후 풀어볼 예정
1654: 랜선 자르기
더보기
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
int k, n;
int arr[1000001];
// 핵심 메소드
bool cut(int v)
{
ll ans = 0;
for (int i = 0; i < k; ++i)
ans += arr[i] / v;
return ans >= n;
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> k >> n;
for (int i = 0; i < k; ++i)
cin >> arr[i];
sort(arr, arr + k);
ll st = 0;
ll en = (1<<31)-1;
while (st < en)
{
ll mid = (st + en + 1) / 2;
if (cut(mid)) st = mid;
else en = mid - 1;
}
cout << st;
return 0;
}
Parametric Search의 대표 문제.
최적화 문제 : N개를 만들 수 있는 랜선의 최대 길이
->결정 문제 : 랜선의 길이가 X일 떄 랜선이 N개 이상인가 아닌가?
기본 문제
10815: 숫자 카드
더보기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
int v1[500001];
int v2[500002];
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 0; i < n; ++i)
cin >> v1[i];
cin >> m;
for (int i = 0; i < m; ++i)
cin >> v2[i];
sort(v1, v1 + n);
for (int i = 0; i < m; ++i)
cout << binary_search(v1, v1 + n, v2[i]) << ' ';
return 0;
}
1822: 차집합
더보기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int n, m;
ll arr1[500001];
ll arr2[500001];
vector<ll> answer;
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; ++i)
cin >> arr1[i];
for (int i = 0; i < m; ++i)
cin >> arr2[i];
sort(arr1, arr1 + n);
sort(arr2, arr2 + m);
for (int i = 0; i < n; ++i)
if (!binary_search(arr2, arr2 + m, arr1[i])) answer.push_back(arr1[i]);
cout << answer.size() << '\n';
for (auto& elem : answer)
cout << elem << ' ';
return 0;
}
16401: 과자 나눠주기
더보기
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
int n, m;
int arr[1000001];
// 이 함수를 잘 기억해야 한다
bool cut(int v)
{
if (v == 0) return true;
ll ans = 0;
for (int i = 0; i < m; ++i)
ans += arr[i] / v;
return ans >= n;
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; ++i)
cin >> arr[i];
sort(arr, arr + m);
int st = 0;
int en = 1000000000;
while (st < en)
{
int mid = (st + en + 1) / 2;
if (cut(mid)) st = mid;
else en = mid - 1;
}
cout << st;
return 0;
}
Parametric Search
최적해가 없는 경우에 0을 출력해야 하므로 cut 메소드에서 0일때도 true를 반환하도록 한다.
'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글
| [0x15] 해시 (0) | 2022.08.06 |
|---|---|
| [0x14] 투 포인터 (0) | 2022.08.05 |
| [0x12] 수학 (0) | 2022.08.05 |
| [0x11] 그리디 (0) | 2022.08.04 |
| [0x10] 다이나믹 프로그래밍 (0) | 2022.08.03 |