이진 검색
정렬된 배열에서 원하는 요소를 빠르게 찾는 알고리즘
일반적으로 시간 복잡도는 O(log n)입니다.
방법
- 배열이 정렬되었는지 확인 (정렬되지 않은 경우 이진 검색을 사용할 수 없음)
- 검색하려는 배열의 중앙값 찾기
- 중앙값이 찾고 있는 값과 같은지 확인하십시오.
- 중앙값이 검색된 값과 같으면 검색을 종료하고 인덱스 값을 반환합니다.
- 중앙값이 찾고 있는 값보다 크면 배열의 왼쪽 절반을 새 배열로 간주하여 이진 검색을 수행합니다.
- 이때 왼쪽 배열의 마지막 인덱스는 중간 인덱스 – 1
- 중앙값이 찾고 있는 값보다 작으면 배열의 오른쪽 절반을 새 배열로 간주하고 이진 검색을 수행합니다.
- 이때 오른쪽 배열의 첫 번째 인덱스는 중간 인덱스 + 1
- 찾고 있는 값이 배열에서 발견되지 않으면 검색을 취소하고 -1과 같은 특수 값 또는 오류 메시지를 반환합니다.
화신
#include <iostream>
#include <algorithm>
using namespace std;
int arr() = { 3, 99, 21, 33, 4, 1, 5, 55, 7, 10 };
void bs(int target) {
// arr가 정렬이 안 되어 있으면 꼭 정렬시켜야 함
sort(arr, arr + 10); // 오름차순 정렬
int left = 0; // 시작 index
int right = 9; // 끝 index
int flag = 0; // 찾았다 안 찾았다 표시
while (left <= right) {
int mid = (left + right) / 2; // mid를 예측
if (arr(mid) == target) {
flag = 1; // 답을 찾았으면 flag가 1로 표시됨
break;
}
else if (target < arr(mid)) { // target이 array의 mid 값보다 작다면
right = mid - 1; // target은 왼쪽에 있으므로, 오른쪽을 mid-1으로 이동
}
else if (target > arr(mid)) { // target이 array의 mid 값보다 크다면
left = mid + 1; // target은 오른쪽에 있으므로, 왼쪽을 mid+1로 이동
}
}
cout << flag; // 1: target을 찾았다, 0: target이 없다
}
int main() {
int target;
cin >> target;
bs(target);
}
효과적으로 사용하는 경우
- 배열에서 여러 번 찾을 때
- N개의 배열에서 주어진 값을 Q번 찾아야 합니다.
- 일반적으로: O(N) * Q
- 두 부분으로 구성된 검색: O(NlogN)(처음) + O(logN)*Q
- Q = N이면
- 일반적으로: O(N^2)
- 이분 검색: O(NlogN)
- N개의 배열에서 주어진 값을 Q번 찾아야 합니다.
파라메트릭 검색
최적화 문제해결에 사용되는 알고리즘(최적화 문제)
이진 검색(Binary Search) 최적의 값 찾기
*최적화 문제
- 여러 조건에서 **목적 함수**를 최대화하거나 최소화하는 값을 찾는 문제
- 문제에 따라 함수는 여러 형태를 취할 수 있지만 일반적으로 **단조적**이어야 합니다. 최적에 가깝다5월
예) 이진 검색 대 매개변수 검색
- 이진 검색 예: 정렬된 배열에서 특정 값 찾기
- 목적 함수: 주어진 배열에서 특정 값을 찾는 함수
- 조건: 배열을 정렬해야 합니다.
- 이진 검색을 사용하여 배열을 반으로 나누고 검색 범위를 점차 좁혀 특정 값을 찾습니다.
- 파라메트릭 검색 예 : 정렬되지 않은 배열에서 중앙값 찾기
- 목적 함수: 주어진 배열~에 기능적 입력보다 작은 값의 수함수 반환
- 조건: 배열이 정렬되지 않음
- 매개변수 검색을 사용하여 중앙값 찾기
- 매개변수 검색을 적용하려면 이 기능입니다. 단조 함수해야한다
파라메트릭 검색을 위한 문제 해결 방법
N개의 구슬이 있습니다.
N개의 구슬은 길이가 일정하지 않아야 합니다.
구슬은 길이에 따라 점수가 매겨집니다. (너비 무시)
그래서 N마블을 최대한 길게 만들고 일정한 K사이즈를 가지고 고객에게 판매하려고 합니다.
예를 들어, N = 3이고 K = 4이고 길이가 30, 40, 50인 구슬이 있으면
가장 긴 일정한 구슬 K의 길이는 25이고, 길이 5인 구슬은 30으로 자르고 길이 15인 구슬은 40으로 자른다. (대리석은 부품을 부착하여 사용할 수 없습니다. 금이 갈 경우 제품의 가치가 떨어지기 때문입니다.)
또 다른 예로, N=2이고 K=2인 경우 길이가 100개이고 길이가 22인 구슬이 있다면 K개의 가장 긴 일정한 크기의 구슬은 50개입니다. 이 경우 길이가 22인 구슬은 사용되지 않습니다.
K 이상의 N개의 구슬을 일정하게 만들면 구슬이 가질 수 있는 최대 길이를 출력하십시오.
기입
첫 번째 줄에는 고객이 원하는 구슬 수 N과 구슬 분할 수 K가 공백으로 구분되어 제공됩니다.
(1<=N<=10,000, 1<=K<=1,000,000, N<=K)
각 구슬의 길이는 두 번째 줄부터 N 줄까지 입력됩니다.
구슬의 길이는 정수 범위로 입력됩니다.
누르다
첫 번째 줄에 N개의 구슬이 K개의 부분으로 나눌 수 있는 최대 길이를 출력하세요.
설계
- 문제 조건에 따라 낮음(왼쪽) 및 높음(오른쪽) 결정
- 마지막 수단 답변너무 낮고 높음이 답입니다 단위동일
- 대답은 “최대 길이” → 낮음과 높음은 길이 관련 값입니다.
- low는 1(최소 길이), high는 주어진 마블 길이 중 가장 긴 것으로 정의할 수 있습니다.
- 목적 함수 정의
- 이 문제의 목적 함수는 다음과 같습니다. 중간 값가지다 계산~을 통해 참/거짓 반환해야한다.
- 목적 함수 항상 증가또는 항상 체중 감량(단조 함수).
- 위의 조건을 고려하여 목적함수 정의
- 대리석 길이 (센터), 적절한 길이의 대리석 틀림없이(K와 비교하기 위해) 만들 수 있는지 계산
- K 값과 비교하여 true(생성 가능)/false(생성 불가)를 반환합니다.
화신
#include <iostream>
#include <algorithm>
using namespace std;
int N, K; // N : 주어지는 대리석 개수, K : 고객이 요청하는 대리석의 분할 개수
int arr(10000); // 갖고 있는 대리석의 길이를 저장
bool condition(int cut_len) {
long long sum_ = 0; // cut_len으로 각각을 잘랐을 시 얻을 수 있는 대리석 개수
for (int i = 0; i < N; i++) {
sum_ += arr(i) / cut_len; // 원하는 크기로 대리석 잘라보기
}
if (sum_ >= K) // K개 이상을 만들 수 있다
return true;
return false; // K개 이상을 만들 수 없다
}
void psearch(int high) {
int left = 1;
int right = high;
int ans = 0;
while (left <= right) {
// 가능성 -> 정답이라고 가정한 값
int mid = (left + right) / 2;
// 이 가능성이 정답이 될수 있는 지
if (condition(mid) == true) {
// 정답이 될 가능성이 있는 값을 찾았을 때
// 상한선을 높여 볼까? -> left 값 변경
ans = mid;
left = mid + 1;
}
else {
// 이 mid 값은 정답이 될 수 없다
// 상한선의 가장 큰 값의 범위를 낮춘다 -> right 값 변경
right = mid - 1;
}
}
cout << ans; // K개 잘랐을 때, 얻을 수 있는 최대 길이
}
int main() {
cin >> N >> K;
int max_ = 0; // 내가 가진 대리석의 길이 중 가장 긴 것
for (int i = 0; i < N; i++) {
cin >> arr(i);
if (max_ < arr(i))
max_ = arr(i);
}
psearch(max_);
}
두손
배열이나 목록과 같은 순차적 데이터 구조에서 두 개의 포인터로 문제를 해결하는 방법
일반적으로 O(n)의 시간 복잡도를 가집니다.
#include <iostream>
using namespace std;
int main() {
int arr() = { 1,2,3,1,2,3,5,6,7,8 };
int target = 6; // 찾고자 하는 배열의 합
int left = 0; // slow pointer
int right = 0; // fast pointer
int sum = 0; // pointer들이 가리키는 배열의 합
int cnt = 0; // target과 같은 합이 나오면 check
while (left <= 10 && right <= 10) {
if (sum == target) {
// target 값과 같다 -> 왼쪽을 줄여서 이동 (right를 움직이면 배열 idx 초과 오류 가능성)
cnt++;
sum -= arr(left++);
}
else if (sum < target) {
// sum이 목표보다 작다 -> 오른쪽으로 늘려서 이동
sum += arr(right++);
}
else if (sum > target) {
// sum이 목표보다 크다 -> 왼쪽을 줄여서 이동
sum -= arr(left++);
}
}
cout << cnt; // 5
}
슬라이딩 윈도우
주어진 간격의 합이 내가 원하는 답인지 확인하려면
#include <iostream>
using namespace std;
int main() {
int arr() = { 1,2,3,1,2,3,5,6,7,8 };
int size_ = 10; // arr 크기
int N = 3;
// 1. 초기 포인터 setting
int left = 0;
int right = N-1;
// 2. 초기 공통 구간 setting
int sum = 0;
for (int i = left; i < right; i++) {
sum += arr(i);
}
// 3. sliding window
int ans = 21e8;
while (right < size_) {
// a. 구간 완성
sum += arr(right);
// b. 수행
if (sum < ans)
ans = sum;
// c. 다음 공통 구간 만들기
sum -= arr(left);
// d. left와 right 포인터 이동
left++;
right++;
}
}
#2 문제 해결 적용
// 위와 비교해 어떤 구현방법이 직관적이고 편한 지는 본인이 선택해서 구현
// 구간 합이 가장 큰 부분 찾기 문제
#include <iostream>
using namespace std;
int main() {
int arr() = { 1,2,3,1,2,3,5,6,7,8 };
int size_ = 10;
int N = 3;
int left = 0;
int right = N - 1;
int sum_ = 0;
for (int i = left; i <= right; i++) {
sum_ += arr(i); // 1. 구간 전체를 더해서 시작
}
int max_ = -21e8;
int max_l = left, max_r = right;
while (right < size_) {
if (max_ < sum_) {
max_l = left;
max_r = right;
max_ = sum_;
}
cout << left << " " << right << " " << sum_ << endl;
right++;
sum_ += arr(right); // right를 옮기고 값을 더함
sum_ -= arr(left); // 값을 빼준 후 left를 옮김
left++;
}
}