μΆμ² : https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5
μμ°¨ νμ
: 리μ€νΈ μμ μλ νΉμ ν λ°μ΄ν°λ₯Ό μ°ΎκΈ° μν΄ μμμλΆν° λ°μ΄ν°λ₯Ό νλμ© νμΈνλ λ°©λ²
μ΄μ§ νμ
: μ λ ¬λμ΄ μλ 리μ€νΈμμ νμ λ²μλ₯Ό μ λ°μ© μ’νκ°λ©° λ°μ΄ν°λ₯Ό νμνλ λ°©λ²
ππ» 리μ€νΈκ° μ λ ¬λμ΄ μμ΄μΌ ν¨
ππ» μ΄μ§ νμμ μμμ , λμ , μ€κ°μ μ μ΄μ©νμ¬ νμ λ²μλ₯Ό μ€μ
ππ» λΉ λ₯΄κ² νμ κ°λ₯νμ¬ λ‘κ·Έ μκ°λ³΅μ‘λλ₯Ό κ°μ§ μ μμ
μ΄λ―Έ μ λ ¬λ 10κ°μ λ°μ΄ν° μ€ κ°μ΄ 4μΈ μμλ₯Ό μ°Ύλ μμλ₯Ό μ΄ν΄λ³΄μ
STEP 1 : μμ μΈλ±μ€ : 0, μ€κ° μΈλ±μ€ : 4 (μμμ μ΄ν μ κ±°), λ μΈλ±μ€ : 9
β
μ€κ°μ κ³Ό λΉκ΅νμ¬ μμΌλ―λ‘ μ€κ°μ λ―Έλ§μμλ§ νμ. μ¦, μ€κ°μ μ΄μ μΈλ±μ€λ λ³Ό νμ β
β
κ°μΌλ©΄ νμ μλ£ βοΈ
β
μ€κ°μ μμΉλ₯Ό μΌμͺ½
μΌλ‘ μ΄λ
STEP 2 : μμ μΈλ±μ€ : 0, μ€κ° μΈλ±μ€ : 1 (μμμ μ΄ν μ κ±°), λ μΈλ±μ€ : 3
β
μ€κ°μ κ³Ό λΉκ΅νμ¬ ν¬λ―λ‘ μ€κ°μ μ΄κ³Όμμλ§ νμ. μ¦, μ€κ°μ μ΄ν μΈλ±μ€λ λ³Ό νμ β
β
κ°μΌλ©΄ νμ μλ£ βοΈ
β
μμμ μμΉλ₯Ό μ€λ₯Έμͺ½
μΌλ‘ μ΄λ
STEP 3 : μμ μΈλ±μ€ : 2, μ€κ° μΈλ±μ€ : 2 (μμμ μ΄ν μ κ±°), λ μΈλ±μ€ : 3
β
μμμ κ³Ό μ€κ°μ μ΄ κ°μΌλ―λ‘ νμ μλ£
β
μ°Ύκ³ μ νλ κ° 4κ° μΈλ±μ€ 2μ μμΉνλ€λ κ²μ μμλ
π€― μκ° λ³΅μ‘λ λΆμ
β
λ¨κ³λ§λ€ νμ λ²μλ₯Ό 2λ‘ λλλ κ²κ³Ό λμΌνλ―λ‘ μ°μ° νμλ logN
μ λΉλ‘
β
μλ₯Ό λ€μ΄ μ΄κΈ° λ°μ΄ν° κ°μκ° 32κ°μΌ λ, μ΄μμ μΌλ‘ 1λ¨κ³λ₯Ό κ±°μΉλ©΄ 16κ°κ°λμ λ°μ΄ν°λ§, 2λ¨κ³λ₯Ό κ±°μΉλ©΄ 8κ°κ°λμ λ°μ΄ν°λ§, 3λ¨κ³λ₯Ό κ±°μΉλ©΄ 4κ°κ°λμ λ°μ΄ν°λ§ λ¨λλ€.
β
λ€μ λ§ν΄ μ΄μ§ νμμ νμ λ²μλ₯Ό μ λ°μ© μ€μ΄λ©°, μκ° λ³΅μ‘λλ O(logN)
μ 보μ₯νλ€.
python
# μ΄μ§ νμ μμ€μ½λ ꡬν (μ¬κ· ν¨μ) def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # μ°Ύμ κ²½μ° μ€κ°μ μΈλ±μ€ λ°ν if array[mid] == target: return mid # μ€κ°μ μ κ°λ³΄λ€ μ°Ύκ³ μ νλ κ°μ΄ μμ κ²½μ° μΌμͺ½ νμΈ elif array[mid] > target: return binary_search(array, target, start, mid - 1) # μ€κ°μ μ κ°λ³΄λ€ μ°Ύκ³ μ νλ κ°μ΄ ν° κ²½μ° μ€λ₯Έμͺ½ νμΈ else: return binary_search(array, target, mid + 1, end) # n(μμμ κ°μ)κ³Ό target(μ°Ύκ³ μ νλ κ°)μ μ λ ₯ λ°κΈ° n, target = list(map(int, input().split())) # μ 체 μμ μ λ ₯ λ°κΈ° array = list(map(int, input().split())) # μ΄μ§ νμ μν κ²°κ³Ό μΆλ ₯ result = binary_search(array, target, 0, n - 1) if result == None: print("μμκ° μ‘΄μ¬νμ§ μμ΅λλ€.") else: print(result + 1)
Java
import java.util.*; public class Main { // μ΄μ§ νμ μμ€μ½λ ꡬν(μ¬κ· ν¨μ) public static int binarySearch(int[] arr, int target, int start, int end) { if (start > end) return -1; int mid = (start + end) / 2; // μ°Ύμ κ²½μ° μ€κ°μ μΈλ±μ€ λ°ν if (arr[mid] == target) return mid; // μ€κ°μ μ κ°λ³΄λ€ μ°Ύκ³ μ νλ κ°μ΄ μμ κ²½μ° μΌμͺ½ νμΈ else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1); // μ€κ°μ μ κ°λ³΄λ€ μ°Ύκ³ μ νλ κ°μ΄ ν° κ²½μ° μ€λ₯Έμͺ½ νμΈ else return binarySearch(arr, target, mid + 1, end); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); // μμμ κ°μ(n)μ μ°Ύκ³ μ νλ κ°(target)μ μ λ ₯λ°κΈ° int n = sc.nextInt(); int target = sc.nextInt(); // μ 체 μμ μ λ ₯λ°κΈ° int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } // μ΄μ§ νμ μν κ²°κ³Ό μΆλ ₯ int result = binarySearch(arr, target, 0, n - 1); if (result == -1) { System.out.println("μμκ° μ‘΄μ¬νμ§ μμ΅λλ€."); } else { System.out.println(result + 1); } } }
python
# μ΄μ§ νμ μμ€μ½λ ꡬν (λ°λ³΅λ¬Έ) def binary_search(array, target, start, end): while start <= end: mid = (start + end) // 2 # μ°Ύμ κ²½μ° μ€κ°μ μΈλ±μ€ λ°ν if array[mid] == target: return mid # μ€κ°μ μ κ°λ³΄λ€ μ°Ύκ³ μ νλ κ°μ΄ μμ κ²½μ° μΌμͺ½ νμΈ elif array[mid] > target: end = mid - 1 # μ€κ°μ μ κ°λ³΄λ€ μ°Ύκ³ μ νλ κ°μ΄ ν° κ²½μ° μ€λ₯Έμͺ½ νμΈ else: start = mid + 1 return None # n(μμμ κ°μ)κ³Ό target(μ°Ύκ³ μ νλ κ°)μ μ λ ₯ λ°κΈ° n, target = list(map(int, input().split())) # μ 체 μμ μ λ ₯ λ°κΈ° array = list(map(int, input().split())) # μ΄μ§ νμ μν κ²°κ³Ό μΆλ ₯ result = binary_search(array, target, 0, n - 1) if result == None: print("μμκ° μ‘΄μ¬νμ§ μμ΅λλ€.") else: print(result + 1)
Java
import java.util.*; public class Main { // μ΄μ§ νμ μμ€μ½λ ꡬν(λ°λ³΅λ¬Έ) public static int binarySearch(int[] arr, int target, int start, int end) { while (start <= end) { int mid = (start + end) / 2; // μ°Ύμ κ²½μ° μ€κ°μ μΈλ±μ€ λ°ν if (arr[mid] == target) return mid; // μ€κ°μ μ κ°λ³΄λ€ μ°Ύκ³ μ νλ κ°μ΄ μμ κ²½μ° μΌμͺ½ νμΈ else if (arr[mid] > target) end = mid - 1; // μ€κ°μ μ κ°λ³΄λ€ μ°Ύκ³ μ νλ κ°μ΄ ν° κ²½μ° μ€λ₯Έμͺ½ νμΈ else start = mid + 1; } return -1; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); // μμμ κ°μ(n)μ μ°Ύκ³ μ νλ κ°(target)μ μ λ ₯λ°κΈ° int n = sc.nextInt(); int target = sc.nextInt(); // μ 체 μμ μ λ ₯λ°κΈ° int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } // μ΄μ§ νμ μν κ²°κ³Ό μΆλ ₯ int result = binarySearch(arr, target, 0, n - 1); if (result == -1) { System.out.println("μμκ° μ‘΄μ¬νμ§ μμ΅λλ€."); } else { System.out.println(result + 1); } } }
bisect_left(a, x)
: μ λ ¬λ μμλ₯Ό μ μ§νλ©΄μ λ°°μ΄ aμ xλ₯Ό μ½μ
ν κ°μ₯ μΌμͺ½ μΈλ±μ€λ₯Ό λ°ν
bisect_right(a, x)
: μ λ ¬λ μμλ₯Ό μ μ§νλ©΄μ λ°°μ΄ aμ Xλ₯Ό μ½μ
ν κ°μ₯ μ€λ₯Έμͺ½ μΈλ±μ€λ₯Ό λ°ν
β
C++μμ bisect_left(a, x)
λ lower_bound
, bisect_right(a, x)
λ upper_bound
μ λμΌνλ€.
β
κ°μ΄ μλ μΈλ±μ€λ₯Ό λ°ννλ κ²μ΄λ€!
python
from bisect import bisect_left, bisect_right a = 11, 2, 4, 4, 8] x = 4 print(bisect_left(a, x)) print(bisect_right(a, x))
μ€νκ²°κ³Ό :
2
4
python
from bisect import bisect_left, bisect_right # κ°μ΄ [left value, right_ valuelμΈ λ°μ΄ν°μ κ°μλ₯Ό λ°ννλ ν¨μ def count_by_range(a, left_value, right_value): right_index = bisect_right(a, right_value) left_index = bisect_left(a, left_value) return right_index - left_index # λ°°μ΄ μ μΈ a= [1, 2, 3, 3, 3, 3, 4, 4, 8, 9] # κ°μ΄ 4μΈ λ°μ΄ν° κ°μ μΆλ ₯ print(count_by_range(a, 4, 4)) # κ°μ΄ [-1, 3] λ²μμ μλ λ°μ΄ν° κ°μ μΆλ ₯ print(count_by_range(a, -1, 3))
μ€νκ²°κ³Ό :
2
6
κ²°μ λ¬Έμ
('μ' νΉμ μλμ€')λ‘ λ°κΎΈμ΄ ν΄κ²°νλ κΈ°λ²μμ: νΉμ ν 쑰건μ λ§μ‘±νλ κ°μ₯ μλ§μ κ°
μ λΉ λ₯΄κ² μ°Ύλ μ΅μ ν λ¬Έμ
β
μΌλ°μ μΌλ‘ μ½λ© ν
μ€νΈμμ νλΌλ©νΈλ¦ μμΉ λ¬Έμ λ μ΄μ§ νμμ μ΄μ©νμ¬ ν΄κ²°ν μ μλ€.
μ μ ν λμ΄λ₯Ό μ°Ύμ λκΉμ§ μ΄μ§ νμμ μννμ¬ λμ΄ Hλ₯Ό λ°λ³΅ν΄μ μ‘°μ νλ©΄ λλ€
β
'νμ¬ μ΄ λμ΄λ‘ μλ₯΄λ©΄ 쑰건μ λ§μ‘±ν μ μλκ°?'λ₯Ό νμΈν λ€μ 쑰건μ λ§μ‘± μ¬λΆ('μ' νΉμ 'μλμ€)μ λ°λΌμ νμ λ²μλ₯Ό μ’νμ ν΄κ²°ν μ μλ€.
β
μ λ¨κΈ°μ λμ΄λ 0λΆν° 10μ΅κΉμ§μ μ μ μ€ νλ. μ΄λ κ² ν° νμ λ²μλ₯Ό 보면 κ°μ₯ λ¨Όμ μ΄μ§ νμ
μ λ μ¬λ €μΌ νλ€.
λ¬Έμ μμ μ μλ μμλ₯Ό ν΅ν΄ κ·Έλ¦ΌμΌλ‘ μ΄ν΄ν΄ 보μ
STEP 1 : μμ μΈλ±μ€: 0, μ€κ° μΈλ±μ€: 9, λ μΈλ±μ€: 19
β
μ΄λ νμν λ‘μ ν¬κΈ° : M = 6, μλ¦° λ‘μ κΈΈμ΄λ 25μ΄λ―λ‘ κ²°κ³Ό μ μ₯
β
λ‘μ ν¬κΈ°λ₯Ό λ§μ‘±νλ―λ‘ μ€κ° μΈλ±μ€λ₯Ό μ€λ₯Έμͺ½
μΌλ‘ μ΄λ (μ¦, μλ₯΄λ κ°μ ν¬κΈ°λ₯Ό λλ¦Ό)
STEP 2 : μμ μΈλ±μ€: 10, μ€κ° μΈλ±μ€: 14, λ μΈλ±μ€: 19
β
μ΄λ νμν λ‘μ ν¬κΈ° : M = 6, μλ¦° λ‘μ κΈΈμ΄λ 9μ΄λ―λ‘ κ²°κ³Ό μ μ₯
β
λ‘μ ν¬κΈ°λ₯Ό λ§μ‘±νλ―λ‘ μ€κ° μΈλ±μ€λ₯Ό μ€λ₯Έμͺ½
μΌλ‘ μ΄λ (μ¦, μλ₯΄λ κ°μ ν¬κΈ°λ₯Ό λλ¦Ό)
STEP 3 : μμ μΈλ±μ€: 15, μ€κ° μΈλ±μ€: 17, λ μΈλ±μ€: 19
β
μ΄λ νμν λ‘μ ν¬κΈ° : M = 6, μλ¦° λ‘μ κΈΈμ΄λ 2μ΄λ―λ‘ κ²°κ³Ό μ μ₯νμ§ μμ
β
λ‘μ ν¬κΈ°λ₯Ό λ§μ‘±νμ§ λͺ»νλ―λ‘ μ€κ° μΈλ±μ€λ₯Ό μΌμͺ½
μΌλ‘ μ΄λ (μ¦, μλ₯΄λ κ°μ ν¬κΈ°λ₯Ό μ€μ)
STEP 4 : μμ μΈλ±μ€: 15, μ€κ° μΈλ±μ€: 15, λ μΈλ±μ€: 16
β
μ΄λ νμν λ‘μ ν¬κΈ° : M = 6, μλ¦° λ‘μ κΈΈμ΄λ 6μ΄λ―λ‘ κ²°κ³Ό μ μ₯
β
λ‘μ ν¬κΈ°λ₯Ό λ§μ‘±νκ³ μμ μΈλ±μ€μ μ€κ° μΈλ±μ€κ° κ°μΌλ―λ‘ μΈλ±μ€ 리ν΄
python
# λ‘μ κ°μ(N)μ μμ²ν λ‘μ κΈΈμ΄(M)μ μ λ ₯ n, m = list(map(int, input().split(' '))) # κ° λ‘μ κ°λ³ λμ΄ μ 보λ₯Ό μ λ ₯ array = list(map(int, input().split())) # μ΄μ§ νμμ μν μμμ κ³Ό λμ μ€μ start = 0 end = max(array) # μ΄μ§ νμ μν (λ°λ³΅μ ) result = 0 while(start <= end): total = 0 mid = (start + end) // 2 for x in array: # μλμ λμ λ‘λ³Άμ΄ μ κ³μ° if x > mid: total += x - mid # λ‘λ³Άμ΄ μμ΄ λΆμ‘±ν κ²½μ° λ λ§μ΄ μλ₯΄κΈ° (μ€λ₯Έμͺ½ λΆλΆ νμ) if total < m: end = mid - 1 # λ‘λ³Άμ΄ μμ΄ μΆ©λΆν κ²½μ° λ μλ₯΄κΈ° (μΌμͺ½ λΆλΆ νμ) else: result = mid # μ΅λν λ μλμ λκ° μ λ΅μ΄λ―λ‘, μ¬κΈ°μμ resultμ κΈ°λ‘ start = mid + 1 # μ λ΅ μΆλ ₯ print(result)
Java
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // λ‘μ κ°μ(N)μ μμ²ν λ‘μ κΈΈμ΄(M) int n = sc.nextInt(); int m = sc.nextInt(); // κ° λ‘μ κ°λ³ λμ΄ μ 보 int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } // μ΄μ§ νμμ μν μμμ κ³Ό λμ μ€μ int start = 0; int end = (int) 1e9; // μ΄μ§ νμ μν (λ°λ³΅μ ) int result = 0; while (start <= end) { long total = 0; int mid = (start + end) / 2; for (int i = 0; i < n; i++) { // μλμ λμ λ‘μ μ κ³μ° if (arr[i] > mid) total += arr[i] - mid; } if (total < m) { // λ‘μ μμ΄ λΆμ‘±ν κ²½μ° λ λ§μ΄ μλ₯΄κΈ°(μΌμͺ½ λΆλΆ νμ) end = mid - 1; } else { // λ‘μ μμ΄ μΆ©λΆν κ²½μ° λ μλ₯΄κΈ°(μ€λ₯Έμͺ½ λΆλΆ νμ) result = mid; // μ΅λν λ μλμ λκ° μ λ΅μ΄λ―λ‘, μ¬κΈ°μμ resultμ κΈ°λ‘ start = mid + 1; } } System.out.println(result); } }
π€ μ΄λ¬ν μ΄μ§ νμ
κ³Όμ μ λ°λ³΅νλ©΄ λ΅μ λμΆν μ μλ€.
μ€κ°μ μ κ°μ μκ°μ΄ μ§λ μλ‘ μ΅μ νλ κ°
μ΄ λκΈ° λλ¬Έμ, κ³Όμ μ λ°λ³΅νλ©΄μ μ»μ μ μλ λ‘μ κΈΈμ΄ ν©μ΄ νμν λ‘μ κΈΈμ΄λ³΄λ€ ν¬κ±°λ κ°μ λλ§λ€ μ€κ° μΈλ±μ€μ κ°
μ κΈ°λ‘νλ©΄ λλ€.
β
μκ° λ³΅μ‘λ O(logN)
μΌλ‘ λμνλ μκ³ λ¦¬μ¦μ μꡬ
β
μΌλ°μ μΈ μ ν νμ(Linear Search)λ‘λ μκ° μ΄κ³Ό νμ μ λ°λλ€.
β
νμ§λ§ λ°μ΄ν°κ° μ λ ¬λμ΄ μκΈ° λλ¬Έμ μ΄μ§ νμ
μ μνν μ μλ€.
β
νΉμ κ°μ΄ λ±μ₯νλ 첫 λ²μ§Έ μμΉμ λ§μ§λ§ μμΉλ₯Ό μ°Ύμ μμΉ μ°¨μ΄λ₯Ό κ³μ°ν΄ λ¬Έμ λ₯Ό ν΄κ²°ν μ μλ€.
python (κ΅μ¬.ver)
from bisect import bisect_left, bisect_right # κ°μ΄ [left_value, right_value]μΈ λ°μ΄ν°μ κ°μλ₯Ό λ°ννλ ν¨μ def count_by_range(array, left_value, right_value): right_index = bisect_right(array, right_value) left_index = bisect_left(array, left_value) return right_index - left_index n, x = map(int, input().split()) # λ°μ΄ν°μ κ°μ N, μ°Ύκ³ μ νλ κ° x μ λ ₯ λ°κΈ° array = list(map(int, input().split())) # μ 체 λ°μ΄ν° μ λ ₯ λ°κΈ° # κ°μ΄ [x, x] λ²μμ μλ λ°μ΄ν°μ κ°μ κ³μ° count = count_by_range(array, x, x) # κ°μ΄ xμΈ μμκ° μ‘΄μ¬νμ§ μλλ€λ©΄ if count == 0: print(-1) # κ°μ΄ xμΈ μμκ° μ‘΄μ¬νλ€λ©΄ else: print(count)
python (μ§μ.ver)
from bisect import bisect_left, bisect_right n, x = map(int, (input().split())) arr = list(map(int, input().split())) result = bisect_right(arr, x) - bisect_left(arr, x) print(result if result > 0 else "-1")
Java
import java.util.*; public class Main { public static int lowerBound(int[] arr, int target, int start, int end) { while (start < end) { int mid = (start + end) / 2; if (arr[mid] >= target) end = mid; else start = mid + 1; } return end; } public static int upperBound(int[] arr, int target, int start, int end) { while (start < end) { int mid = (start + end) / 2; if (arr[mid] > target) end = mid; else start = mid + 1; } return end; } // κ°μ΄ [left_value, right_value]μΈ λ°μ΄ν°μ κ°μλ₯Ό λ°ννλ ν¨μ public static int countByRange(int[] arr, int leftValue, int rightValue) { // μ μ: lowerBoundμ upperBoundλ end λ³μμ κ°μ λ°°μ΄μ κΈΈμ΄λ‘ μ€μ int rightIndex = upperBound(arr, rightValue, 0, arr.length); int leftIndex = lowerBound(arr, leftValue, 0, arr.length); return rightIndex - leftIndex; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); // λ°μ΄ν°μ κ°μ N, μ°Ύκ³ μ νλ κ° x μ λ ₯λ°κΈ° int n = sc.nextInt(); int x = sc.nextInt(); // μ 체 λ°μ΄ν° μ λ ₯λ°κΈ° int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } // κ°μ΄ [x, x] λ²μμ μλ λ°μ΄ν°μ κ°μ κ³μ° int cnt = countByRange(arr, x, x); // κ°μ΄ xμΈ μμκ° μ‘΄μ¬νμ§ μλλ€λ©΄ if (cnt == 0) System.out.println(-1); // κ°μ΄ xμΈ μμκ° μ‘΄μ¬νλ€λ©΄ else System.out.println(cnt); } }