Algorithm/개념 구현
이진 탐색 / 매개 변수 탐색
도전하는 린치핀
2024. 8. 12. 23:22
1. 선형 탐색
- 보통 생각하는 탐색(완전 탐색)은 선형 탐색으로 수행된다.
- 예를 들어 어떤 수(10)가 배열에 존재 하는지 탐색하는 상황을 말한다.
- 선형 탐색은 일렬된 자료를 단방향으로 모두 확인하며 탐색을 진행하기 때문에 시간복잡도는 O(n)이 나온다.
- 만약, 배열이 정렬이 되어 있다면 더 빠르게 탐색할 수 있다.
- 정렬이 기본적인 전제 조건으로 배열이 있다면?
2. 이진 탐색
- 정렬된 상태의 배열에서의 탐색 (10을 찾기)
- 이진 탐색 : 탐색 범위를 절반씩 좁혀가며 탐색을 진행
- 어떤 수를 찾을 때, 범위를 절반씩 줄여나가며 정답 후보를 갱신하므로 시간복잡도는 O(logN)이 나온다.
ex) [1, 6, 8, 10, 15, 16, 20, 22, 23, 24] - 배열 내 10을 찾는 과정
- start 1 ~ end 24 → mid 15 : 10은 15보다 작으므로 15 뒤에 있는 값은 절대로 정답이 아님
- start 1 ~ end 10 → mid 6 : 10은 6보다 크기 때문에 6 앞의 값은 절대로 정답이 아님
- start 8 ~ end 10 → mid 8 : 10은 8보다 크기 때문에 8 앞의 값은 절대로 정답이 아님
- start 10 ~ end 10 → mid 10 : 10 탐색 완료!
// 구간의 양쪽 설정
int s = 0;
int e = n - 1;
// 구간 내에서 이진 탐색
while(s <= e) {
mid = (s + e) / 2;
// 탐색 완료 출력 후 반복 중단
if(arr[mid] == target) {
cout << mid;
break;
}
// 중간값이 타겟보다 작으면 왼쪽 값 제외
else if(arr[mid] < target) {
s = mid + 1;
}
// 중간값이 타켓보다 크면 오른쪽 값 제외
else if(arr[mid] > target) {
e = mid - 1;
}
}
- 만약 9의 값을 탐색한다면? → s가 e보다 크기 때문에 target 찾지 못하고 반복문 종료
3. 이진 탐색 응용 (lower bound, upper bound)
- 보통의 이진 탐색은 위의 이진 탐색처럼 간단하게 탐색을 하고 끝내는 경우가 거의 없다.
- 대부분의 코테에서 나오는 이진탐색 카테고리의 문제는 이후에 나오는 매개변수 탐색에 해당하는데 매개변수 탐색을 알기 위해 “lower bound, uppder bound”에 대해서 알아야 한다.
- 이진 탐색 응용 : 이진 탐색의 다른 형태로 “xxxxxooooo 형태에서 가장 왼쪽의 o을 찾는다”
- 이것 또한, 기본 전제는 정렬이 되어있는 배열에서의 탐색이다.
- 예제 1 ) XXXXXOOOO 로 되어 있는 배열에서 가장 왼쪽에 있는 O를 찾는다면?
- 처음 mid 는 5번째 X이다.
- 그러면 5번째 mid가 X이므로 5번 전에 있는 것들은 모두 X라는 것을 확인하고 start를 6번으로 둔다.
- 그러면 mid는 7번째 O가 나오므로 7번 뒤에는 모두 O인것을 확인 할 수 있다(7번은 정답 후보)
- 7번의 O보다 작은 O가 있을 수 있는지 확인하기 위해 end를 6번으로 두고 mid가 6번일때 확인
- 6번은 O이므로 7번보다 작은 6번의 O가 정답이 된다.
- 예제 2 ) XXXOOOZZZ 로 되어 있는 배열에서 가장 오른쪽에 있는 O를 찾는다면?
- 처음 mid 는 5번째 O이다.
- 그러면 5번째 mid가 O이므로 5번은 정답 후보로 등록이 된다.
- 하지만 우리는 가장 오른쪽에 있는 O를 찾아야 하기 때문에 5번 전에는 신경을 끈다.
- start가 5번이 되어 7번이 mid가 되는데 7번은 Z이므로 7번 이후는 모두 지운다.
- start와 end, mid 모두 6번이 되므로 6번은 O이므로 정답 후보에 있던 5번의 O보다 오른쪽에 있으니깐 정답은 6번의 O가 된다.
정렬된 배열에서 특정 수 x보다 크거나 같은 값 중 제일 왼쪽 인덱스를 lower bound라고 한다.
비슷한 개념으로 x보다 큰 값 중 제일 왼쪽 인덱스를 upper bound라고 한다.
- 예를 들어 [5, 6 10, 19, 22, 30, 30, 33, 40] 배열이 있다고 생각해보자
- lower bound 30은 [5, 6 10, 19, 22, 30, 30, 33, 40] 이고
- uppder bound 30은 [5, 6 10, 19, 22, 30, 30, 33, 40] 이다.
4. lower bound 구현
// Lower bound 구현
// 크기가 n인 오른차순으로 정렬된 배열에서 특정 수 x 보다 크거나 같은 값 중
// 제일 왼쪽의 인덱스(lower bound) 출력
// 없으면 -1 출력
// --------------------------
// 1. 탐색 범위 닫힌 구간
// 2. 정답 범위에서 lower bound
// 3. mid가 x보다 크거나 같으면 mid를 정답 후보 저장 후, mid 이상은 제거
// 4. mid가 X보다 작으면 왼쪽값 제거
cin >> x;
int s = 0;
int e = n - 1;
int answer = -1;
while(s<= e) {
mid = (s + e) / 2;
if(arr[mid] >= x) {
answer = mid;
e = mid -1;
}
else {
s = mid + 1;
}
}
5. 매개변수 탐색
- N개의 수 중 몇개의 연속된 수를 더해야 그 값이 S가 될까?
- 만약 정답의 형태가(xxxxxooooo) 라면 x와 o의 경계를 찾으면 된다.
- → 완전 탐색 풀이 : 1개부터 N개까지 수들을 모두 더해본 다음 S이상이 되는 경우를 찾는다.
- “어떤 값이 가장 최소인 값”을 찾는 최적화 문제를 → “이 값이 정답이 될 수 있는가?”를 찾는 형태의 결정 문제로 변환하는 알고리즘
- 즉 정답이 되는 경계를 구하는 방식이라고 생각할 수 있다.
예제 ) https://www.acmicpc.net/problem/2805
설정할 수 있는 절단기 높이의 최댓값을 구하는 문제
입력 - N(나무의 수, 1≤ N ≤ 1,000,000) M(가져가려는 나무 길이, 1≤ M ≤ 2,000,000,000)
높이는 1,000,000,000보다 작거나 같은 자연수
- 문제 이해
- 입력20 15 10 17
- 4 7
- 문제 이해h=1 → 19 + 14 + 10 + 16 = 58 (o)h=15 → 5 + 0 + 0 + 2 = 7 (o)
- h=16 → 4 + 0 + 0 + 1 = 5 (x)
- …
- h=0 → 20 + 15 + 10 + 17 = 62 (o)
#include <iostream> using namespace std; int n, m; int arr[10000100]; bool check(int x) { long long sum = 0; for(int i=0; i<n; i++) { if(arr[i] > x) sum += arr[i] - x; } return sum >= m; } int main() { int s, e, mid, answer; cin >> n >> m; for(int i=0; i<n; i++) cin >> arr[i]; answer = 0; s= 0, e = 1000000000; while(s<=e) { mid = (s+e) / 2; if(check(mid)) { answer = mid; s = mid + 1; } else e = mid -1; } cout << answer << endl; }