[알고리즘] 이분 탐색 (Binary Search)

처음에는 문제를 생각해본다,,

(1) 브루트포스로 풀 수 잇을까? (2) 안되면 어떻게 풀지 ,,,

• 이분탐색은 O(N) → O(log2N)으로 줄일 수 있는 분할정복 알고리즘이다
• 이분탐색 전에는 배열이 모두 정렬되어 있어야 한다

예를 들어서 소주병 뚜껑에 어떤 숫자가 적혀있는 지 가장 빠르게 구하는 방법은 무엇일까?

뚜껑 숫자의 범위가 1~50일 경우에,

(1) 1부터 50까지 다 질러본다 -> 브루트포스 방법이고, 총 O(N)의 시간복잡도를 가질 것이다.

(2) 가운데(25)부터 시작해본다, 만약 UP일 경우 (26~50) 사이로 다시 탐색을 해본다.

-> 결국 N개의 숫자를 모두 탐색하는 것이 아니라, 반씩 나누면서 범위를 좁히며 탐색하게 되고 결국 시간복잡도는 O(logN)이 된다.

 

• 구현방법 1 while문 사용하기(C++)

int A[100];

int find(int left, int right, int key){
        int start = left;
        int end = right;
        while(start < end){
                int middle = (start + end) / 2;
                if(A[middle] == key) return middle;
                if(A[middle] < key) start = middle+1;
                else end = middle;
        }
        return -1;
}

sort(A.begin(), A.end());
find(0, 100, 10);

 

• 구현방법 2 재귀함수로 풀기(Python)

  def binary_search(mylist, left, right, key):
  	if left > right:
  		return -1
  
    middle = (left+right)//2
    if key == mylist[middle]:
      return middle
  
    if key < mylist[middle]:
      return binary_search(mylist, left, middle-1, key)
    else:
      return binary_search(mylist, middle+1, right, key)
  
  find = binary_search(mylist, 0, len(mylist)-1, 7)​

🦔 백준 풀어볼 문제 (중급&고급 난이도)

2805번 나무 자르기
3020번 개똥벌레 함께풀어요~~
1949번 중량제한
2480번 두 용액 → 2473번 세 용액

 

2805번 나무 자르기 문제를 같이 풀어봅시다!

• 모든 나무 높이에 대해서, 나무를 잘라보고 M길이의 나무를 얻을 수 있는 지 확인하자 → O(N*H)
• 그러나 문제를 보다시피 N과 H가 매우 큰 상태이다,, O(N*H)은 불가능!
• 만약 O(N*log2H)로 풀수 있다면 ? 쌉가능
• H를 1부터 끝까지 다 검사하지 말고,, 가능한 범위에서만 검사하자 → 이분탐색을 사용하여 log2H로 풀 수 있다
• 나무를 잘라본 다음에 원하는 높이만큼 나무를 얻을 수 있다면 더 위를 잘라보고, 그렇지 않다면 너 밑을 잘라보자.

Code(Python)

N = int(input())
M = int(input())

trees = []

for i in range(N):
  trees.append(int(input()))
  
possible = -1

left = 0
right = max(trees)
middle = max(trees) // 2

while left <= right:

  s = 0
  for tree in trees:
    if middle < tree:
      s += tree - middle

  if s >= M:
    if possible < middle:
      possible = middle
    left = middle + 1
    middle = (right + left) //2
  else:
    right = middle - 1
    middle = (right + left) //2

print(possible)