문제 출처 : https://www.acmicpc.net/problem/1920
문제 파악
문제 자체는 간단하다.
N_list = [4,1,5,2,3]
M_list = [1,3,7,9,5]
두개의 정수배열을 입력받고,
M_list의 요소들이 N_list에 존재하는 지 없는 지 파악하여
있다면 1, 없다면 0 을 출력하는 문제
위 경우 답은 1 1 0 0 1 을 한 줄씩 출력해주면 된다.
첫번째로는 완전탐색을 떠올렸다.
이중 반복문을 돌면 다 탐색이 가능하니 문제 조건을 봤다.
N,M 최댓값이 100,000 으로
2중반복문을 돌면 100,000 * 100,000 = 100억이 된다.
파이썬 언어로는 1억 미만이 시간복잡도에서 걸리지 않기에
완전탐색은 불가하다.
그러면?
이분 탐색
이 문제는 이분 탐색 스킬을 써야한다.
그래서 이분 탐색이 뭔지 알아보자.
1. 이분탐색(Binary Search)란 무엇인가
이분탐색 : 정렬된 범위에서, 절반을 버리면서 원하는 값을 찾는 알고리즘
=> 정답 후보의 범위를 절반씩 좁힌다.
반드시 필요한 조건은 '정렬돼 있음(= 단조성)' 이다.
즉 계속 정렬된 상태로 계속 증가하거나, 감소하는 꼴이어야 사용이 가능하다.
2. 언제 떠올려야 하는가 — 3가지 트리거
코테에서 이분탐색을 떠올리는 상황 신호 3가지가 있다.
(1) 정렬된 배열에서 특정 값/범위 찾기
(2) 정답이 ‘수치 범위’일 때
(3) 조건이 단조적(monotonic)일 때
어떤 지점 기준으로
False -> True, 또는
True -> False
이 경우 경계 지점을 이분탐색으로 찾는다.
→ 단조적 → YES/NO 검사 → 이분탐색.
3. 대표적인 형태
def binary_search(arr, target):
l = 0
r = len(arr) - 1
while l <= r:
mid = (l + r) // 2
if arr[mid] == target:
return mid # 정답 발견
elif arr[mid] < target:
l = mid + 1 # 오른쪽만 봄
else:
r = mid - 1 # 왼쪽만 봄
return -1 # 없으면 -1 같은 값 반환이렇게 left, right를 지정하고, 중간값을 구해 그 값과 target과 계속 비교하며 left, right의 인덱스를 조정하며 target을 찾는다.
이렇게 하면 시간복잡도는 O(log N) 이 된다.
원리 적용
이 기법으로 수 찾기 문제를 풀어보자면
우선 N_list , M_list 가 있다고 했을 때
- 이분 탐색 알고리즘의 조건에 따라 수가 단조적이어야 하므로 N_list를 정렬해준다.
- M_list 요소들에 대해 반복문을 돌며 이분탐색을 통해 N_list에 존재하는 지 파악하고, answer 배열에 1 또는 0 을 넣는다.
- answer 배열을 하나씩 출력해준다.
해답 및 풀이
import sys
input = sys.stdin.readline
N = int(input())
N_list = list(map(int,input().split()))
# N_list 정렬
N_list.sort()
M = int(input())
M_list = list(map(int,input().split()))
answer = [] # M개 채워야 함
def binary_search(array, target):
left = 0
right = len(array)-1
while left <= right:
mid = (right + left) // 2
if array[mid] == target:
return True
elif array[mid] < target:
left = mid + 1
else:
right = mid - 1
return False
for m in M_list:
if binary_search(N_list, m):
answer.append(1)
else:
answer.append(0)
for a in answer:
print(a)이분 탐색 꼴 머리에 넣기
다음날 다시 푼 코드
import sys
input = sys.stdin.readline
N = int(input())
N_list = list(map(int,input().split()))
# N_list 정렬
N_list.sort()
M = int(input())
M_list = list(map(int,input().split()))
def binary_search(arr,target):
l = 0
r = len(arr)-1
while l <= r :
mid = (l+r) // 2
if arr[mid] == target:
return 1
elif arr[mid] > target:
r = mid -1
else:
l = mid + 1
return 0
for m in M_list:
print(binary_search(N_list,m))answer 배열을 따로 만들지 않고 바로 return 하는 식으로 코드를 간결화했다.
elif arr[mid] > target:
r = mid -1
else:
l = mid + 1 arr[mid] 보다 크고작음을 이용해 전체 탐색 범위를 반으로 나누는 이분탐색 알고리즘이지만
elif arr[mid] > target:
r -= 1
else:
l += 1이렇게 코드를 짜서 시간초과가 났었다.
이분 탐색은 mid를 기준으로 반씩 날리는 탐색임을 잊지말자.
