이진 탐색 / 매개 변수 탐색

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;
  }