항해99 TIL-11

풀이 문제: 백준 16401 (과자 나눠주기)

알고리즘: 이진 탐색

후기:

1. 이진 탐색은 처음이었다

이진 탐색 (Binary Search)

• 시간 복잡도: $O(\log(n))$

  • 탐색 범위가 너무 크면, 이진 탐색을 먼저 떠올리자 1. low, high 지정 2. mid = (low + high)//2 지정 3. 문제 조건 만족 확인 후, 경우에 따라 아래와 같이 범위 조정

  • Case1: 조건 만족 O, But 범위 하한을 높여야 하는 경우
    • result = mid로 저장 후
    • low = mid+1로 업데이트
  • Case2: 조건 만족 X, 범위 상한을 낮춰야 하는 경우
    • high = mid-1로 업데이트