[이진탐색] 부품찾기

[ericagong]

⭐ 성찰

1. 집합의 in 연산은 O(1) 소요되므로 존재 여부 파악에 매우 효율적임. cf) 배열의 in 연산은 O(N) 소요
2. 계수 정렬을 하는 경우, 공간 복잡도를 잘 고려해보아야 함
3. 시간 복잡도 계상 편의성을 위해 10만, 100만, 1000만, 1억, 10억에 대한 logN값 익혀두기

$$log_2 {10^3} = 10 $$

$$log_2 {10^6} = 20 $$

$$log_2 {10^9} = 30 $$

$$log_2 {100,000} = 16 $$

$$log_2 {1,000,000} = 19 $$

$$log_2 {10,000,000} = 20 $$

$$log_2 {100,000,000} = 23 $$

$$log_2 {100,000,000} = 30 $$

❓ 문제 상황

[부품찾기] 이코테 p.197

👨‍💻 문제 해결: 이진탐색

✅ 1차 풀이: 간단한 이진탐색

⌛ 시간복잡도: O(NlogN) <= 2,000만

• 정렬의 시간복잡도 O(NlogN)
• 이진 탐색의 시간복잡도 O(MlogN)
• M = 1 비교 연산
• N = 1,000,000, logN = 20
  1. 이진 탐색 전 반드시 정렬을 수행함
  2. 찾고자 하는 부품이 있는지 정렬을 수행함

     
     import sys

input = sys.stdin.readline n = int(input()) nums = list(map(int, input().split())) m = int(input()) checks = list(map(int, input().split()))

이진 탐색을 위해서는 반드시 정렬 필요

nums.sort()

def binary_search(li, t, s, e): while s <= e: mid = (s + e) // 2 if li[mid] == t: return 'yes' elif li[mid] < t: s = mid + 1 else: e = mid - 1 return 'no'

for c in checks: print(binary_search(nums, c, 0, len(nums)-1), end=' ')

### ✅ 2차 풀이: 계수 정렬
#### ⌛ 시간복잡도 O(N) <= 1,000,000 
- 배열의 특정 인덱스에 접근하는 연산은 O(1) 소요
1. 계수 정렬에 착안하여 부품이 있다면 해당 배열 요소의 값을 1 증가
2. 이후 요청받은 물품 존재 여부를 해당 배열의 요소 값이 1 이상인지 보고 판단
```python
import sys

input = sys.stdin.readline
n = int(input())
nums = [0] * (1000001)

for _ in range(n):
  num = int(input())
  nums[num] += 1

m = int(input())
checks = list(map(int, input().split()))

for item in checks:
  if nums[item] >= 1:
    print('yes', end=' ')
  else:
    print('no', end=' ')

✅ 3차 풀이: 집합

⌛ 시간복잡도 O(M) <= 2000만

• M = 100,000
  1. 집합 자료형의 포함 여부에 대한 연산은 O(1) 소요
  2. 따라서 집합 자료형으로 받은 뒤, is in 연산 수행해 존재 여부 판단

     
     import sys

input = sys.stdin.readline n = int(input()) nums = set(map(int, input().split())) m = int(input()) checks = list(map(int, input().split()))

for item in checks: if item in nums: print('yes', end=' ') else: print('no', end=' ')